Document Type
Article
Department
Mathematics (HMC)
Publication Date
1988
Abstract
It is shown that if formulas are used to compute Boolean functions in the presence of randomly occurring failures then: (1) there is a limit strictly less than 1/2 to the failure probability per gate that can be tolerated, and (2) formulas that tolerate failures must be deeper (and, therefore, compute more slowly) than those that do not. The heart of the proof is an information-theoretic argument that deals with computation and errors in very general terms. The strength of this argument is that it applies with equal ease no matter what types of gate are available. Its weaknesses is that it does not seem to predict quantitatively the limiting value of the failure probability or the ratio by which computation proceeds more slowly in the presence of failures.
Rights Information
© 1988 Institute of Electrical and Electronics Engineers
Terms of Use & License Information
DOI
10.1109/18.2628
Recommended Citation
Pippenger, N., "Reliable computation by formulas in the presence of noise," Information Theory, IEEE Transactions on , vol.34, no.2, pp.194,197, Mar 1988. doi: 10.1109/18.2628
