Fast identification of untestable delay faults using implications

The authors propose a novel algorithm to rapidly identify untestable delay faults using pre-computed static logic implications. The fault-independent analysis identifies large sets of untestable faults, if any, without enumerating them. The cardinalities of these sets are obtained by using a counting algorithm that has quadratic complexity in the number of lines. Since the method is based on an incomplete set of logic implications, it gives only a lower bound on the number of untestable faults. A post-processing step can list the untestable faults, if desired. Targeting untestable delay faults for test generation by an automatic test pattern generation (ATPG) tool can be avoided. The method works for the segment delay fault model and its special case, the path delay fault model, and identifies robustly untestable, non-robustly untestable, and functionally unsensitizable delay faults. Results on benchmark circuits show that many delay faults are identified as untestable in a very short time. For the benchmark circuit c6288, the algorithm identified 1.978/spl times/10/sup 20/ functionally unsensitizable path faults in 3 CPU seconds.