ON THE MAXIMUM TOLERABLE NOISE FOR RELIABLE COMPUTATION BY FORMULAS

Authors
EVANS W PIPPENGER N
Citation
W. Evans et N. Pippenger, ON THE MAXIMUM TOLERABLE NOISE FOR RELIABLE COMPUTATION BY FORMULAS, IEEE transactions on information theory, 44(3), 1998, pp. 1299-1305
Citations number
7
Categorie Soggetti
Computer Science Information Systems","Engineering, Eletrical & Electronic","Computer Science Information Systems
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
44
Issue
3
Year of publication
1998
Pages
1299 - 1305
Database
ISI
SICI code
0018-9448(1998)44:3<1299:OTMTNF>2.0.ZU;2-9
Abstract
It is shown that if a formula is constructed from noisy 2-input NAND g ates, with each gate failing independently with probability epsilon, t hen reliable computation can or cannot take place according as epsilon is less than or greater than epsilon(0) = (3 - root 7)4 = 0.08856....