Advanced fault collapsing [logic circuits testing]

The partitioning of faults into equivalence classes so that only one representative fault per class must be explicitly considered in fault simulation and test generation, called fault collapsing, is addressed. Two types of equivalence, which are relevant to the work reported, are summarized. New theorems on fault equivalence and dominance, forming the basis of an algorithm that collapses all the structurally equivalent faults in a circuit, plus many of the functionally equivalent faults, are presented. Application of the algorithm to a set of benchmark circuits establishes that identification of functionally equivalent faults is feasible, and that, in some cases, they are a large fraction of the faults in a circuit. The collapsing algorithm applies not only to combinational designs but to synchronous sequential circuits as well