Test vector decomposition-based static compaction algorithms for combinational circuits

ABSTRACT

Testing system-on-chips involves applying huge amounts of test data, which is stored in the tester memory and then transferred to the chip under test during test application. Therefore, practical techniques, such as test compression and compaction, are required to reduce the amount of test data in order to reduce both the total testing time and memory requirements for the tester. In this article, a new approach to static compaction for combinational circuits, referred to as test vector decomposition (TVD), is proposed. In addition, two new TVD based static compaction algorithms are presented. Experimental results for benchmark circuits demonstrate the effectiveness of the two new static compaction algorithms.

REFERENCES

• 1: Abramovici, M., Bruer, M. A., and Friedman, A. D. 1990. Digital Systems Testing and Testable Design. IEEE, Piscataway, NJ.
• 2: Abramovici, M., Menon, P. R., and Miller, D. T. 1984. Critical path tracing---an alternative to fault simulation. IEEE Design Test, 83--92.
• 3: Akers, S. B. and Joseph, C. 1987. On the role of independent fault sets in the generation of minimal test sets. In Proceedings of the International Test Conference (Washington, D.C.). IEEE Computer Society Press, Los Alamitos, Calif., 1100--1107.
• 4: Akers, S. B., Krishamurthy, B., Park, S., and Swaminathan, A. 1990. Why is less information from logic simulation more useful in fault simulation? In Proceedings of the International Test Conference. IEEE, Los Alamitos, Calif., 786--800.
• 5: Sheldon B. Akers , Balakrishnan Krishnamurthy, Test Counting: A Tool for VLSI Testing, IEEE Design & Test, v.6 n.5, p.58-77, September 1989 [doi>10.1109/54.43080]
• 6: Ayari, B. and Kaminska, B. 1994. A new dynamic test vector compaction for automatic test pattern generation. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 13, 3 (Mar.), 353--358.
• 7: Kwame Osei Boateng , Hideaki Konishi , Tsuneo Nakata, A Method of Static Compaction of Test Stimuli, Proceedings of the 10th Asian Test Symposium, p.137, November 19-21, 2001
• 8: Chang, J.-S. and Lin, C.-S. 1995. Test set compaction for combinational circuits. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 14, 11 (Nov.), 1370--1378.
• 9: Aiman El-Maleh , Ali Al-Suwaiyan, An Efficient Test Relaxation Technique for Combinational & Full-Scan Sequential Circuits, Proceedings of the 20th IEEE VLSI Test Symposium, p.53, April 28-May 02, 2002
• 10: Paulo F. Flores , Horácio C. Neto , João P. Marques-Silva, On Applying Set Covering Models to Test Set Compaction, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.8, March 04-06, 1999
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Ilker Hamzaoglu , Janak H. Patel, Test set compaction algorithms for combinational circuits, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.283-289, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288615]
• 13: Hamzaoglu, I. and Patel, J. H. 2000. Test set compaction algorithms for combinational circuits. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 19, 8 (Aug.), 957--963.
• 14: Hochbaum, D. S. 1996. An optimal test compression procedure for combinational circuits. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 15, 10 (Oct.), 1294--1299.
• 15: Seiji Kajihara , Kohei Miyase, On identifying don't care inputs of test patterns for combinational circuits, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 16: Kajihara, S., Pomeranz, I., Kinoshita, K., and Reddy, S. M. 1994. On compacting test sets by addition and removal of test vectors. In Proceedings of the VLSI Test Symposium (Cherry Hill, N.J.). IEEE Computer Society Press, Los Alamitos, Calif., 25--28.
• 17: Kajihara, S., Pomeranz, I., Kinoshita, K., and Reddy, S. M. 1995. Cost effective generation of minimal test sets for stuck-at faults in combinational logic circuits. IEEE Trans. Computer-Aided Des. 14, 12 (Dec.), 1496--1504.
• 18: Krishnamurthy, B. and Akers, S. B. 1984. On the complexity of estimating the size of a test set. IEEE Trans. Comput. C-33, 8 (Aug.), 750--753.
• 19: Lee, H. K. and Ha, D. S. 1996. HOPE: An efficient parallel fault simulator for synchronous sequential circuits. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 15, 9 (Sept.), 1048--1058.
• 20: Xijiang Lin , Janusz Rajski , Irith Pomeranz , Sudhakar M. Reddy, On static test compaction and test pattern ordering for scan designs, Proceedings of the IEEE International Test Conference 2001, p.1088-1097, October 30-November 01, 2001
• 21: James A. McHugh, Algorithmic graph theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 22: Kohei Miyase , Seiji Kajihara , Sudhakar M. Reddy, A Method of Static Test Compaction Based on Don't Care Identification, Proceedings of the The First IEEE International Workshop on Electronic Design, Test and Applications (DELTA '02), p.392, January 29-31, 2002
• 23: Thomas Niermann , Janak H. Patel, HITEC: a test generation package for sequential circuits, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 24: Pomeranz, I., Reddy, L. N., and Reddy, S. M. 1993. Compacttest: A method to generate compact test sets for combinational circuits. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 12, 7 (July), 1040--1049.
• 25: Pomeranz, I. and Reddy, S. M. 1992. Generalization of independent faults for transition faults. In Proceedings of the VLSI Test Symposium (Atlantic City, N.J.). IEEE Computer Society Press, Los Alamitos, Calif., 7--12.
• 26: Pomeranz, I. and Reddy, S. M. 2001. Forward-looking fault simulation for improved static compaction. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 20, 10 (Oct.), 1262--1265.
• 27: Reddy, L. N., Pomeranz, I., and Reddy, S. M. 1992. ROTCO: A reverse order test compaction technique. In Proceedings of the EURO-ASIC Conference (Paris, France). IEEE Computer Society Press, Los Alamitos, Calif., 189--194.
• 28: Schulz, M. H., Trischler, E., and Sarfert, T. M. 1988. SOCRATES: A highly efficient automatic test pattern generation system. IEEE Trans. Computer-Aided Des. Integ. Circ. Syst. 7, 1 (Jan.), 126--137.
• 29: Gert-Jan Tromp, Minimal Test Sets for Combinatorial Circuits, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.204-209, October 26-30, 1991
• 30: Wang, J. C. and Stabler, E. P. 1995. Collective test generation and test set compaction. In Proceedings of the International Symposium on Circuits and Systems (Seattle, Wash.). IEEE Computer Society Press, Los Alamitos, Calif., 2008--2011.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.3 Reliability and Testing**

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Theory

Keywords:
Static compaction, class-based clustering, combinational circuits, independent fault clustering, taxonomy, test vector decomposition