Noise Threshold for Universality of Two-Input Gates

It is known that epsi-noisy gates with two inputs are universal for arbitrary computation (i.e., can compute any function with bounded error), if all gates fail independently with probability epsi and epsi < beta 2 = (3 - radic7)/4 ap 8.856%. In this paper, it is shown that this bound is tight fo...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2008-08, Vol.54 (8), p.3693-3698
Main Author: Unger, F.
Format: Article
Language:English
Subjects:
Applied sciences
Approximation
Circuit faults
Circuit noise
Circuits
Computation with unreliable components
Computational modeling
Computer errors
Electric noise
Electronics
Errors
Exact sciences and technology
fault-tolerant computation
Gates
Information theory
Information, signal and communications theory
Mathematical analysis
Mathematical models
Noise
Noise robustness
Noise threshold
Telecommunications and information theory
Thresholds
Upper bound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is known that epsi-noisy gates with two inputs are universal for arbitrary computation (i.e., can compute any function with bounded error), if all gates fail independently with probability epsi and epsi < beta 2 = (3 - radic7)/4 ap 8.856%. In this paper, it is shown that this bound is tight for formulas, by proving that gates with two inputs, in which each gate fails with probability at least beta 2 cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with two-input gates and it is beta 2 . It is conjectured that the same threshold also holds for circuits.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2008.926459