TEST-GENERATION FOR PATH DELAY FAULTS USING BINARY DECISION DIAGRAMS

A new test generation technique for path delay faults in circuits employing scan/hold type flip-flops is presented, Reduced ordered binary decision diagrams (ROBDDs) are used to represent Boolean functions realized by ail signals in the circuit, as well as to represent die constraints to be satisfied by the delay fault test, Two faults are considered for each path in the circuit, For each fault, a pair of constraint functions, corresponding to the two time frames that constitute a transition, is evaluated. If the constraint function in the second time frame is nonnull, robust - hazard-free - test generation for the delay fault is attempted, A robust test thus generated belongs either to the class of fully transitional path (FTP) tests or to the class of single input transition (SIT) tests. If a robust test cannot be found, the existence of a non-robust test is checked, Boolean algebraic manipulation of the constraint functions guarantees that if neither robust nor non-robust tests exist, the fault is undetectable. In its present form the method is applicable to ail circuits that are amenable to analysis using ROBDDs, An implementation of this technique is used to analyze delay fault testability of ISCAS '89 benchmark circuits, These results show that the algebraic technique is one to two orders of magnitude faster than previously reported methods based on branch-and-bound algorithms.