An exact non-enumerative fault simulator for path-delay faults

The present an efficient path-delay fault (PDF) simulator that does not involve enumeration of paths. Our method calculates the exact fault coverage, and identifies all tested faults in any circuit with a large number of paths. We present a new data structure, called the Path-Status Graph (PSG), to efficiently hold the status of each PDP in the circuit, i.e., whether or not the PDF is tested. The key to this efficiency is in breaking the information into pieces and distributing it over the data structure and in retaining all or part of the reconverging fanout structure of the circuit in the PSG. Thus, an exponential number of PDFs can share the same piece of information. Using one thousand random tests, we simulated all of the approximately 10²⁰ PDFs in the circuit c6288 and determined that 4.4 billion faults were detected. This number is larger by over three orders of magnitude compared to what was possible with previously reported methods