Efficient location-based logic diagnosis of digital circuits
Holst, Stefan · OPUS Publication Server of the University of Stuttgart (University of Stuttgart) · 2012
Logic diagnosis is the task of finding defects within a random logic circuit based on its faulty behavior. Fast and accurate algorithms for logic diagnosis are an integral part of modern chip development. Classic diagnosis algorithms were often based on fault models which contain a priori assumptions on the behavior of defects. In recent technologies, fault model based approaches become ineffective because defect mechanisms get more and more complex. So research has started on location-based diagnosis algorithms, which use more general fault models or no model at all and report defective substructures directly. The generality however may also have a negative effect on the accuracy of the diagnosis results. With the lack of a fault model, a diagnosis algorithm has less knowledge on possible or likely malfunctions of a circuit. This increases the search space dramatically and may even lead to defect candidates which are physically impossible. Reducing a priori assumptions while retaining sufficient knowledge on likely defect mechanisms is the key to effective logic diagnosis. This work introduces the Conditional Line Flip (CLF) calculus as a way to describe arbitrary defects in logic circuits. This generalized fault modeling approach is used to investigate the assumptions made by diagnostic fault models and diagnosis algorithms found in the literature. The second main contribution of this work is a location-based logic diagnosis algorithm called Partially Overlapping Impact couNTER (POINTER). It builds directly upon the CLF calculus, works independently of any specialized fault model and offers powerful heuristics for sorting defect candidates according to their likelihood in physical chips. The POINTER approach is extended and modified to account for the particular challenges of high precision diagnostics in a lab, during production, and in autonomous online diagnosis in the field. Experimental results on industrial designs confirm that, despite its generality and lack of application specific knowledge, POINTER performs much better than previous diagnosis approaches. In cases where very high response compaction ratios are used, POINTER even enables fault model independent diagnosis for the first time.