Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We propose a general methodology to speed up the test generation process for circuits with high-level primitives. Our search procedure is a variation of depth first search that tries to fully exploit the capabilities of a computer to execute complex arithmetic and logical operations. We present techniques for signal value justification, and fault propagation, which are used by our algorithm. We have implemented a dependency-directed backtracking method to speed up our algorithm. This methodology has been applied to six circuits and the results are found to be very encouraging.

REFERENCES

• 1: Ibarra, O. H. and Sahni, S., "Polynomially Complete Fault Detection Problems," Tran. Computers, vol. C-24, pp. 242-249, March 1975.
• 2: Roth, J. P., "Diagnosis of Automata Failures: A Calculus and a Method," IBM Journal of Res. and Develop., vol. 10, pp. 278-291, Jul. 1966.
• 3: Goel, P., "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits," IEEE Trans. on Computers, vol. e-30, pp. 215-222, March 1981.
• 4: Fujiwara, H. and Shimorao, T., "'On the Acceleration of Test Generation Algorithms," Proc. of the 13th lntl Syrup. on Fault-Tolerant Computing., pp. 98-105, 1983.
• 5: Thatte, S. M. and Abraham, J. A., "Test Generation for Microprocessors," IEEE Tran Comp., vol. c-29, pp. 429- 441, Jun. 1980.
• 6: Brahme, D. and Abraham, J. A., "Functional Testing of Microprocessors," IEEE Trans. on Computers, vol. c-33, pp. 475-485, June 1984.
• 7: Lin, T. and Su, S, Y, H., "The S-Algorithm: A Promising Solution for Systematic Functional Test Generation," IEEE Tran. on CAD, vol. CAD-4, pp. 250-263, July 1985.
• 8: C. Bellon , R. Velazco, Taking into account asynchronous signals in functional test of complex circuits, Proceedings of the 21st conference on Design automation, p.490-496, June 25-27, 1984, Albuquerque, New Mexico, United States
• 9: Annaratone, M. A. and Sami, M. G., "An Approach to Functional Testing of Microprocessors," 12th Int. Conf. on Fault-Tolerant Computing Systems, pp. 158-164, 1982.
• 10: Shen L. and Su S. Y. H., "A Functional Testing Method for Microprocessors," 14th Ira. Conf. on Fault-Tolerant Computing Systems, pp. 212-218, 1984.
• 11: Sridhar, T. and Hayes, J. P., "Testing Bit-sliced Microprocessors,'" Proc. of 9th int. Conf. on Fault- Tolerant Computing, pp. 211-218, June 1979.
• 12: Robach, C. and Saucier, G., "Microprocessor Functional Testing," Proc. of Test Conference, 1980.
• 13: Breuer, M. A. and Friedman, A. D., "Functional Level Primitives in Test Generation," IEEE Trans. Comp., vol. c-29, pp. 223-224, March 1980.
• 14: Levendel, Y. H. and Menon, P. R., "Test Generation Algorithms for Computer Hardware Description Languages," IEEE Trans. Comp., vol. e-31, pp. 577-588, July 1982.
• 15: Naraln, P., A Hierarchical Approach to Test Generation Using Behavioral Descriptions, Amherst, Massachusetts: M. S. Thesis, Univ. of Massaehusetts, Feb. 1989.
• 16: Murray, B. T. and Hayes, J. P., "Hierarchical Test Generation Using Precomputed Tests for Modules," Proc. of International Test Conference, pp. 221-229, Sept. 1988.
• 17: Murakami, M., Shiraki, N., and Hirakawa, K., "Logie Verification and Test Generation for VLSI Circuits," Intl. Test Conf., pp. 467-472, 1980.
• 18: Brglez, F. and Fujiwara, H,, "Neutral Netlist of Ten Combinational Benehrnark Circuits and a Target Translator in FORTRAN," Special session on ATPG and fault simulation, Proc. of IEEE Intl. Syrup. on Circuits and Systems, June 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

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

General Terms:
Algorithms, Design