On test generation by input cube avoidance

ABSTRACT

Test generation procedures attempt to assign values to the inputs of a circuit so as to detect target faults. We study a complementary view whereby the goal is to identify values that should not be assigned to inputs in order not to prevent faults from being detected. We describe a procedure for computing input cubes (or incompletely specified input vectors) that should be avoided during test generation for target faults. We demonstrate that avoiding such input cubes leads to the detection of target faults after the application of limited numbers of random input vectors. This indicates that explicit test generation is not necessary once certain input values are precluded. Potential uses of the computed input cubes are in a test generation procedure to reduce the search space, and during built-in test generation to preclude input vectors that will not lead to the detection of target faults.

REFERENCES

• 1: P. Goel and B. C. Rosales, "Test Generation and Dynamic Compaction of Tests", in Proc. Test Conf., 1979 pp. 189--192.
• 2: Irith Pomeranz , Lakshmi N. Reddy , Sudhakar M. Reddy, COMPACTEST: A Method to Generate Compact Test Sets for Combinatorial Circuits, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.194-203, October 26-30, 1991
• 3: J.-S. Chang and C.-S. Lin, "Test Set Compaction for Combinational Circuits", in Proc. Asian Test Symp., 1992, pp. 20--25.
• 4: Y. Matsunaga, "MINT -An Exact Algorithm for Finding Minimum Test Sets", IEICE Trans. Fundamentals., vol. E76-A, No. 10, Oct. 1993, pp. 1652--1658.
• 5: S. Kajihara, I. Pomeranz, K. Kinoshita and S. M. Reddy, "Cost-Effective Generation of Minimal Test Sets for Stuck-at Faults in Combinational Logic Circuits", IEEE Trans. on Computer-Aided Design, Dec. 1995, pp. 1496--1504.
• 6: 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]
• 7: Thomas J. Snethen, Simulator-oriented fault test generator, Proceedings of the 14th conference on Design automation, p.88-93, January 1977
• 8: V. D. Agrawal, K. T. Cheng, and P. Agrawal, "A Directed Search Method for Test Generation Using Concurrent Simulator," IEEE Trans, on Computer-Aided Design, Feb. 1989, pp. 131--138.
• 9: Daniel G. Saab , Youssef G. Saab , Jacob A. Abraham, CRIS: a test cultivation program for sequential VLSI circuits, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.216-219, November 1992, Santa Clara, California, United States
• 10: Elizabeth M. Rudnick , Janak H. Patel , Gary S. Greenstein , Thomas M. Niermann, Sequential circuit test generation in a genetic algorithm framework, Proceedings of the 31st annual conference on Design automation, p.698-704, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196619]
• 11: Paolo Prinetto , Maurizio Rebaudengo , Matteo Sonza Reorda, An Automatic Test Pattern Generator for Large Sequential Circuits Based on Genetic Algorithms, Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years, p.240-249, October 02-06, 1994
• 12: I. Pomeranz , S. M. Reddy, On improving genetic optimization based test generation, Proceedings of the 1997 European conference on Design and Test, p.506, March 17-20, 1997
• 13: Mahesh A. Iyer , Miron Abramovici, Sequentially Untestable Faults Identified Without Search ("Simple Implications Beat Exhaustive Search!"), Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years, p.259-266, October 02-06, 1994
• 14: D. E. Long , M. A. Iyer , M. Abramovici, Identifying sequentially untestable faults using illegal states, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.4, April 30-May 03, 1995
• 15: Mahesh A. Iyer , David E. Long , Miron Abramovici, Identifying sequential redundancies without search, Proceedings of the 33rd annual conference on Design automation, p.457-462, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240605]
• 16: On Finding Undetectable and Redundant Faults in Synchronous Sequential Circuits, Proceedings of the International Conference on Computer Design, p.498, October 05-05, 1998
• 17: Qiang Peng , Jacob Savir, MUST: Multiple-Stem Analysis for Identifying Sequentially Untestable Faults, Proceedings of the 2000 IEEE International Test Conference, p.839, October 03-05, 2000
• 18: Manan Syal , Michael S. Hsiao, Untestable Fault Identification using Recurrence Relations and Impossible Value Assignments, Proceedings of the 17th International Conference on VLSI Design, p.481, January 05-09, 2004
• 19: Yung-Chieh Lin , Feng Lu , Kai Yang , Kwang-Ting Cheng, Constraint extraction for pseudo-functional scan-based delay testing, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120797]
• 20: João P. Marques-Silva , Karem A. Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transactions on Computers, v.48 n.5, p.506-521, May 1999 [doi>10.1109/12.769433]