Title :
On the maximum tolerable noise of k-input gates for reliable computation by formulas
Author :
Evans, William S. ; Schulman, Leonard J.
Author_Institution :
Dept. of Comput. Sci., Univ. of British Columbia, Vancouver, BC, Canada
Abstract :
We determine the precise threshold of component noise below which formulas composed of odd degree components can reliably compute all Boolean functions.
Keywords :
Boolean functions; circuit noise; computation theory; directed graphs; error statistics; information theory; logic circuits; reliability; Boolean functions; acyclic graph; component noise; directed graph; error probability; information-theoretic technique; input gate noise; interconnection structure; maximum tolerable noise; odd degree component formulas; reliable computation; reliable computing; Boolean functions; Circuit noise; Computational modeling; Computer science; Councils; Error probability; Integrated circuit interconnections; Noise level; Tree graphs;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2003.818405
