On the structural properties of cominational circuits and their application to fault simulation

A new fault simulation framework is proposed for combinational circuits, supported by a detailed analysis of the complexity of each of the three fault simulation components: fault-free (logic) simulation, explicit simulation of reconvergent fanout stem faults, and critical path tracing within fanout-free regions. The complexity analysis, measured in terms of the number of required gate evaluations, is implementation independent. The new framework achieves a reduction of the complexity of each component at both the static (input vector independent) level and the dynamic (input vector dependent) level.At the static level, structural properties determined by a reconvergent fanout analysis are used to reduce the explicit simulation of fanout stem faults. At the dynamic level, dependencies between fault detectabilities are identified and used to reduce both the critical path tracing and explicit simulation components. In addition, fault-free simulation is reduced by tracking areas outside of which it is not required. The dynamic analysis reduces the fault simulation even further through a selective choice of the order in which the three simulation components are performed