Fast identification of untestable delay faults using implications

We propose a novel algorithm to rapidly identify untestable delay faults using pre-computed static logic implications. Our 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 our method is based on an incomplete set of logic implications, it gives only a lower bound of 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 on the segment delay fault model and its special case, the path delay fault model, to identify 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, our algorithm identified 1.978 x 10^20 functionally unsensitizable path faults in 3 CPU seconds.