A METHOD OF FAULT SIMULATION BASED ON STEM REGIONS

An exact fault simulation can be achieved by simulating only the faults on reconvergent fan-out stems, while determining the detectability of faults on other lines by critical path tracing within fan-out-free regions. We have delimited, for every reconvergent fan-out stem, a region of the circuit outside of which the stem fault does not have to be simulated. Lines on the boundary of such a stem region, called exit lines, have the following property: if the stem fault is detected on the line, and the line is critical with respect to a primary output, then the stem fault is detected at that primary output. Any fault simulation technique can be used to simulate the stem fault within its stem region. The fault simulation complexity of a circuit is shown to be directly related to the number and size of stem regions in the circuit. We have used the concept of stem regions as a framework for an efficient fault simulator for combinational circuits. The concept allows a static reduction of the circuit area of explicit analysis for single as well as multiple output circuits. A dynamic reduction of processing steps is also achieved as the fault simulation progresses and fault coverage increases. Both the static and dynamic reductions are fully compatible with the parallel pattern evaluation technique, resulting in a very efficient implementation. The simulation algorithm is described, and experimental results are shown for the well-known benchmark circuits. © 1990 IEEE