EST: The new frontier in automatic test-pattern generation

ABSTRACT

We present a new algorithm, EST, that accelerates any combinatorial circuit Automatic Test-Pattern Generation algorithm. EST detects equivalent search states, which are saved for all faults during ATPG. The search space is reduced by using Binary Decision Diagram fragments to detect previously-encountered search states (possibly from prior faults). Search terminates earlier than before. Redundant fault analysis further accelerates ATPG. ATPG is accelerated 1347 times for hard-to-test faults in the ISCAS '85 benchmarks.

REFERENCES

• 1: S.B. Akers. Binary Decision Diagrams. IEEE Trans. on Computers, C-27(6):509-516, June 1978.
• 2: F. Brglez and H. Fujiwara. A Neutral Netlist of 10 Combinational Benchmark Circuits. In Proc. of IS- CAS; Special Session on ATPG and Fault Simulation, pages 151-158. IEEE, June 1985.
• 3: K. Cho , R. E. Bryant, Test pattern generation for sequential MOS circuits by symbolic fault simulation, Proceedings of the 26th ACM/IEEE conference on Design automation, p.418-423, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74452]
• 4: H. Fujiwara and T. Shimono. On the Acceleration of Test Generation Algorithms. In Proc. of the i3th FTCS, pages 98-105. IEEE, June 1983.
• 5: Rhonda Kay Gaede , Don E. Ross , M. Ray Mercer , Kenneth M. Butler, CATAPULT: concurrent automatic testing allowing parallelization and using limited topology, Proceedings of the 25th ACM/IEEE conference on Design automation, p.597-600, June 12-15, 1988, Atlantic City, New Jersey, United States
• 6: 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]
• 7: T. Larrabee. Efficient Generation of Test Patterns Using Boolean Difference. In Proc. of the Int. Test Conf., pages 795-801. IEEE, August 1989.
• 8: P.Goel. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits. IEEE Trans. on Computers, C-30(3):215-222, March 1981.
• 9: J.P. Roth, W.G. Bouricius, and P.I~L. Schneider. Programmed Algorithms to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits. IEEE Trans. on Electronic Computers, t'}G-16(10):567-580, Oct. 1967.
• 10: M. Schulz and E. Auth. Improved :Deterministic Test Pattern Generation with Applications to Redundancy Identification. IEEE Trans. on CAD, 8(7):811-816, July 1989.
• 11: R. S. Wei and A. Sangiovanni-VincenteUl. PROTEUS: A Logic Verification System for Combinational Circuits. In Proc. of the ITC, pages 350-359. IEEE, Oct. 1986.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**
          Subjects: Test generation**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design