A stochastic model for fault propagation, in combinational circuits

The authors present a new stochastic model for fault propagation in combinational circuits that is sensitive to the structural characteristics of the circuit. Under random testing, fault propagation through a circuit is modeled as a branching process. Due to the presence of fanout, a fault on a gate at level l, once activated, will generate a number of copies of itself, called descendants, at level l+1. Similarly, due to the presence of reconvergent fanout, a fault may cease to propagate. An activated fault is detected if at least one of its descendants is active at the primary outputs. For a fault on a gate at level l, the authors present basic results on the distribution of the number of next-level descendants and the number of kth-level descendants, k⩾l. The importance of these results lies in the fact that they are sensitive to the circuit structure and play a basic role in design for testability