An efficient tree-based algorithm for computing path delay fault coverage

A new algorithm for the efficient computation of path delay fault coverage for circuits with very large number of path delay faults has been presented. The directed acyclic graph representing a combinational circuit consists of a set of trees rooted at the fanout and output nodes. The algorithm uses a tree-based marking process to compute the path delay fault coverage of a given delay-test set in linear time and memory. The root of a tree is marked as used only when it has been tested with respect to the rising and falling path delay faults passing through all the leaves of the tree. The algorithm takes advantage of large tree structures found in most digital designs, to provide a reasonably accurate and very efficient method for the estimation of path delay fault coverage. Some results obtained using non-robust simulation of benchmark circuits suggest the viability and validity of our approach