TEST-GENERATION FOR PATH DELAY FAULTS USING BINARY DECISION DIAGRAMS

A new test generation technique for path delay faults in circuits empl oying scan/hold type flip-flops is presented, Reduced ordered binary d ecision diagrams (ROBDDs) are used to represent Boolean functions real ized by ail signals in the circuit, as well as to represent die constr aints to be satisfied by the delay fault test, Two faults are consider ed for each path in the circuit, For each fault, a pair of constraint functions, corresponding to the two time frames that constitute a tran sition, is evaluated. If the constraint function in the second time fr ame is nonnull, robust - hazard-free - test generation for the delay f ault 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 e xistence of a non-robust test is checked, Boolean algebraic manipulati on of the constraint functions guarantees that if neither robust nor n on-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 f aster than previously reported methods based on branch-and-bound algor ithms.