On redundancy and untestability in sequential circuits
Mahesh A. Iyer · 1996
This research addresses the problems of identifying redundancy and untestability in synchronous sequential circuits. The widespread misconceptions about redundancy are revealed and examples are provided to illustrate the differences between untestability and redundancy in sequential circuits. Existing techniques to identify sequential redundancy are discussed, and it is shown that some of these methods are based on incorrect theoretical results. Specifically, it is shown that untestable faults in balanced pipeline circuits and in circuits with fault-free global reset mechanisms are not necessarily redundant, and that a constant function does not always indicate a redundancy. It is also shown that adding a global reset mechanism or retiming synchronous circuitry may introduce redundancies. The first efficient algorithm (FIRES) to identify sequential redundancy, that is practical for large circuits is presented. No global reset is assumed and no state transition information is required. The concept of a c-cycle redundancy as a generalization of the conventional notion of sequential redundancy is introduced. FIRES is based on the result that a fault which requires a conflict as a necessary condition for its detection is c-cycle redundant. FIRES has provably polynomial-time complexity, but is not guaranteed to identify all redundancies in a circuit. Experimental results on benchmark circuits indicate that FIRES finds a large number of redundancies. When a sequential test generator targets a sequentially redundant fault, the most it can do is prove it as untestable. It is shown that, in general, the redundant faults identified by FIRES are not easy targets for state-of-the-art sequential test generators. Another algorithm, FUNI, to find untestable faults using illegal states is also introduced. FUNI uses the illegal states identified by a recently proposed algorithm, FILL, and finds untestable faults for which these illegal states are necessary for detection. FUNI identifies untestable faults without using the exhaustive search involved in ATG. 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.