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 theshort-circuit model of gate failure, is weaker than the traditionalvon Neumann modelin which faulty gates always output precisely the wrong value. Our model has the advantage that it allows us to design Boolean circuits that can tolerate worst-case faults, as well as circuits that have arbitrarily high success probability in the case of random faults. Moreover, the short-circuit model captures a particular type of fault that commonly appears in practice, and it suggests a simple method for performing posttest alterations to circuits that have more severe types of faults. A variety of bounds on the size of fault-tolerant circuits are proved in the paper. Perhaps, the most important is a proof that anyk-fault-tolerant circuit for any input-sensitive function using any type of gates (even arbitrarily powerful, multiple-input gates) must have size at leastΩ(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 tokof the gates are faulty is one of the central questions left open in the paper.