A new method of fast fault grading

A new algorithm of fast fault grading for combinational circuits, based on critical path tracing, is presented. In the algorithm the information coming from the preprocessing of a circuit structure description is used for static reduction of regions in the circuit where extra analysis of fault propagation is necessary. For most of the benchmarks the reduction exceeds 20%. The pseudoedges are inserted into the circuit structure description so that the multi-stem regions may be proposed in the same way as if they were single-stem ones. The forward pass of a classic critical path tracing algorithm is supplemented with extra calculations of the reachability of nodes belonging to the stem regions. Thanks to that, parallel fault propagation analysis may be performed. The algorithm uses code driven simulation technique and it applies critical path tracing in the whole area of a combinational circuit. No explicit fault simulation is used, at all. The implementation of the algorithm has proven its high efficiency with and even without dynamic reduction of the number of processing steps.