Sequential redundancy identification using recursive learning

ABSTRACT

A sequential redundancy identification procedure is presented. Based on uncontrollability analysis and recursive learning techniques, this procedure identifies c-cycle redundancies in large circuits, without simplifying assumptions or state transition information. The proposed procedure can identify redundant faults which require conflicting assignments on multiple lines. In this sense, it is a generalization of FIRES, a state-of-the-art redundancy identification algorithm. A modification of the proposed procedure is also presented for identifying untestable faults. Experimental results on ISCAS benchmarks demonstrate that these two procedures can efficiently identify a large portion of c-cycle redundant and untestable faults.

REFERENCES

• 1: 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
• 2: 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
• 3: 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
• 4: Kwang-Ting Cheng, On removing redundancy in sequential circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.164-169, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127655]
• 5: I.Pomeranz and S.M.Reddy, "On Identifying Untestable and Redundant Faults In Synchronous Sequential Circuits," 12 th IEEE VLSI Test Symposium, pp.8-14, April 1994.
• 6: V. Agrawal and S. Chakradhar, "Combinational ATPG Theorems for Identifying Untestable Faults in Sequential Circuits," Proc. of Euro. Test Conf., Apr. 1993.
• 7: H.Cho, G.D.Hachtel and F.Somenzi, "Redundancy Identification/Removal and Test Generation for Sequential Circuits Using Implicit State Enumeration," IEEE Trans. on CAD, vol.12,no.7, pp.935-945, July 1993.
• 8: Mahesh Anantharaman Iyer, On redundancy and untestability in sequential circuits, Illinois Institute of Technology, Chicago, IL, 1996
• 9: 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
• 10: M. Abramovici and M.A. Iyer, "Low-Cost Redundancy Identification for Combinational Circuits," 7th. Intn' I. Conf. on VLSI Design, pp.315-318, Jan. 1994.
• 11: W.Kunz and D.K.Pradhan, "Recursive Learning: A New Implication Technique for Efficient Solution to CAD Problems - Test, Verification, and Optimization," IEEE Trans. on CAD, vol.13,no.9, pp.1143-1158, Sept. 1994.
• 12: D.K.Pradhan and W.Kunz, "Method For Circuit Verification and Multi-Level Circuit Optimization Based On Structural Implications," U.S. Patent, No. 5526514, June 11, 1996.
• 13: Wolfgang Kunz, HANNIBAL: an efficient tool for logic verification based on recursive learning, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.538-543, November 07-11, 1993, Santa Clara, California, United States
• 14: 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]
• 15: 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]
• 16: R. Mukherjee, J. Jain and D. K. Pradhan "Functional Learning: A New Approach to Learning in Digital Circuits",Proc. IEEE VLSI Test Symp., pp 122-127, April 1994.
• 17: A. Dargelas, C. Gauthron, Y. Bertrand, "MOSA, A Multiple Strategy Oriented Sequential ATPG", 1 st European Test Workshop, June 1996.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation, Reliability

Keywords:
FIRES, ISCAS benchmarks, c-cycle redundancies, c-cycle redundant faults, logic CAD, recursive learning, redundancy identification algorithm, sequential redundancy identification, state transition information, uncontrollability analysis, untestable faults