Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> From information and coding theory to coded computation <s> Error-correcting codes have been very successful in protecting against errors in data transmission. Computing on encoded data, however, has proved more difficult. In this paper we extend a framework introduced by Spielman [14] for computing on encoded data. This new formulation offers significantly more design flexibility, reduced overhead, and simplicity. It allows for a larger variety of codes to be used in computation and makes explicit conditions on codes that are compatible with computation. We also provide a lower bound on the overhead required for a single step of coded computation. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> From information and coding theory to coded computation <s> Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> From information and coding theory to coded computation <s> Stochastic computing (SC) was proposed in the 1960s as a low-cost alternative to conventional binary computing. It is unique in that it represents and processes information in the form of digitized probabilities. SC employs very low-complexity arithmetic units which was a primary design concern in the past. Despite this advantage and also its inherent error tolerance, SC was seen as impractical because of very long computation times and relatively low accuracy. However, current technology trends tend to increase uncertainty in circuit behavior and imply a need to better understand, and perhaps exploit, probability in computation. This article surveys SC from a modern perspective where the small size, error resilience, and probabilistic features of SC may compete successfully with conventional methodologies in certain applications. First, we survey the literature and review the key concepts of stochastic number representation and circuit structure. We then describe the design of SC-based circuits and evaluate their advantages and disadvantages. Finally, we give examples of the potential applications of SC and discuss some practical problems that are yet to be solved. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> From information and coding theory to coded computation <s> Noise, traditionally defined as an unwanted signal or disturbance, has been shown to play an important constructive role in many information processing systems and algorithms. This noise enhancement has been observed and employed in many physical, biological, and engineered systems. Indeed stochastic facilitation (SF) has been found critical for certain biological information functions such as detection of weak, subthreshold stimuli or suprathreshold signals through both experimental verification and analytical model simulations. In this paper, we present a systematic noise-enhanced information processing framework to analyze and optimize the performance of engineered systems. System performance is evaluated not only in terms of signal-to-noise ratio but also in terms of other more relevant metrics such as probability of error for signal detection or mean square error for parameter estimation. As an important new instance of SF, we also discuss the constructive effect of noise in associative memory recall. Potential enhancement of image processing systems via the addition of noise is discussed with important applications in biomedical image enhancement, image denoising, and classification. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> From information and coding theory to coded computation <s> In this paper the problem of reliable communication with a noisy encoder is examined. We explicitly provided the construction of the encoder and show that even when all logic gates that constitute the encoder are noisy, reliable communication with a positive rate is still possible. The encoding complexity is shown to be O(log 1/p tar /log1/e) per bit to achieve a target bit error rate p tar , where e denotes the error probability of each noisy gate. This complexity upper bound is shown to coincide with a lower bound in order sense, and is hence tight. The key technique in the proposed construction is to embed noisy decoders inside the noisy encoder, which are utilized repeatedly to prevent the bit error rate from escalating. The proposed noisy encoder has a direct application in noisy computing of a linear transform. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> From information and coding theory to coded computation <s> 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. <s> BIB006
The study of fault-tolerant systems dates back to von Neumann's investigation  of building reliable systems from unreliable components. Fault-tolerant systems research has focused more heavily on a coarser-grained view. In contrast, information theory focuses on the mathematical study of communication over noisy channels  while coding theory studies methods for judiciously trading redundancy in data representations for either reduced transmission time (source coding) or improved end-to-end reliability in transmission over a noisy channel (channel coding). In contrast to channel coding techniques whose objective is to counteract the effect of noise, Chen et al. BIB004 exploit the presence of noise to improve image processing tasks, demonstrating how adding Gaussian noise to quantized images can improve the output quality of signal processing tasks. This observation that noise can improve a computing system's performance has parallels to randomized algorithms (see, e.g., Section 9). Classical information and coding theory rely on the assumption that noise only occurs in communication, rather than in computation. In contrast, recent research has begun to study the fundamental limits of encoders BIB005 and decoders BIB002 202] built on top of hardware implementations that are, like the communication channel, susceptible to noise. Similarly, recent research has investigated techniques for executing computation on encoded representations in order to obtain exact or approximate results in the presence of noise. These methods have been referred to in the research literature as coded computation BIB006 BIB001 . One plausible direction for future research is to identify computing abstractions that unify the above techniques via new computational operators that execute on encoded representations. Stochastic computing BIB003 , hyper-dimensional computing  , and deep embedded representations (deep learning) offer promising examples.