FILL and FUNI: algorithms to identify illegal states and sequentially untestable faults

ABSTRACT

In this paper, we first present an algorithm (FILL) to efficiently identify a large subset of illegal states in synchronous sequential circuits, without assuming a global reset mechanism. A second algorithm, FUNI, finds sequentially untestable faults whose detection requires some of the illegal states computed by FILL. Although based on binary decision diagrams (BDDs), FILL is able to process large circuits by using a new functional partitioning procedure. The incremental building of the set of illegal states guarantees that FILL will always obtain at least a partial solution. FUNI is a direct method that identifies untestable faults without using the exhaustive search involved in automatic test generation (ATG). Experimental results show that FUNI finds a large number of untestable faults up to several orders of magnitude faster than an ATG algorithm that targeted the faults identified by FUNI. Also, many untestable faults identified by FUNI were aborted by the test generator.

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: Miron Abramovici , Mahesh A. Iyer, One-Pass Redundancy Identification and Removal, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.807-815, September 20-24, 1992
• 3: Miron Abramovici , James J. Kulikowski , Rabindra K. Roy, The Best Flip-Flops to Scan, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.166-173, October 26-30, 1991
• 4: ABRAMOVICI, M., KULIKOWSKI, J. J., MENON, P. R., AND MILLER, D. T. 1986. SMART and FAST: Test generation for VLSI scan-design circuits. IEEE Des. Test (Aug.).
• 5: ABRAMOVICI, M. AND BREUER, M.A. 1979. On redundancy and fault detection in sequential circuits. IEEE Trans. Comput. C-28, 11 (Nov.), 864-865.
• 6: AGRAWAL, V. D. AND CHAKRADHAR, S. T. 1993. Combinational ATPG theorems for identifying untestable faults in sequential circuits. In Proceedings of the on IEEE European Test Conference (Apr. 1993), IEEE Computer Society Press, Los Alamitos, CA, 249-253.
• 7: 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.
• 8: BREUER, M.A. 1978. New concepts in automated testing of digital circuits. In Proceedings of the EEC Symposium on CAD of Digital Electronic Circuits and Systems (Nov.), North-Holland Publishing Co., Amsterdam, The Netherlands, 69-72.
• 9: 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.
• 10: 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]
• 11: CHAKRABORTY, T. J., DAVIDSON, S., AND BENCIVENGA, B. 1991. GENTEST: The architecture of sequential circuit test generator. In Proceedings of the IEEE Conference on Custom Integrated Circuits (May 1991), IEEE Computer Society Press, Los Alamitos, CA.
• 12: CHAKRADHAR, S. T., AGRAWAL, V. D., AND ROTHWEILER, S. G. 1993. A transitive closure algorithm for test generation. IEEE Trans. Comput.-Aided Des. 12, 7 (July), 1015-1028.
• 13: Hyunwoo Cho , Gary D. Hachtel , Enrico Macii , Bernard Plessier , Fabio Somenzi, Algorithms for approximate FSM traversal, Proceedings of the 30th international conference on Design automation, p.25-30, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164555]
• 14: CHO, H., HACHTEL, G. D., AND SOMENZI, F. 1993b. Redundancy identification/removal and test generation for sequential circuits using implicit state enumeration. IEEE Trans. Comput.- Aided Des. 12, 7 (July), 935-945.
• 15: CHO, H., JEONG, S. W., SOMENZI, F., AND PIXLEY, C. 1993c. Synchronizing sequences and symbolic traversal techniques in test generation. J. Electron. Test. 4, 1 (Feb.), 19-31.
• 16: COUDERT, O. AND MADRE, g. C. 1991. Symbolic computation of the valid states of a sequential machine: Algorithms and discussion. In Proceedings of the International Workshop on Formal Methods in VLSI Design (Jan. 1991),
• 17: O. Coudert , C. Berthet , J. C. Madre, Verification of synchronous sequential machines based on symbolic execution, Proceedings of the international workshop on Automatic verification methods for finite state systems, p.365-373, February 1990, Grenoble, France
• 18: IYER, M.A. 1991. One-pass redundancy identification and removal in combinational circuits. M.S. Thesis. Illinois Institute of Technology, Chicago, IL.
• 19: Mahesh Anantharaman Iyer, On redundancy and untestability in sequential circuits, Illinois Institute of Technology, Chicago, IL, 1996
• 20: 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
• 21: IYER, M. A. AND ABRAMOVICI, M. 1994b. Low-cost redundancy identification for combinational circuits. In Proceedings of the 7th International Conference on VLSI Design (India, Jan. 1994), 315-318.
• 22: Mahesh A. Iyer , Miron Abramovici, FIRE: a fault-independent combinational redundancy identification algorithm, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.2, p.295-301, June 1996 [doi>10.1109/92.502203]
• 23: Mahesh A. Iyer , David E. Long , Miron Abramovici, Surprises in Sequential Redundancy Identification, Proceedings of the 1996 European conference on Design and Test, p.88, March 11-14, 1996
• 24: Mahesh A. Iyer , David E. Long , Miron Abramovici, Identifying sequential redundancies without search, Proceedings of the 33rd annual conference on Design automation, p.457-462, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240605]
• 25: LIANG, H.-C., LEE, C. L., AND CHEN, J. E. 1994. A sequential redundant fault identification scheme and its application to test generation. In Proceedings of the IEEE Asian Symposium on Test, IEEE Computer Society Press, Los Alamitos, CA, 57-62.
• 26: Hsing-chung Liang , Chung Len Lee , Jwu E. Chen, Identifying Untestable Faults in Sequential Circuits, IEEE Design & Test, v.12 n.3, p.14-23, September 1995 [doi>10.1109/MDT.1995.466367]
• 27: LIN, B. AND TOUATI, H.J. 1990. Don't care minimization of multi-level sequential logic networks. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'90, Nov.), IEEE Computer Society Press, Los Alamitos, CA, 414-417.
• 28: D. E. Long , M. A. Iyer , M. Abramovici, Identifying sequentially untestable faults using illegal states, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.4, April 30-May 03, 1995
• 29: 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
• 30: 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]
• 31: 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]
• 32: POMERANZ, I. AND REDDY, S. M. 1994. On identifying undetectable and redundant faults in synchronous sequential circuits. In Proceedings of the on 12th Annual IEEE VLSI Test Symposium (Apr.), IEEE Computer Society Press, Los Alamitos, CA, 8-14.
• 33: Shaz Qadeer , Robert K. Brayton , Vigyan Singhal, Latch Redundancy Removal Without Global Reset, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.432-439, October 07-09, 1996
• 34: RUTMAN, R.A. 1972. Fault detection test generation for sequential logic by heuristic tree search. IEEE Computer Group Repository, Paper No. R-72-187.
• 35: TOUATI, H. J., SAVOJ, H., LIN, B., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1990. Implicit state enumeration of finite state machines using BDDs. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'90, Nov.), IEEE Computer Society Press, Los Alamitos, CA, 130-133.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation; Switching theory; Verification
  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
      B.8.2 Performance Analysis and Design Aids

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics; Engineering
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Theory, Verification

Keywords:
automatic test generation, illegal states, sequential circuits, untestable faults