Stochastic computing

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 of randomized 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 called stochastic 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 the logical AND of the two streams.

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}\land 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 true if 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 a Gibbs sampler. It can also be interpreted as a hybrid analog/digital computer.

Stochastic computing was first introduced in a pioneering paper by John von Neumann in 1953. However, the theory could not be fully developed until advances in computing of the 1960s, mostly through a series of simultaneous and parallel efforts in the US and the UK. By the late 1960s, attention turned to the design of special-purpose hardware to perform stochastic computation. A host of these machines were constructed between 1969 and 1974; RASCEL is pictured in this article.

Despite the intense interest in the 1960s and 1970s, stochastic computing ultimately failed to compete with more traditional digital logic, for reasons outlined below. The first (and last) International Symposium on Stochastic Computing took place in 1978; active research in the area dwindled over the next few years.