Hierarchical Fault Collapsing for Logic Circuits

Abstract

The process of grouping stuck-at faults into equivalence or dominance classes and then selecting one representative for each class is known as fault collapsing. There have been several techniques to collapse the faults structurally and functionally. We present a new method that determines all functional dominances between the faults of a circuit using redundancy identification and then collapses faults. This procedure produces the smallest possible equivalence and dominance collapsed sets. Our method is more efficient than other functional collapsing algorithms, but is still expensive in CPU time. Therefore, we recommend its application only to smaller sub-circuits that may be embedded in larger circuits.

Another contribution of this research is a thorough examination of the fault equivalence and dominance relations for multiple output circuits. The conventional definition for equivalence says that “two faults are equivalent if and only if the corresponding faulty circuits have identical output functions.” This definition is extended for multiple output circuits as “two faults of a Boolean circuit are called diagnostically equivalent if and only if the functions of the two faulty circuits are identical at each output.” Alternatively, “if all tests that detect a fault also detect another fault, not necessarily at the same output, then the two faults are called detection equivalent.” The definitions for fault dominance follow on similar lines.

A program implements our novel algorithm based on redundancy identification to find the complete equivalence and dominance collapsed sets using diagnostic and detection collapsing definitions. When applied to a 4-bit ALU it collapses the total fault set of 502 faults to 253 and 155, respectively, according to diagnostic equivalence and dominance. The collapsed sets have 234 and 92 faults, respectively, for detection equivalence and dominance. In comparison, the conventional structural equivalence and dominance collapsing results in 301 and 248 faults, respectively.

Functional fault collapsing, using the proposed algorithm, is done for standard cells and other logic blocks and the collapse data is saved as library information. Using the redundancy-based fault collapsing for a full adder library cell, we hierarchically collapse faults in a 64-bit adder to sets of 1538 equivalence and 768 dominance collapsed faults. In comparison, a flattened 64-bit adder circuit collapses into 2306 and 1794 equivalence and dominance collapsed sets, respectively. It is also shown that hierarchical collapsing results in an order of magnitude reduction in the CPU time for very large circuits. A flattened 1024-bit adder requires 39.9 seconds for structural collapsing while the same circuit, if described hierarchically as an interconnect of 1024 full adders, takes only 3.60 seconds. The 1024-bit adder can also be hierarchically built using four 256-bit adders, which are built using four 64-bit adder, and so on and this circuit takes only 2.31 seconds to collapse faults. In conclusion, hierarchical collapsing saves CPU time and potentially provides more collapsing.