Stochastic computing (SC) is subject to many subtle, interacting, and application-driven error types often not found in conventional binary computing systems. These errors may defy standard methods of analysis and demand the use of black-box simulation to quantify system performance and accuracy. To address this issue, we propose a methodology called Bayesian Analysis of Stochastic Errors (BASE). BASE provides a comprehensive statistical basis for understanding and analyzing SC errors either in mathematical terms or in conjunction with simulation. It also introduces three new viewpoints into SC theory: bias-variance decomposition to distinguish systematic from random errors, Bayesian cost metrics to account for application dependencies, and estimator dominance to compare circuits. We demonstrate BASE’s utility via examples that reveal the intricacies of stochastic circuit errors. We also use BASE to analyze SC’s fundamental building blocks and demonstrate how to analyze circuit error using purely statistical models.

Stochastic computing (SC) uses streams of pseudo-random bits to perform low-cost and error-tolerant numerical processing for applications like neural networks and digital filtering. A key operation in these domains is the summation of many hundreds of bit-streams, but existing SC adders are inflexible and unpredictable. Basic mux adders have low area but poor accuracy while other adders like accumulative parallel counters (APCs) have good accuracy but high area. This work introduces parallel sampling adders (PSAs), a novel weighted adder family that offers a favorable area-accuracy trade-off and provides great flexibility to large-scale SC adder design. Our experiments show that PSAs can sometimes achieve the same high accuracy as APCs, but at half the area cost. We also examine the behavior of large-scale SC adders in depth and uncover some surprising results. First, APC accuracy is shown to be sensitive to input correlation despite the common belief that APCs are correlation insensitive. Then, we show that mux-based adders are sometimes more accurate than APCs, which contradicts most prior studies. Explanations for these anomalies are given and a decorrelation scheme is proposed to improve APC accuracy by 4x for a digital filtering application.

Stochastic computing (SC) is a low-cost computational paradigm that has promising applications in digital filter design, image processing, and neural networks. Fundamental to these applications is the weighted addition operation, which is most often implemented by a multiplexer (mux) tree. Mux-based adders have very low area but typically require long bitstreams to reach practical accuracy thresholds when the number of summands is large. In this work, we first identify the main contributors to mux adder error. We then demonstrate with analysis and experiment that two new techniques, precise sampling and full correlation, can target and mitigate these error sources. Implementing these techniques in hardware leads to the design of CeMux (Correlation-enhanced Multiplexer), a stochastic mux adder that is significantly more accurate and uses much less area than traditional weighted adders. We compare CeMux to other SC and hybrid designs for an electrocardiogram filtering case study that employs a large digital filter. One major result is that CeMux is shown to be accurate even for large input sizes. CeMux's higher accuracy leads to a latency reduction of 4× to 16× over other designs. Furthermore, CeMux uses about 35% less area than existing designs, and we demonstrate that a small amount of accuracy can be traded for a further 50% reduction in area. Finally, we compare CeMux to a conventional binary design and we show that CeMux can achieve a 50% to 73% area reduction for similar power and latency as the conventional design but at a slightly higher level of error.

A fundamental assumption in stochastic computing (SC) is that bit-streams are generally well-approximated by a Bernoulli process, i.e., a sequence of independent 0-1 choices. We show that this assumption is flawed in unexpected and significant ways for some bit-streams such as those produced by a typical LFSR-based stochastic number generator (SNG). In particular, the Bernoulli assumption leads to a surprising overestimation of output errors and how they vary with input changes. We then propose a more accurate model for such bit-streams based on the hypergeometric distribution and examine its implications for several SC applications. First, we explore the effect of correlation on a mux-based stochastic adder and show that, contrary to what was previously thought, it is not entirely correlation insensitive. Further, inspired by the hypergeometric model, we introduce a new mux tree adder that offers major area savings and accuracy improvement. The effectiveness of this study is validated on a large image processing circuit which achieves an accuracy improvement of 32%, combined with a reduction in overall circuit area.

Understanding accuracy and the tradeoffs it entails is key to evaluating the growing list of stochastic computing (SC) circuit designs. Due to shortcomings of current SC error theory, simulation has become the standard way to estimate a circuit's accuracy. However, simulation can demand large computational resources and lead to uncertain, misleading, or unexplainable results. A soundly based analytic approach is therefore preferable to simulation. In this work, we first show the input value distribution's large influence on circuit accuracy. Then we develop a Bayesian error analysis methodology which uses the input value distribution as a prior to inform better accuracy estimates. This error formulation introduces concepts new to SC such as estimator dominance and points to ways of improving simulation-based accuracy estimates. Orthogonal to the Bayesian ideas, we also show how to use bias-variance decomposition to simplify and aggregate the effects of SC's many error sources. We present techniques that use the beta distribution to model the stochastic number value distribution. Finally, we demonstrate the use of these ideas to improve the accuracy and analysis of an SC-based neural network.

An asymptotic form for the spectral density of a continuous-phase digital FM signal is derived. This expression is valid at frequencies far from the carrier and shows how the rate at which the spectral density falls away depends on the baseband pulse shape.