Gate-level test generation for sequential circuits

ABSTRACT

This paper discusses the gate-level automatic test pattern generation (ATPG) methods and techniques for sequential circuits. The basic concepts, examples, advantages, and limitations of representative methods are reviewed in detail. The relationship between gate-level sequential circuit ATPG and the partial scan design is also discussed.

REFERENCES

• 1: Jacob A. Abraham , Vinod K. Agarwal, Test generation for digital systems, Fault-tolerant computing: theory and techniques; vol. 1, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 2: ABRAMOVICI, M., BREUER, M. A., AND FRIEDMAN, A. D. 1990. Digital Systems Testing and Testable Design. IEEE Computer Society Press, Los Alamitos, CA.
• 3: AGRAWAL, V. D. AND CHAKRADHAR, S.T. 1995. Combinational ATPG theorems for identifying untestable faults in sequential circuits. IEEE Trans. Comput. Aided Des. 14, 9, (Sept.), 1155-1160.
• 4: AGRAWAL, V. D. AND SETH, S. C. 1988. Tutorial--Test Generation for VLSI Chips. IEEE Computer Society Press, Ch. 3, Los Alamitos, CA.
• 5: BRAHME, D. AND ABRAHAM, g.A. 1984. Functional testing of microprocessors. IEEE Trans. Comput. C-33, 7, (July), 475-485.
• 6: BREUER, M.A. 1971. A random and an algorithmic technique for fault detection and test generation. IEEE Trans. Comput. C-20, (Nov.), 1366-1370.
• 7: BREUER, M.A. 1974. The effects of races, delays, and delay faults on test generation. IEEE Trans. Comput. C-23, 10, (Oct.), 1078-1092.
• 8: BREUER, M.A. 1983. Test generation models for busses and tri-state drivers. In Proceedings of the 1983 IEEE ATPG Workshop (March), 53-58.
• 9: BREUER, M. A. AND HARRISON, L.M. 1974. Procedures for eliminating static and dynamic hazards in test generation. IEEE Trans. Comput. C-23, 10 (Oct.), 1069-1078.
• 10: BREUER, M. A. AND FRIEDMAN, A.D. 1980. Functional level primitives in test generation. IEEE Trans. Comput., (March), 223-235.
• 11: BRGLEZ, F., BRYAN, D., AND KOZMINSKI, K. 1989. Combinational profiles of sequential benchmark circuits. In Proceedings of the 1989 IEEE International Symposium on Circuits and Systems (May), 1929-1934.
• 12: Srimat T. Chakradhar , Steven G. Rothweiler, Redundancy Removal and Test Generation for Circuits with Non-Boolean Primitives, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.12, April 30-May 03, 1995
• 13: CHAPPELL, S.G. 1974. LAMP: Automatic test generation for asynchronous digital circuits. Bell Syst. Tech. J., (Oct.), 1477-1503.
• 14: CHENG, K.-T. 1993. Redundancy removal for sequential circuits without reset states. IEEE Trans. CAD, (Jan.), 13-24.
• 15: Kwang-Ting Cheng , Vishwani D. Agrawal, Unified Methods for VLSI Simulation and Test Generation, Kluwer Academic Publishers, Norwell, MA, 1989
• 16: K.-T. Cheng , V. D. Agrawal, A Partial Scan Method for Sequential Circuits with Feedback, IEEE Transactions on Computers, v.39 n.4, p.544-548, April 1990 [doi>10.1109/12.54847]
• 17: CHENG, K.-T. AND JOU, J.-Y. 1992.A functional fault model for sequential circuits. IEEE Trans. CAD, (Sept.), 1065-1073.
• 18: Kwang-Ting Cheng , A. S. Krishnakumar, Automatic generation of functional vectors using the extended finite state machine model, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.57-79, Jan. 1996 [doi>10.1145/225871.225880]
• 19: CHENG, K.-T. AND MA, H-K. T. 1993. On the over-specification problem in sequential ATPG algorithms. IEEE Trans. Comput. Aided Des. (Oct.), 1599-1604.
• 20: CHENG, W.T. 1988. The BACK algorithm for sequential test generation. In Proceedings of the 1988 IEEE International Conference on Computer Design (Oct.), 66-69.
• 21: CHENG, W.T. 1989. Private communications, Aug.
• 22: CHO, H., HACHTEL, G. D., SOMENZI, F. 1993. Redundancy identification/removal and test generation for sequential circuits using implicit state enumeration. IEEE Trans. CAD (July), 935-945.
• 23: CHO, H., JEONG, S., SOMENZI, F., AND PIXLEY, C. 1993. Synchronizing sequences and symbolic traversal techniques in test generation. J. Electron. Testing, Theor. Appl. 4, 1, 19-31.
• 24: 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
• 25: DAHBURA, A. T., UYAR, M. U., AND YAU, C. W. 1989. An optimal test sequence for the JTAG/IEEE Pl149.1 test access port controller. In Proceedings of the IEEE International Test Conference (Aug.), 55-62.
• 26: Srinivas Devadas , Hi-Keung Y. Ma , A. Richard Newton, Redundancies and don't cares in sequential logic synthesis, Journal of Electronic Testing: Theory and Applications, v.1 n.1, p.15-30, Feb. 1990 [doi>10.1007/BF00134012]
• 27: FUJIWARA, H. AND SHIMONO, T. 1983. On the acceleration of test generation algorithms. IEEE Trans. Comput. C32, (Dec.), 1137-1144.
• 28: Abhijit Ghosh , Srinivas Devadas , A. Richard Newton, Sequential test generation at the register-transfer and logic levels, Proceedings of the 27th ACM/IEEE conference on Design automation, p.580-586, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123408]
• 29: GHOSH, A., DEVADAS, S., AND NEWTON, A. R. 1991. Test generation and verification for highly sequential circuits. IEEE Trans. Comput. Aided Des. (May), 652-667.
• 30: U. Glässer , H. T. Vierhaus, FOGBUSTER: an efficient algorithm for sequential test generation, Proceedings of the conference on European design automation, p.230-235, September 18-22, 1995, Brighton, England
• 31: GOEL, P. 1981. An implicit enumeration algorithm to generate tests for combinational circuits. IEEE Trans. Comput. C-30, (March), 215-222.
• 32: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 33: GOLDSTEIN, L. H. 1979. Controllability/observability analysis for digital circuits. IEEE Trans. Circuits Syst. CAS-26., (Sept.), 685-693.
• 34: R. Gupta , M. A. Breuer, The Ballast Methodology for Structured Partial Scan Design, IEEE Transactions on Computers, v.39 n.4, p.538-544, April 1990 [doi>10.1109/12.54846]
• 35: Mark C. Hansen , John P. Hayes, High-Level Test Generation Using Symbolic Scheduling, Proceedings of the IEEE International Test Conference on Driving Down the Cost of Test, p.586-595, October 21-25, 1995
• 36: HENNIE, F.C. 1964. Fault-detecting experiments for sequential circuits. In Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, (Nov.), 95-110.
• 37: HILL, F. g. AND HUEY, B. 1977. SCIRTSS: A search system for sequential circuit test sequences. IEEE Trans. Comput. C-26, (May), 490-502.
• 38: 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
• 39: 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
• 40: HSIEH, E.P. 1971. Checking experiments for sequential machines. IEEE Trans. Comput. C-20, (Oct.), 1152-1166.
• 41: 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
• 42: T. P. Kelsey , K. K. Saluja , S. Y. Lee, An Efficient Algorithm for Sequential Circuit Test Generation, IEEE Transactions on Computers, v.42 n.11, p.1361-1371, November 1993 [doi>10.1109/12.247839]
• 43: M. Keim , B. Becker , B. Stenner, On the (non-)resetability of synchronous sequential circuits, Proceedings of the 14th IEEE VLSI Test Symposium (VTS '96), p.240, April 28-May 01, 1996
• 44: 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]
• 45: KUBO, H. 1968. A procedure for generating test sequences to detect sequential circuit failures. NEC Res. & Dev., (Oct. 1968), 69-78.
• 46: LEE, D. H. AND REDDY, S.M. 1991. A new test generation method for sequential circuits. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD-91), (Nov.), 446-449.
• 47: LEE, J. AND PATEL, J.H. 1991. A signal-driven discrete relaxation technique for architectural level test generation. In Proceedings of the IEEE International Conference on Computer-Aided Design, (Nov.), 458-461.
• 48: LEE, J. AND PATEL, J.H. 1994. Architectural level test generation for microprocessors. IEEE Trans. CAD, 13, 10 (Oct.), 1288-1300.
• 49: MA, H-K. T., DEVADAS, S., NEWTON, A. R., AND SANGIOVANNI-VINCENTELLI, A. 1988. Test generation for sequential circuit. IEEE Trans. Comput. Aided Des., (Oct.), 1081-1093.
• 50: 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
• 51: Ralph A. Marlett, EBT: A comprehensive test generation technique for highly sequential circuits, Proceedings of the 15th conference on Design automation, p.335-339, June 19-21, 1978, Las Vegas, Nevada, United States
• 52: A Miczo, Digital logic testing and simulation, Harper & Row Publishers, Inc., New York, NY, 1985
• 53: MUTH, P. 1976. A nine-valued circuit model for test generation. IEEE Trans. Comput. C-25, (June), 630-636.
• 54: NIERMANN, T. M., CHENG, W.-T., AND PATEL, J.H. 1992. PROOFS: A fast, memory-efficient sequential circuit fault simulator. IEEE Trans. CAD 11, 2, (Feb.), 198-207.
• 55: 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
• 56: NITTA, S., KAWAMURA, M., AND HIRABAYASHI, K. 1985. Test generation by activation and defect-drive (TEGAD). Integration 3, 12 (Dec.).
• 57: Takuji Ogihara , Shinichi Murai , Yuzo Takamatsu , Kozo Kinoshita , Hideo Fujiwara, Test generation for scan design circuits with tri-state modules and bidirectional terminals, Proceedings of the 20th conference on Design automation, p.71-78, June 27-29, 1983, Miami Beach, Florida, United States
• 58: Carl Pixley, Introduction to a Computational Theory and Implementation of Sequential Hardware Equivalence, Proceedings of the 2nd International Workshop on Computer Aided Verification, p.54-64, June 18-21, 1990
• 59: PIXLEY, C. AND BEIHL, G. 1991. Calculating resettability and reset sequences. In Proceedings of the IEEE International Conference on Aided Design, (Nov.), 376-379.
• 60: PIXLEY, C., JEONG, S., AND HACHTEL, a. 1994. Exact calculation of synchronous sequences based on binary decision diagrams. IEEE Trans. CAD, 13, 8, (Aug.), 1024-1034.
• 61: Irith Pomeranz , Sudhakar M. Reddy, On achieving a complete fault coverage for sequential machines using the transition fault model, Proceedings of the 28th conference on ACM/IEEE design automation, p.341-346, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127691]
• 62: Irith Pomeranz , Sudhakar M. Reddy, The Multiple Observation Time Test Strategy, IEEE Transactions on Computers, v.41 n.5, p.627-637, May 1992 [doi>10.1109/12.142689]
• 63: I. Pomeranz , S. M. Reddy, Classification of Faults in Synchronous Sequential Circuits, IEEE Transactions on Computers, v.42 n.9, p.1066-1077, September 1993 [doi>10.1109/12.241596]
• 64: POMERANZ, I. AND REDDY, S.M. 1994. On identifying untestable and redundant faults in synchronous sequential circuits. In Proceedings of the 12th IEEE VLSI Test Symposium, (April), 8-14.
• 65: 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
• 66: 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
• 67: PUTZOLU, G. R. AND ROTH, J.P. 1971. A heuristic algorithm for the testing of asynchronous circuits. IEEE Trans. Comput. C-20, (June), 639-647.
• 68: June-Kyung Rho , Fabio Somenzi , Carl Pixley, Minimum length synchronizing sequences of finite state machine, Proceedings of the 30th international conference on Design automation, p.463-468, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164978]
• 69: ROTH, J.P. 1966. Diagnosis of automata failures: A calculus and a method. IBM J. Res. Dev. 10, (July), 278-291.
• 70: RUDNICK, E. M., HOLM, J. G., SAAB, D. G., AND PATEL, J. H. 1994. Application of simple genetic algorithms to sequential circuit test generation. In Proceedings of the European Design and Test Conference, (March), 40-45.
• 71: 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]
• 72: 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]
• 73: 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
• 74: Daniel G. Saab , Youssef G. Saab , Jacob A. Abraham, Iterative [simulation-based genetics + deterministic techniques]= complete ATPG0, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.40-43, November 06-10, 1994, San Jose, California, United States
• 75: Krishan Sabnani , Anton Dahbura, A protocol test generation procedure, Computer Networks and ISDN Systems, v.15 n.4, p.285-297, Sept. 1988 [doi>10.1016/0169-7552(88)90064-5]
• 76: SCHNURMANN, H. D., LINDBLOOM, E., AND CARPENTER, R. G. 1975. The weigthed random test-pattern generator. IEEE Trans. Comput. C-24, 695-700.
• 77: SCHULZ, M. H. AND AUTH, E. 1988. Advanced automatic test pattern generation and redundancy identification techniques. In Proceedings of the 18th IEEE International Symposium on Fault-Tolerant Computing, (June), 30-35.
• 78: SCHULZ, M. H. AND AUTH, E. 1989. ESSENTIAL: An efficient self-learning test pattern generation algorithm for sequential circuits. In Proceedings of the International Test Conference, (Aug.), 28-37.
• 79: SCHULZ, M. H., TRISCHLER, E., AND SARFERT, T. M. 1988. SOCRATES: A highly efficient automatic test pattern generation system. IEEE Trans. CAD, (Jan.), 126-137.
• 80: SESHU, S. 1965. On an improved diagnosis program. IEEE Trans. Electron. Comput. EC-14, 2, (Feb.), 76-79.
• 81: SESHU, S. AND FREEMAN, D.N. 1962. The diagnosis of asynchronous sequential switching systems. IRE Trans. Electron. Comput. EC-11, (Aug.), 459-465.
• 82: Thomas J. Snethen, Simulator-oriented fault test generator, Proceedings of the 14th conference on Design automation, p.88-93, January 1977
• 83: SRINIVAS, M. AND PATNAIK, L.M. 1993. A simulation-based test generation scheme using genetic algorithms. In Proceedings of the IEEE International Conference VLSI Design, (Jan.), IEEE Computer Science Press, 132-135.
• 84: THATTE, S. M. AND ABRAHAM, g.A. 1980. Test generation for microprocessors. IEEE Trans. Comput., C-29, 6, (June), 429-441.
• 85: THOMAS, g.g. 1971. Automated diagnostic test program for digital networks. Comput. Des., (Aug.), 63-67.
• 86: Jalal A. Wehbeh , Daniel G. Saab, On the Initialization of Sequential Circuits, Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years, p.233-239, October 02-06, 1994

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Reliability, Verification

Keywords:
IC testing, automatic test generation, sequential circuit test generation, testing