Title :
Information theory and noisy computation
Author :
Evans, William S. ; Schulman, Leonard J.
Author_Institution :
Dept. of Comput. Sci., British Columbia Univ., Vancouver, BC, Canada
Abstract :
We report on two types of results. The first is a study of the rate of decay of information carried by a signal which is being propagated over a noisy channel. The second is a series of lower bounds on the depth, size, and component reliability of noisy logic circuits which are required to compute some function reliably. The arguments used for the circuit results are information-theoretic, and in particular, the signal decay result is essential to the depth lower bound. Our first result can be viewed as a quantified version of the data processing lemma, for the case of Boolean random variables
Keywords :
Boolean functions; circuit reliability; information theory; logic circuits; noise; random processes; telecommunication channels; Boolean random variables; component reliability; data processing; depth; information decay rate; information theory; lower bounds; noisy channel; noisy computation; noisy logic circuits; signal decay; signal propagation; size; Boolean functions; Circuit noise; Computer science; Data processing; Information theory; Logic circuits; Logic gates; Mutual information; Random variables; Reliability theory;
Conference_Titel :
Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on
Conference_Location :
Whistler, BC
Print_ISBN :
0-7803-2453-6
DOI :
10.1109/ISIT.1995.550443
