ON THE DESIGN OF RELIABLE BOOLEAN CIRCUITS THAT CONTAIN PARTIALLY UNRELIABLE GATES

We investigate a model of gate failure for Boolean circuits in which a faulty gate is restricted to output one of its input values. For some types of gates, the model, which we call the short-circuit model of g ate failure, is weaker than the traditional von Neumann model in which faulty gates always output precisely the wrong value. Our model has t he advantage that it allows us to design Boolean circuits that can tol erate worst-case faults, as well as circuits that have arbitrarily hig h success probability in the case of random faults. Moreover, the shor t-circuit model captures a particular type of fault that commonly appe ars in practice, and it suggests a simple method for performing postte st alterations to circuits that have more severe types of faults. A va riety of bounds on the size of fault-tolerant circuits are proved in t he paper. Perhaps, the most important is a proof that any k-fault-tole rant circuit for any input-sensitive function using any type of gates (even arbitrarily powerful, multiple-input gates) must have size at le ast Omega(k log k/log log k). Obtaining a tight bound on the size of a circuit for computing the AND of two values if up to k of the gates a re faulty is one of the central questions left open in the paper. (C) 1997 Academic Press.