Stochastic computing is a collection of techniques that represent continuous values by streams of random bits. Complex computations can then be computed by simple bit-wise operations on the streams. Stochastic computing is distinct from the study ofrandomized algorithms.

Suppose that${\displaystyle p,q\in [0,1]}$ is given, and we wish to compute${\displaystyle p\times q}$. Stochastic computing performs this operation using probability instead of arithmetic.

Specifically, suppose that there are two random, independent bit streams calledstochastic numbers (i.e.Bernoulli processes), where the probability of a 1 in the first stream is${\displaystyle p}$, and the probability in the second stream is${\displaystyle q}$. We can take thelogical AND of the two streams.

${\displaystyle a_i}$	1	0	1	1	0	1	...
${\displaystyle b_i}$	1	1	0	1	1	0	...
${\displaystyle a_i\wedge b_i}$	1	0	0	1	0	0	...

The probability of a 1 in the output stream is${\displaystyle pq}$. By observing enough output bits and measuring the frequency of 1s, it is possible to estimate${\displaystyle pq}$ to arbitrary accuracy.

The operation above converts a fairly complicated computation (multiplication of${\displaystyle p}$ and${\displaystyle q}$) into a series of very simple operations (evaluation of${\displaystyle a_i\wedge b_i}$) on random bits.To put in another perspective, assuming the truth table of an AND gate. Conventional interpretation is that the output is trueif and only if input A and B are true. However, if the table is interpreted vertically, (0011) AND (0101) is (0001), i.e., 1/2 x 1/2 = 1/4, which is exactly an arithmetic multiplication. As the information is presented in probability distribution, probability multiplication is literally an AND operation.

More generally speaking, stochastic computing represents numbers as streams of random bits and reconstructs numbers by calculating frequencies. The computations are performed on the streams and translate complicated operations on${\displaystyle p}$ and${\displaystyle q}$ into simple operations on their stream representations. (Because of the method of reconstruction, devices that perform these operations are sometimes called stochastic averaging processors.) In modern terms, stochastic computing can be viewed as an interpretation of calculations in probabilistic terms, which are then evaluated with aGibbs sampler. It can also be interpreted as a hybridanalog/digital computer.

Stochastic computing was first introduced in a pioneering paper byJohn von Neumann in 1953.^[1] However, thetheory could not be fully developed until advances in computing of the 1960s,^[2][3]mostly through a series of simultaneous and parallel efforts in the US^[4]and the UK.^[5]By the late 1960s, attention turned to the design ofspecial-purpose hardware to perform stochastic computation. A host^[6]of these machines were constructed between 1969 and 1974; RASCEL^[7]is pictured in this article.

Despite the intense interest in the 1960s and 1970s, stochasticcomputing ultimately failed to compete with more traditional digitallogic, for reasons outlined below. The first (and last)International Symposium on Stochastic Computing^[8]took place in 1978; active research in the area dwindled over the nextfew years.

Although stochastic computing declined as a general method ofcomputing, it has shown promise in several applications. Research hastraditionally focused on certain tasks in machine learning andcontrol.^[9][10]Somewhat recently, interest has turned towards stochasticdecoding, which applies stochastic computing to the decoding of errorcorrecting codes.^[11] More recently, stochastic circuits have been successfully used inimage processing tasks such asedge detection^[12] andimage thresholding.^[13] Recent advancement in stochastic circuits also shows promising speed and energy efficiency advantages in artificial intelligence (AI)hardware acceleration onedge computing.

Although stochastic computing was a historical failure, it may still remain relevant forsolving certain problems. To understand when it remains relevant, it is useful tocompare stochastic computing with more traditional methods of digital computing.

Suppose we wish to multiplytwo numbers each with${\displaystyle n}$ bits of precision.Using the typicallongmultiplication method, we need to perform${\displaystyle n^2}$ operations. With stochastic computing, we canAND together any number of bits and the expected value will alwaysbe correct. (However, with a small number of samples the variance willrender the actual result highly inaccurate).

Moreover, the underlying operations in a digital multiplier arefull adders, whereas a stochasticcomputer only requires anAND gate. Additionally,a digital multiplier would naively require${\displaystyle 2n}$ input wires,whereas a stochastic multiplier would only require two input wires^{[citation needed]}.(If the digital multiplier serialized its output, however, it would alsorequire only two input wires.)

Additionally, stochastic computing is robust against noise; if a fewbits in a stream are flipped, those errors will have no significant impacton the solution.

Furthermore, stochastic computing elements can tolerate skew in the arrival time of the inputs.Circuits work properly even when the inputs are misaligned temporally. As a result, stochasticsystems can be designed to work with inexpensive locally generated clocks instead of using a global clock and an expensive clock distribution network.^[14]

Finally, stochastic computing provides an estimate of the solutionthat grows more accurate as we extend the bit stream. In particular,it provides a rough estimate very rapidly. This property is usually referred to asprogressive precision, which suggests that the precisionof stochastic numbers (bit streams) increases as computation proceeds.^[15]It is as if themost significant bits of the numberarrive before itsleast significant bits; unlike theconventionalarithmetic circuits where the mostsignificant bits usually arrive last. In someiterative systems the partial solutions obtained through progressive precision can provide faster feedbackthan through traditional computing methods, leading to fasterconvergence.

