Double Phase Fault Collapsing with Linear Complexity in Digital Circuits

The paper presents a new structural fault collapsing method with linear algorithmic complexity to reduce the search space for test generation and fault diagnosis in digital circuits. The method is based on the two phase topology analysis of the circuit description. The first phase of fault collapsing is carried out on the gate level during superposition of Binary Decision Diagrams (BDD) of logic gates, which is then used for constructing a higher macro level compacted model of the circuit in the form of structurally synthesized BDDs (SSBDD). The fault collapsing can be regarded here as a side of effect of the model compaction. The second phase of the procedure is carried out already at the higher macro level by topological analysis of SSBDDs. Both procedures have linear complexity. Another contribution of the paper is the development, for the first time, of higher and lower bounds for the effect of structural fault collapsing. Experimental data show that the fault collapsing by the proposed method is more efficient than former structural fault collapsing methods and is well scalable for complex circuits.