Scalable Algorithm for Structural Fault Collapsing in Digital Circuits

The paper presents a new algorithm for structural fault collapsing to reduce search space for test generation, speed up fault simulation and make fault diagnosis easier in digital circuits. The proposed method is based on hierarchical topology analysis of the circuit description. First, the gate-level circuit will be converted into a macro-level network of fan-out-free regions each of them represented by a BDD. This conversion procedure represents the first step of fault collapsing, resulting in a compressed BDD model for representing the remaining set of fault sites. The paper presents an algorithm which implements a complementary step for further fault collapsing, and is carried out at the macro level by topological reasoning of equivalence and dominance relations between the nodes of BDDs. The algorithm has linear complexity and is implemented as a scalable fault collapsing procedure. We introduce higher and lower bounds for structural fault collapsing and provide statistics of distribution of fault collapsing results for a broad set of benchmark circuits. Experimental research has demonstrated better results for structural fault collapsing compared with state-of-the-art.