Some false paths are caused by redundant stuck-at faults. Removal of those stuck-at faults automatically eliminates such false paths from the circuit. However, there are other false paths that are not associated with any redundant stuck-at fault. All links of such a false path are shared with other testable paths. We focus on the elimination of this type of false paths. We use a nonenumerative path delay fault simulator, which duplicates selected gates to separate the detected and undetected path delay faults. The expanded circuit may contain new redundant stuck-at faults, corresponding to those undetected paths that are false. This happens because in the expanded circuit some new links have only false paths passing through them. Such links become the sites for redundant stuck-at faults. Removal of these redundant faults eliminates false paths. The quality of the result may depend on the coverage of testable paths by the vectors that are simulated. Since a non-enumerative path delay simulation and an implication-based redundancy removal technique are used, the present procedure of false-path elimination can be applied to very large circuits.

We present an efficient path-delay fault (PDF) simulator that does not involve the 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 PDF in the circuit, i.e., whether or not the PDF is tested. The keg 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 fan-out structure of the circuit in the PSG. Thus, an exponential number of PDF's can share the same piece of information. Using 1000 random tests, we simulated all of the approximately 10/sup 20/ PDF's 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.

A new simulation-based method uses single-input change (SIC) vectors to derive tests efficiently for singly testable (ST) path-delay faults (PDFs). A PDF is ST if there exists a delay test that guarantees its detection when it is the only PDF in the circuit. It is known that an ST PDF must have a single-input change test. We utilize this result and present a fault simulator that is specifically tuned to simulate single-input change vectors efficiently. We assign random values to all inputs, and then propagate rising and falling transitions from each input while all other inputs are held steady. We present a 16-valued algebra with which rising and falling PDF's from all inputs are concurrently simulated. Using a suitable encoding for signal values, gates are evaluated directly through Boolean operations, and all computation stages use machine word parallelism. Results on the ISCAS'85 and '89 benchmarks show that the approach is superior to another published method in terms of both fault coverage and execution time.

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/sup 20/ 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.

In this paper, we classify path-delay faults into three categories: singly-testable (ST), multiply-testable (MT), and singly-testable dependent (ST-dependent). All ST faults are guaranteed detection in the case of a single fault, and some may be guaranteed detection through robust and validatable non-robust tests even in the case of multiple faults. An ST-dependent fault can affect the circuit speed only if certain ST faults are present. Thus, if the ST faults are tested, the ST-dependent faults need not be tested. MT faults cannot be guaranteed detection, but affect the speed only if delay faults simultaneously exist on a set of paths none of which is ST. We classify all path-delay faults into the three categories by a procedure using any unaltered single stuck fault test generation tool. We use only two runs of this tool on a network derived from the original network. As a by-product of this process, we generate single and multiple input change delay tests for all testable faults. With these tests, we expect that most defective circuits are identified. Examples and results on ISCAS'89 benchmarks are presented.