On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates
✍ Scribed by Dan Kleitman; Tom Leighton; Yuan Ma
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 392 KB
- Volume
- 55
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 gate failure, is weaker than the traditional von Neumann model in 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 shortcircuit 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 any k-fault-tolerant circuit for any input-sensitive function using any type of gates (even arbitrarily powerful, multiple-input gates) must have size at least 0(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 are faulty is one of the central questions left open in the paper.