ATPG tools for delay faults at the functional level

ABSTRACT

We present an ATPG tool for functional delay faults which applies to the single-input transition (SIT) and the multi-input transition (MIT) fault models, and is based on Reduced Ordered Binary Decision Diagrams (ROBDDs). We are able, for the first time, to identify all faults that do not have any SIT tests, and generate all SIT tests for nonredundant faults in combinational circuits. We also provide methodologies for efficient generation of MIT tests. Our experimental results on the ISCAS'85 benchmarks is by far superior to existing methods as well as a Satisfiability-based tool that we have developed for comparative purposes. The presented tool, coupled with advancements in path delay fault coverage, shows that both the SIT and MIT functional models are very useful in ATPG for robust path delay faults for synthesized circuits.

REFERENCES

• 1: D. Bhattacharya , P. Agrawal , V. D. Agrawal, Delay fault test generation for scan/hold circuits using Boolean expressions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.159-164, June 08-12, 1992, Anaheim, California, United States
• 2: Prathima Agrawal , Debashis Bhattacharya , Vishwani D. Agrawal, Test Generation for Path Delay Faults Using Binary Decision Diagrams, IEEE Transactions on Computers, v.44 n.3, p.434-447, March 1995 [doi>10.1109/12.372035]
• 3: Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
• 4: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 5: CRAWFORD, J. M. AND AUTON, L. D. 1993. Experimental results on the cross-over point in satisfiability problems. In 11th National Conference on Artificial Intelligence (1993).
• 6: Jayant Deodhar, Color Counting and its Application to Path Delay Fault Coverage, Proceedings of the 2nd International Symposium on Quality Electronic Design, p.378, March 26-28, 2001
• 7: Rolf Drechsler, BiTeS: a BDD based test pattern generator for strong robust path delay faults, Proceedings of the conference on European design automation, p.322-327, September 19-23, 1994, Grenoble, France
• 8: Karl Fuchs , Michael Pabst , Torsten Rössel, RESIST: a recursive test pattern generation algorithm for path delay faults, Proceedings of the conference on European design automation, p.316-321, September 19-23, 1994, Grenoble, France
• 9: Gary D. Hachtel , Fabio Somenzi, Logic Synthesis and Verification Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 10: LARRABEE, T. 1992. Test generation using boolean satisfiability. IEEE Trans. Comput.-Aided Des. 11, 1 (Jan.), 4-15.
• 11: 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]
• 12: Irith Pomeranz , Sudhakar M. Reddy, On testing delay faults in macro-based combinational circuits, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.332-339, November 06-10, 1994, San Jose, California, United States
• 13: Irith Pomeranz , Sudhakar M. Reddy, Functional test generation for delay faults in combinational circuits, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.687-694, November 05-09, 1995, San Jose, California, United States
• 14: SOMENZI, F. ET AL. 1999. CUDD:CU decision diagram package. Public Software, http://vlsi. colorado.edu/ fabio/CUDD.
• 15: S. Tragoudas , M. Michael, ATPG tools for delay faults at the functional level, Proceedings of the conference on Design, automation and test in Europe, p.124-es, January 1999, Munich, Germany [doi>10.1145/307418.307578]
• 16: Bill Underwood , Wai-On Law , Sungho Kang , Haluk Konuk, Fastpath: A Path-Delay Test Generator for Standard Scan Designs, Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years, p.154-163, October 02-06, 1994

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  E. Data
  E.1 DATA STRUCTURES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Graph algorithms

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Performance, Reliability

Keywords:
Automatic test pattern generation, Binary Decision Diagrams, Boolean Satisfiability, delay testing, functional-level testing, path delay fault simulation (coverage), path delay fault testing, testing digital circuits