A new algorithm for global fault collapsing into equivalence and dominance sets

Nodes in a dominance graph represent faults of a circuit. A directed edge from node f_i to node f_j means that fault f_j dominates f_i. The equivalence of faults f_i and f_j is indicated by the presence of simultaneous edges f_i → f_j and f_j → f_i. When local dominance and equivalence relations are included in this graph, its transitive closure provides the collapsed fault sets. Pre-collapsed fault sets of standard cells and other logic blocks can be stored in a graph library for hierarchical fault collapsing. Examples show how more compact fault sets are obtained by using functional equivalences that can be found by analysis of small cells. Benchmark circuits c432 and c499 are used to illustrate the use of functional fault collapsing within their exclusive-OR cells.