SEQUENTIAL REDUNDANCY IDENTIFICATION


Abstract

This talk will address the problem of sequential redundancy identification. Previous solutions to this difficult problem are either based on incorrect theoretical results, or rely on unrealistic simplifying assumptions, or are applicable only to small circuits. Some surprising examples that contradict common expectations about sequential redundancy will also be presented. This talk will discuss the limitations of the existing definitions of sequential redundancy and introduce a new concept of c-cycle redundancy as a generalization of the conventional notion of sequential redundancy. Removing c-cycle redundancy allows circuit simplifications that are not possible with conventional redundancy.

Next, an efficient algorithm, FIRES, will be presented to identify c-cycle redundancies. FIRES does not have the limitations of existing methods. It does not assume the existence of a global reset nor does it require any state transition information. FIRES has provably polynomial-time complexity and is practical for large circuits. However, it is not guaranteed to identify all redundancies in a circuit. Experimental results on benchmark circuits show that FIRES identifies a large number of redundancies. In general, the redundant faults identified by FIRES are not easy targets for state-of-the-art sequential test generators.

If time permits, some recent extensions and work in progress will also be briefly discussed.

This work was done with D. Long and M. Abramovici (Bell Labs).



Relevant Papers

M. A. Iyer and M. Abramovici, "FIRE: A Fault-Independent Combinational Redundancy Identification Algorithm", IEEE Trans. on VLSI Systems, vol. 4, no. 2, pp. 295-301, June 1996.

M. A. Iyer, "On Redundancy and Untestability in Sequential Circuits" , Ph.D. Thesis, ECE Department, Illinois Institute of Technology, Chicago, IL - 60616, July 1995.

M. A. Iyer, D. E. Long, and M. Abramovici, "Surprises in Sequential Redundancy Identification" , Proc. European Design and Test Conference, pp. 88-94, March 1996.

M. A. Iyer, D. E. Long and M. Abramovici, "Identifying Sequential Redundancies Without Search" , Proc. 33rd. Design Automation Conf., pp. 457-462, June 1996.

Contact 
©2002-2018 U.C. Regents