Fault Nodes in Implication Graph for Equivalence/Dominance Collapsing, and Identifying Untestable and Independent Faults

This paper presents a new fault node for implication graph that represents the Boolean detectability status of a fault in the circuit. An implication graph with fault nodes is termed functional fault graph (FFG) because such a graph stores both the functional information and the fault information of the circuit. By computing the transitive closure and graph condensation of the FFG of a circuit, we show that we can collapse faults, and identify untestable faults and independent fault pairs in the circuit. Compared to prior fault independent-based approaches for fault collapsing, our technique gives the best result by reducing the fault-set size by 66%. Additional advantages of our technique compared to previous techniques are: a) It can also identify independent fault pairs in the circuit, and b) It can be extended for other fault models and has a variety of applications. Our experiment with c7552 also found more than 268 K independent fault pairs. This work also introduces the first fault-independent polynomial-time approach for identifying untestable transition delay faults.