Stochastic computing is, by its very nature, random. When we examinea random bit stream and try to reconstruct the underlying value, the effective precisioncan be measured by the variance of our sample. In the example above, the digital multipliercomputes a number to${\displaystyle 2n}$ bits of accuracy, so theprecision is${\displaystyle 2^{-2n}}$. If we are using a random bitstream to estimate a number and want the standard deviation of ourestimate of the solution to be at least${\displaystyle 2^{-2n}}$, wewould need${\displaystyle O(2^{4n})}$ samples. This represents anexponential increase in work. In certain applications, however, theprogressive precision property of stochastic computing can be exploitedto compensate this exponential loss.

Second, stochastic computing requires a method of generating randombiased bit streams. In practice, these streams are generated withpseudo-random number generators. Unfortunately, generating(pseudo-)random bits is fairly costly (compared to the expense of,e.g., a full adder). Therefore, the gate-level advantage ofstochastic computing is typically lost.

Third, the analysis of stochastic computing assumes that the bitstreams are independent (uncorrelated). If this assumption does nothold, stochastic computing can fail dramatically. For instance, if wetry to compute${\displaystyle p^2}$ by multiplying a bit stream for${\displaystyle p}$ by itself, the process fails: since${\displaystyle a_i\wedge a_i=a_i}$, the stochastic computation would yield${\displaystyle p\times p=p}$, which is not generally true (unless${\displaystyle p=}$0 or 1).In systems with feedback, the problem of decorrelation can manifest inmore complicated ways. Systems of stochastic processors are prone tolatching, where feedback between different components can achievea deadlocked state.^[16]A great deal of effort must be spent decorrelating the system toattempt to remediate latching.

Fourth, although some digital functions have very simple stochasticcounterparts (such as the translation between multiplication and theAND gate), many do not. Trying to express these functions stochasticallymay cause various pathologies. For instance, stochastic decoding requiresthe computation of the function${\displaystyle f(p,q)\to pq/(pq+(1-p)(1-q))}$.There is no single bit operation that can compute this function; the usual solutioninvolves producing correlated output bits, which, as we have seen above, can causea host of problems.

Other functions (such as the averaging operator${\displaystyle f(p,q)\to (p+q)/2}$ require either stream decimation or inflation. Tradeoffs between precision and memorycan be challenging.

Although stochastic computing has a number of defects when consideredas a method of general computation, there are certain applicationsthat highlight its strengths. One notable case occurs in thedecoding of certain error correcting codes.

In developments unrelated to stochastic computing, highly effectivemethods of decodingLDPC codes usingthebelief propagation algorithm weredeveloped. Belief propagation in this context involves iterativelyreestimating certain parameters using two basic operations(essentially, a probabilistic XOR operation and an averagingoperation).

In 2003, researchers realized that these two operations could bemodeled very simply with stochastic computing.^[17]Moreover, since thebelief propagation algorithm is iterative, stochastic computing provides partialsolutions that may lead to faster convergence.Hardware implementations of stochastic decoders have been built onFPGAs.^[18]The proponents of these methods argue that the performance of stochastic decoding iscompetitive with digital alternatives.

Deterministic methods of SC has been developed to perform completely accurate computation with SC circuits.^[19] The essential principle of these methods is that every bit of one bit-streams interacts with every bit of the other bit-streams exactly once. To produce completely accurate result with these methods, the operation must run for the product of the length of input bit-streams. Deterministic methods are developed based on unary bit-streams,^[20][21] pseudo-random bit-streams,^[22] and low-discrepancy bit-streams.^[23]

There are a number of variants of the basic stochastic computingparadigm. Further information can be found in the referenced book byMars and Poppelbaum.

Bundle Processing involves sending a fixed number ofbits instead of a stream. One of the advantages of this approach isthat the precision is improved. To see why, suppose we transmit${\displaystyle s}$ bits. In regular stochastic computing, we canrepresent a precision of roughly${\displaystyle O(1/\sqrt{s})}$ differentvalues, because of the variance of the estimate. In bundleprocessing, we can represent a precision of${\displaystyle 1/s}$.However, bundle processing retains the same robustness to error ofregular stochastic processing.

Ergodic Processing involves sending a stream of bundles, whichcaptures the benefits of regular stochastic and bundle processing.

Burst Processing encodes a number by a higher base increasingstream. For instance, we would encode 4.3 with ten decimal digits as

4444444555

since the average value of the preceding stream is 4.3. Thisrepresentation offers various advantages: there is no randomizationsince the numbers appear in increasing order,so the PRNG issues are avoided, but many of the advantages ofstochastic computing are retained (such as partial estimates of thesolution). Additionally, it retains the linear precision of bundleand ergodic processing.

• Unconventional computing

• Gaines, Brian R. (1967)."Techniques of Identification with the Stochastic Computer"(PDF).Proceedings IFAC Symposium on "The Problems of Identification in Automatic Control Systems", Section 6 Special Identification Instruments, Prague June 12–19, 1967. Retrieved2013-11-11.
• Alaghi, Armin; Hayes, John P. (2013)."Survey of Stochastic Computing"(PDF).ACM Transactions on Embedded Computing Systems.12 (2s):1–19.CiteSeerX 10.1.1.296.4448.doi:10.1145/2465787.2465794.S2CID 4689958. Retrieved2013-11-11.

• History of computing hardware
• Models of computation
• Statistical randomness

• CS1 errors: ISBN date
• CS1 maint: location missing publisher
• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from October 2014