A Modified Run Length Coding Technique for Test Data Compression Based on Multi-Level Selective Huffman Coding

Test data compression is an efficient method for reducing the test application cost. The problem of reducing test data has been addressed by researchers in three different aspects: Test Data Compression, Built-in-Self-Test (BIST) and Test set compaction. The latter two methods are capable of enhancing fault coverage with cost of hardware overhead. The drawback of the conventional methods is that they are capable of reducing the test storage and test power but when test data have redundant length of runs, no additional compression method is followed. This paper presents a modified Run Length Coding (RLC) technique with Multilevel Selective Huffman Coding (MLSHC) technique to reduce test data volume, test pattern delivery time and power dissipation in scan test applications where redundant length of runs is encountered then the preceding run symbol is replaced with tiny codeword. Experimental results show that the presented method not only improves the test data compression but also reduces the overall test data volume compared to recent schemes. Experiments for the six largest ISCAS-98 benchmarks show that our method outperforms most known techniques.

[1] V. Iyengar, K. Chakrabarty and B. T Murray, “Built-in Self-Testing of Sequential Circuits Using Precomputed Test Sets”, Proc. VTS., pp.418-423, 1998.
[2] Jas, J. Ghosh-Dastidar and N. A. Touba, “Scan Vector Compression/Decompression Using Statistical Coding”, Proc. VTS, pp.114-120, 1999.
[3] N.A. Touba, “Survey of test vector compression techniques”, IEEE Design and Test of Computers 23 (4) (2006) 294–303.
[4] Kalamani, C & Paramasivam, K, “Survey of Low Power Testing Using Compression Techniques”, International Journal of Electronics & Communication Technology, vol. 4, no. 4(2013), pp. 13-18.
[5] Wenfa Zhan, Huaguo Liang, Feng Shi, “Test data compression scheme based on variable-to-fixed-plus-variable-length coding”, Journal of Systems Architecture 53 (11) (2007) 877–887.
[6] L. Lei, K. Chakrabarty, “Test data compression using dictionaries with fixed-length indices”, in: Proceedings of the VLSI Test Symposium, 2003, pp. 219–224.
[7] Al-Yamani, E. McCluskey, “Seed encoding for LFSRs and cellular automata”, in: Proceedings of the Design Automation Conference, 2003, pp. 560–565.
[8] Jas, J. Ghosh-Dastidar, N.A. Touba, “An efficient test vector compression scheme using selective Huffman coding”, IEEE Transactions on Computer- Aided Design 23 (6) (2003) 797–806.
[9] Jas, N.A. Touba, “Test vector decompression via cyclical scan chains and its application to testing core-based designs”, in: Proceedings of the International Test Conference, 1998, pp. 458–464.
[10] T. Paul, B. Al-Hashimi, N. Nicolici, “Variable-Length input huffman coding for system-on-a-chip test”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 22 (6) (2003) 783–796.
[11] Chandra, K. Chakrabarty, “System-on-a-chip test data compression and decom- pression architectures based on Golomb codes”, IEEE Transitions on Computer-Aided Design of Integrated Circuits and System 20 (3) (2001) 355–368.
[12] Chandra, K. Chakrabarty, “Test data compression and test resource partitioning for system-on-a-chip using frequency-directed run-length (FDR) codes”, IEEE Transactions on Computers 52 (8) (2003) 1076–1088.
[13] Chandra, K. Chakrabarty, “Reduction of SOC test data volume, scan power and testing time using alternating run-length codes”, in: Proceedings of the IEEE/ACM Design Automation Conference, 2002, pp. 673–678.
[14] Wuertenberger, C.S. Tautermann, S. Hellebrand, “A hybrid coding strategy for optimized test data compression”, in: Proceedings of the International Test Conference, 2003, pp. 451–459.
[15] Aiman El-Maleh, “Test data compression for system-on-a-chip using extended frequency-directed run-length code”, IET Computers and Digital Techniques 2 (3) (2008) 155–163.
[16] Kavousianos, Xrysovalantis, Emmanouil Kalligeros, and Dimitris Nikolos. "Multilevel Huffman coding: an efficient test-data compression method for IP cores", Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 26.6 (2007): 1070-1083.
[17] Mehta, Usha Sandeep, Kankar S. Dasgupta, and Nirnjan M. Devashrayee. "Modified selective Huffman coding for optimization of test data compression, test application time and area overhead", Journal of Electronic Testing 26.6 (2010): 679-688.
[18] W. Zhan, A. El-Maleh, “A new scheme of test data compression based on equal- run-length coding (ERLC)”,, Integr. VLSI Journal. 45(1) (2012) 91–98.
[19] M. Nourani, M. H. Tehranipour, “RL-Huffman encoding for test compression and Power reduction in scan applications”, ACM Trans. Design Autom. Electron.Syst. 10(1)(2005)91–115.
[20] D. Huffman, “A method for the construction of minimum-redundancy codes”, Proc. IRE40 (9) (1952) 1098–1101.
[21] X. Kavousianos, E. Kalligeros, D. Nikolos, “Optimal selective Huffman coding for test-data compression”, IEEETrans.Comput.56 (8)(2007) 1146–1152.
[22] M. VidyaSagar, J.S. Rose Victor, “Modified Run Length Encoding Scheme for High Data Compression Rate’’, International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) 2(12), (2013) 3238-3241.