Signal probabilities in AND-OR trees

The authors consider a class of AND-OR tree circuits and study their response to random-pattern inputs as the depth of the tree is allowed to increase indefinitely. Each binary input of a circuit is independently chosen to be one (zero) with probability x (1-x). The logic of the circuit determines the probability of success (one) at the output as a monotonically increasing S-shaped function of x called the probability transfer function. The probability transfer function of an AND-OR tree is shown to have just one interior fixed point (with respect to changes in depth of the tree) in the (0.1) range of x. Its value is of interest in random testing. As the depth of the tree becomes infinite, the probability transfer function becomes a unit step with the transition point located at the interior fixed point. The authors study the convergence to the unit step as a function of the circuit depth and the fan-ins of the logic gates