On the Maximum Tolerable Noise for Reliable Computation by Formulas

Bruce Hajek; Timothy Weller

doi:10.1109/18.75261

On the Maximum Tolerable Noise for Reliable Computation by Formulas

Research output: Contribution to journal › Article › peer-review

Abstract

It is shown that if formulas constructed from error-prone 3-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.

Original language	English (US)
Pages (from-to)	388-391
Number of pages	4
Journal	IEEE Transactions on Information Theory
Volume	37
Issue number	2
DOIs	https://doi.org/10.1109/18.75261
State	Published - Mar 1991

Keywords

Computation by unreliable components
reliable computing

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Online availability

10.1109/18.75261

Library availability

Discover UIUC Full Text

Cite this

@article{94d93f0720c04bbca683551b62516b47,

title = "On the Maximum Tolerable Noise for Reliable Computation by Formulas",

abstract = "It is shown that if formulas constructed from error-prone 3-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 = "Computation by unreliable components, reliable computing",

author = "Bruce Hajek and Timothy Weller",

year = "1991",

month = mar,

doi = "10.1109/18.75261",

language = "English (US)",

volume = "37",

pages = "388--391",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - On the Maximum Tolerable Noise for Reliable Computation by Formulas

AU - Hajek, Bruce

AU - Weller, Timothy

PY - 1991/3

Y1 - 1991/3

N2 - It is shown that if formulas constructed from error-prone 3-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.

AB - It is shown that if formulas constructed from error-prone 3-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.

KW - Computation by unreliable components

KW - reliable computing

UR - https://www.scopus.com/pages/publications/0026121386

UR - https://www.scopus.com/inward/citedby.url?scp=0026121386&partnerID=8YFLogxK

U2 - 10.1109/18.75261

DO - 10.1109/18.75261

M3 - Article

AN - SCOPUS:0026121386

SN - 0018-9448

VL - 37

SP - 388

EP - 391

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 2

ER -

On the Maximum Tolerable Noise for Reliable Computation by Formulas

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this