Dynamic state traversal for sequential circuit test generation

ABSTRACT

A new method for state justification is proposed for sequential circuit test generation. The linear list of states dynamically obtained during the derivation of test vectors is used to guide the search during state justification. State-transfer sequences that drive the circuit from the current state to the target state may already be known. Otherwise, genetic engineering of existing state-transfer sequences is required. In both cases, genetic-algorithm-based techniques are used to generate valid state justification sequences for the circuit in the presence of the target fault. This approach achieves extremely high fault coverages, and thus outperforms previous deterministic and simulation-based techniques.

REFERENCES

• 1: ABRAMOVICI, M., BREUER, M., AND FRIEDMAN, A. D. 1990. Digital Systems Testing and Testable Design. Computer Science Press, Inc., New York, NY.
• 2: ADVANCED MICRO DEVICES. 1978. The AM2910, a complete 12-bit microprogram sequence controller. In AMD Data Book, AMD Inc
• 3: BRGLEZ, F., BRYANT, D., AND KOZMINSKI, K. 1989. Combinational profiles of sequential benchmark circuits. In Proceedings of the IEEE International Symposium on Circuits and Systems (Portland, OR, May 1989), IEEE Press, Piscataway, NJ, 1929-1934.
• 4: CHO, H., JEONG, S. W., SOMENZI, F., AND PIXLEY, C. 1993. Synchronizing sequences and symbolic traversal techniques in test generation. J. Electron. Test. 4, 1 (Feb.), 19-31.
• 5: F. Corno , P. Prinetto , M. Rebaudengo , M. Sonza Reorda , R. Mosca, Advanced Techniques for GA-based sequential ATPGs, Proceedings of the 1996 European conference on Design and Test, p.375, March 11-14, 1996
• 6: GHOSH, A., DEVADAS, S., AND NEWTON, A. R. 1989. Test generation for highly sequential circuits. In Proceedings of the International Conference on Computer-Aided Design (ICCAD, Nov. 1989), 362-365.
• 7: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 8: M. S. Hsiao , E. M. Rudnick , J. H. Patel, Automatic test generation using genetically-engineered distinguishing sequences, Proceedings of the 14th IEEE VLSI Test Symposium (VTS '96), p.216, April 28-May 01, 1996
• 9: Michael S. Hsiao , Elizabeth M. Rudnick , Janak H. Patel, Alternating Strategies for Sequential Circuit ATPG, Proceedings of the 1996 European conference on Design and Test, p.368, March 11-14, 1996
• 10: T. E. Marchok , A. El-Maleh , W. Maly , J. Rajski, Complexity of sequential ATPG, Proceedings of the 1995 European conference on Design and Test, p.252, March 06-09, 1995
• 11: NIERMANN, T. M. AND PATEL, g. H. 1994. Method for automatically generating test vectors for digital integrated circuits. U.S. Patent no. 5,377.
• 12: 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
• 13: Jaehong Park , Chanhee Oh , M. R. Mercer, Improved sequential ATPG using functional observation information and new justification methods, Proceedings of the 1995 European conference on Design and Test, p.262, March 06-09, 1995
• 14: Irith Pomeranz , Sudhakar M. Reddy, LOCSTEP: A Logic Simulation-Based Test Generation Procedure, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.110, June 27-30, 1995
• 15: I. Pomeranz , S. M. Reddy, Application of Homing Sequences to Synchronous Sequential Circuit Testing, IEEE Transactions on Computers, v.43 n.5, p.569-580, May 1994 [doi>10.1109/12.280804]
• 16: 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
• 17: RUDNICK, E. M. AND PATEL, J. H. 1996. State justification using genetic algorithms in sequential circuit test generation. Tech. Rep. CRHC-96-01/UILU-ENG-96-2201. University of Illinois at Urbana-Champaign, Champaign, IL.
• 18: Elizabeth M. Rudnick , Janak H. Patel, Combining deterministic and genetic approaches for sequential circuit test generation, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.183-188, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217527]
• 19: 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]
• 20: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  J. Computer Applications

General Terms:
Algorithms, Reliability, Verification

Keywords:
automatic test pattern generation (ATPG), finite-state-machine traversal, genetic algorithms, sequential circuits, simulation-based, testing