Fault equivalence and dominance-based fault diagnosis

Fault diagnosis is performed to locate and identify physical failures in a defective integrated circuit. In this thesis, solutions to several problems in fault diagnosis are presented. First, techniques for identifying indistinguishable or functionally equivalent faults in combinational circuits are described. The techniques are based on implication of faulty values; and evaluation of faulty functions in cones of dominator gates of fault pairs. This is enhanced by utilizing circuit redundancy information. Static and dynamic methods are developed to exploit relations among inputs of dominator cones and further speed up the identification of equivalent fault pairs. Improvements compared to previous approaches are achieved in both the number of equivalent fault pairs identified and the time to prove equivalence. Second, theorems are introduced to identify indistinguishable fault pairs in synchronous sequential circuits using an iterative logic array of limited length. A theoretical framework for identification of sequential indistinguishability is developed utilizing information about reachable states, valid states and strongly connected components. Finally, an integrated approach for diagnosis is developed to accurately locate manufacturing defects. A fault model is used to encompass the behavior of a large variety of fault models and dominance relations among faults are used to reduce the list of candidate defect sites. Diagnosis techniques based on this fault model are described that accurately locate bridging defects and transition defects