Title :
On the maximum tolerable noise for reliable computation by formulas
Author :
Hajek, Bruce ; Weller, Timothy
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
fDate :
3/1/1991 12:00:00 AM
Abstract :
It is shown that if formulas constructed from error-prone three-input gates are used to compute Boolean functions, then a per-gate failure probability of 1/6 or more cannot be tolerated. The result is shown to be tight if the per-gate failure probability is constant and precisely known
Keywords :
Boolean functions; probability; reliability theory; Boolean functions; error-prone three-input gates; maximum tolerable noise; per-gate failure probability; reliable computation by formulas; Autocorrelation; Boolean functions; Digital communication; Error probability; Gold; Hypercubes; Notice of Violation; Optical imaging; Optical noise; Spread spectrum communication;
Journal_Title :
Information Theory, IEEE Transactions on
