DocumentCode
1780534
Title
Is “Shannon-capacity of noisy computing” zero?
Author
Grover, Pulkit
Author_Institution
Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear
2014
fDate
June 29 2014-July 4 2014
Firstpage
2854
Lastpage
2858
Abstract
Towards understanding energy requirements for computation with noisy gates, we consider the computation of an arbitrary k-input, k-output binary invertible function. For broader applicability of our results, we allow using some noiseless gates in conjugation with noisy ones. However, we stipulate that the input gates on the computation graph must be separated from the output nodes by a “noisy cut.” We show that for the “information-friction” model proposed recently for energy consumed in circuits, and for binary-input AWGN noise in the computational nodes (with fixed communication schedule), the total (gate + info-friction) energy consumption for reliable computation must diverge to infinity as the target error probability is lowered to zero. Thus, in this model, the capacity of noisy computing is zero regardless of how “rate” of computation is defined: the required energy is unbounded for reliable computation regardless of how efficiently the available resources (e.g. gates, wires, etc.) are used.
Keywords
AWGN; graph theory; information theory; Shannon-capacity; binary-input AWGN noise; computation graph; computational nodes; energy requirements; information-friction model; k-input k-output binary invertible function; noiseless gates; noisy computing; noisy gates; reliable computation; Computational modeling; Error probability; Integrated circuit modeling; Integrated circuit reliability; Logic gates; Noise measurement;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory (ISIT), 2014 IEEE International Symposium on
Conference_Location
Honolulu, HI
Type
conf
DOI
10.1109/ISIT.2014.6875355
Filename
6875355
Link To Document