|
|
|
| |
|
Computation in the Presence of Noise |
 |
by P. Elias
|
|
|
|
 |
|
The behavior of a system consisting of a preliminary coder, an unreliable computer, and a decoder is investigated. Coding input blocks of k binary digits into output blocks of n>2k binary digits, it is shown that a simple combinational computer which can take the and or or of k or more input blocks can only be made arbitrarily reliable by making n/k arbitrarily large, so that the capacity for computation, in an information theory coding sense, is zero. Incomplete results for a single and or or circuit give the same result if the output gives no information about the inputs except for the information about their and or or; if this is not demanded, then for n>2k, reliable computation through noisy computing circuits is possible, but the computing is done in the decoder. |
|
|
| Related Subjects: Computers; Data, structures and accessing; Noise |
|
|
|
PDF