An exact solution to the minimum size test pattern problem

ABSTRACT

This article addresses the problem of test pattern generation for single stuck-at faults in combinational circuits, under the additional constraint that the number of specified primary input assignments is minimized. This problem has different applications in testing, including the identification of "don't care" conditions to be used in the synthesis of Built-In Self-Test (BIST) logic. The proposed solution is based on an integer linear programming (ILP) formulation which builds on an existing Propositional Satisfiability (SAT) model for test pattern generation. The resulting ILP formulation is linear on the size of the original SAT model for test generation, which is linear on the size of the circuit. Nevertheless, the resulting ILP instances represent complex optimization problems, that require dedicated ILP algorithms. Preliminary results on benchmark circuits validate the practical applicability of the test pattern minimization model and associated ILP algorithm.

REFERENCES

• 1: ABRAMOVICI, M., BREUER, M. A., AND FRIEDMAN, A. D. 1990. Digital Systems Testing and Testable Design. IEEE Press, New York.
• 2: BRGLEZ,F.,AND FUJIWARA, H. 1985. A neutral list of 10 combinational benchmark circuits and a target translator in FORTRAN. In Proceedings of the IEEE International Symposium on Circuits and Systems.
• 3: Krishnendu Chakrabarty , Jian Liu , Minyao Zhu , Brian T. Murray, Test Width Compression for Built-In Self Testing, Proceedings of the IEEE International Test Conference, p.328-337, November 03-05, 1997
• 4: CHAKRADHAR,S.T.,AGRAWAL,V.D.,AND ROTHWEILER, S. G. 1993. A transitive closure algorithm for test generation. IEEE Trans. Comput.-Aided Des. 12, 7 (July), 1015-1028.
• 5: COX, H., AND RAJSKI, J. 1994. On necessary and nonconflicting assignments in algorithmic test patterns generation. IEEE Trans. Comput.-Aided Des. 13, 4 (Apr.), 515-530.
• 6: FLORES, P., NETO, H., AND MARQUES-SILVA, J. 2000. On computing minimum size test patterns. Tech. Rep. RT/008/2000 (Sept.). INESC, Lisbon, Portugal.
• 7: FUJIWARA, H., AND SHIMONO, T. 1983. On the acceleration of test generation algorithms. IEEE Trans. Comput. 32, 12 (Dec.), 1137-1144.
• 8: John Giraldi , Michael L. Bushnell, Search State Equivalence for Redundancy Identification and Test Generation, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.184-193, October 26-30, 1991
• 9: GOEL, P. 1981. An implicit enumeration algorithm to generate tests for combinational logic circuits. IEEE Trans. Comput. 30, 3 (Mar.), 215-222.
• 10: Sybille Hellebrand , Birgit Reeb , Steffen Tarnick , Hans-Joachim Wunderlich, Pattern generation for a deterministic BIST scheme, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.88-94, November 05-09, 1995, San Jose, California, United States
• 11: IWLS. 1989. Test benchmark suite. International Workshop on Logic Synthesis 1989. Available from http://www.cbl.ncsu.edu/pub/Benchmark dirs/LGSynth89/.
• 12: T. Kirkland , M. R. Mercer, A topological search algorithm for ATPG, Proceedings of the 24th ACM/IEEE conference on Design automation, p.502-508, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37963]
• 13: Wolfgang Kunz , Dhiraj K. Pradhan, Recursive Learning: An Attractive Alternative to the Decision Tree for Test Genration in Digital Circuits, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.816-825, September 20-24, 1992
• 14: LARRABEE, T. 1992. Test pattern generation using Boolean satisfiability. IEEE Trans. Comput.-Aided Des. 11, 1 (Jan.), 4-15.
• 15: LEE,H.K.,AND HA, D. S. 1993. On the generation of test patterns for combinational circuits. Tech. Rep. 12 93, Department of Electrical Engineering, Virginia Polytechnic Institute and State University.
• 16: Prime Implicant Computation Using Satisfiability Algorithms, Proceedings of the 9th International Conference on Tools with Artificial Intelligence, p.232, November 03-08, 1997
• 17: 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
• 18: Clara Pizzuti, Computing Prime Implicants by Integer Programming, Proceedings of the 8th International Conference on Tools with Artificial Intelligence (ICTAI '96), p.332, November 16-19, 1996
• 19: POMERANZ, I., REDDY,L.N.,AND REDDY, S. M. 1993. COMPACTEST: A method to generate compact test sets for combinational circuits. IEEE Trans. Comput.-Aided Des. Integ. Circ. Syst. 12, 7 (July), 1040-1049.
• 20: SCHULZ,M.H.,AND AUTH, E. 1989. An improved deterministic test pattern generation with applications to redundancy identification. IEEE Trans. Comput.-Aided Des. 8, 7 (July), 811-816.
• 21: João P. Marques Silva , Karem A. Sakallah, Dynamic search-space pruning techniques in path sensitization, Proceedings of the 31st annual conference on Design automation, p.705-711, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196621]
• 22: Joao P. Marques Silva , Karem A. Sakallah, Robust Search Algorithms for Test Pattern Generation, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.152, June 25-27, 1997
• 23: STEPHAN, P. R., BRAYTON,R.K.,AND SANGIOVANNI-VINCENTELLI, A. L. 1996. Combinational test generation using satisfiability. IEEE Trans. Comput.-Aided Des. 15, 9 (Sept.), 1167-1176.
• 24: Mitsuo Teramoto, A Method for Reducing the Search Space in Test Pattern Generation, Proceedings of the IEEE International Test Conference on Designing, Testing, and Diagnostics - Join Them, p.429-435, October 17-21, 1993

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

General Terms:
Algorithms, Reliability

Keywords:
Automatic test pattern generation (ATPG), built-in self-test (BIST), integer linear programming (ILP), propositional satisfiability (SAT), verification and test