Stochastic computing
arithmetic as probability
A conventional multiplier is a few thousand transistors and a carry chain. In stochastic computing it is a single AND gate. The trick is to stop storing a number as bits of a binary word and start storing it as the chance that a bit in a random stream is 1. This page builds the idea from first principles — multiplication, addition, division, the randomness that makes it work, and the precision you pay for it.
The core idea — a number is a 1-density
Take a value $p\in[0,1]$ and emit a long stream of random bits, each independently 1 with probability $p$. The only thing that carries the number is the fraction of ones; the order is irrelevant. This representation looks wasteful — hundreds of bits for one value — but it makes arithmetic almost free, because operations on probabilities become single logic gates operating one bit at a time, with no carry, no wide adder, and no clocked ALU. Stochastic computing dates to Gaines (1969); it is enjoying a revival precisely because the cost that dominates modern chips is moving and switching bits, and this representation switches very few.
$$\text{value } p \;\;\longleftrightarrow\;\; \Pr(\text{bit}=1)=p, \qquad \hat p=\frac{1}{L}\sum_{i=1}^{L} b_i \;\xrightarrow[L\to\infty]{}\; p$$
Drag the sliders: the green row is the bitwise AND of the two streams, and its 1-density tracks the product $p_1p_2$. Shorten the stream and the estimate gets noisier — that is the whole trade of stochastic computing in one picture.
01 Multiplication — a single gate
For two independent streams, the chance that both bits are 1 at the same position is the product of the two probabilities. So a bitwise AND produces a stream whose density is exactly $p_1p_2$ — multiplication with one gate and no carry. Signed values in $[-1,1]$ use bipolar coding and an XNOR gate instead.
$$\Pr(X\wedge Y=1)=p_x\,p_y \qquad\quad \text{bipolar: } p=\tfrac{x+1}{2},\;\; z = 2\Pr(X\odot Y)-1 = x\cdot y$$
Deeper: why independence is non-negotiable
The identity $\Pr(X\wedge Y)=\Pr(X)\Pr(Y)$ holds only when the two streams are statistically independent. If they share a random source, or one is a delayed copy of the other, the AND density drifts toward $\min(p_1,p_2)$ (fully correlated) rather than the product. This is the single most common way a stochastic circuit goes wrong. In practice each operand is driven by its own de-correlated pseudo-random source (an independent LFSR seed), and correlation is treated as a measurable quantity, not an afterthought. Bipolar coding maps $[-1,1]$ onto $[0,1]$ via $p=(x+1)/2$; the XNOR is 1 when both bits agree, giving density $p_xp_y+(1-p_x)(1-p_y)$, which decodes back to $x\cdot y$.
02 Addition — a multiplexer
You cannot simply OR two streams to add them — densities do not exceed 1, so the sum would saturate. Instead a 2:1 multiplexer picks a bit from stream $x$ or stream $y$ each cycle according to a third random select line, giving a scaled average. The scaling ($\tfrac12$ for a fair select) is carried in the surrounding fixed-point bookkeeping.
$$z = s\cdot x + (1-s)\cdot y, \qquad s=\Pr(\text{select}=1) \;\Rightarrow\; z=\tfrac{1}{2}(x+y)\text{ at }s=\tfrac12$$
Deeper: scaled addition and accumulation
Because the MUX output density is a convex combination of the inputs, it always stays a valid probability — the operation is inherently overflow-free, which is part of stochastic computing's fault tolerance. The price is the constant scale factor: adding $n$ streams through a MUX tree divides the result by $n$, so the decode stage must know the tree depth. For long accumulations (e.g. a dot product across many synapses) designs either track the scale explicitly or switch the accumulator to a fixed-point popcount that counts ones across the packed word, trading a little logic for exactness where it matters.
03 Division & square root — CORDIV
Division has no one-gate identity, but it has a small sequential circuit: CORDIV (Li et al., 2014). It is a tiny state machine that raises its output density until the feedback matches the divisor — roughly four look-up tables. Feeding the same stream into both inputs, $\mathrm{CORDIV}(x,x)$, computes a square root.
$$z=\frac{x}{y}\;\;\text{(CORDIV)}, \qquad \sqrt{x}=\mathrm{CORDIV}(x,x)$$
Deeper: the CORDIV state rule
CORDIV is a correlated divider: on each cycle it observes the numerator bit $x$ and a feedback bit $y$ and updates a single state bit — output 1 when $x=1$, output 0 when $y=1$, otherwise hold the previous output. Over many cycles the output density converges to $x/y$ for $x\le y$. It deliberately uses correlated streams — the opposite requirement to the AND multiplier — which is why a stochastic datapath must track the correlation state of every wire. The same primitive, with both inputs tied together, is a square-root unit; more elaborate functions (exponentials, $\tanh$) are built from finite-state machines over the stream, which is exactly how a stochastic neuron activation is realised in hardware.
04 Where the randomness comes from — the SNG
A number becomes a stream through a stochastic number generator (SNG): each cycle it draws a pseudo-random value $r_t$ and emits 1 when $r_t < p$. The random source is usually a linear-feedback shift register (LFSR) — a handful of flip-flops and XORs. Choosing a low-discrepancy source instead (a Sobol sequence) makes the density converge far faster.
$$b_t = \mathbf{1}[\,r_t < p\,], \qquad \text{Bernoulli LFSR: } \sigma\propto \tfrac{1}{\sqrt{L}}, \qquad \text{Sobol: } \text{error}\propto \tfrac{1}{L}$$
Deeper: LFSR seeds, decorrelation and Sobol convergence
Two operands that will be multiplied must be generated from LFSRs with different seeds (or different taps), or their streams correlate and the AND multiplier biases. A Sobol sequence fills the unit interval more evenly than independent random draws, so its running 1-density approaches $p$ as $O(1/L)$ rather than the $O(1/\sqrt L)$ of a Bernoulli stream — a quadratic reduction in the length needed for a given precision. SC-NeuroCore drives its generated RTL from deterministic LFSR seeds so that a simulation and the silicon produce the identical stream, which is what makes the co-simulation bit-true.
05 Precision, cost & fault tolerance
The estimate of a density from $L$ bits is a binomial mean, so its standard error falls only as $1/\sqrt{L}$: one more bit of precision costs four times the stream length. That is the central limitation. In exchange you get gates that are almost free and a representation that shrugs off bit errors — a single flipped bit changes a density by just $1/L$.
$$\sigma_{\hat p}=\sqrt{\frac{p(1-p)}{L}}\;\propto\;\frac{1}{\sqrt L}, \qquad \Delta\hat p_{\text{1 bit-flip}}=\frac{1}{L}$$
Deeper: when to stay stochastic, and when to fall back
Stochastic computing wins where the workload is massively parallel, error-tolerant and multiply-heavy — exactly the profile of neural inference — and where a soft error must not become a catastrophic one. It loses where you need many bits of precision cheaply, because the $1/\sqrt L$ law makes high accuracy expensive in stream length. Real designs are therefore mixed-precision: the bulk of a network runs as bitstreams, while precision-critical parts fall back to Q8.8 fixed-point or micro-floating-point (MXFP). SC-NeuroCore treats the stream length, correlation and error as a stated numerical contract, and refuses to publish an accuracy number without the error bound or parity check behind it.
From bitstream to silicon
Every operation on this page is a gate or a tiny state machine, which is why a stochastic network lowers so cleanly onto an FPGA. The multiplier is an AND, the adder is a MUX, the divider is CORDIV, the encoder is an LFSR + comparator — and because the random sources are deterministic, the Python model and the generated Verilog produce the same bits cycle-for-cycle. That path — equation to RTL to co-simulation to synthesis to formal proof — is the subject of the hardware page.
Reference — operations at a glance
| Operation | Unipolar $[0,1]$ | Bipolar $[-1,1]$ | Hardware cost |
|---|
| Multiply | AND | XNOR | 1 LUT |
| Scaled add | MUX | MUX | 1 LUT |
| Divide | CORDIV | CORDIV | ~4 LUTs |
| Square root | — | CORDIV(x,x) | ~4 LUTs |
| Decode | Popcount | Popcount | adder tree |
Further reading. Gaines, B. R. (1969) Stochastic computing systems — the founding treatment. Alaghi, A. & Hayes, J. P. (2013) Survey of stochastic computing, ACM TECS. Li, P. et al. (2014) CORDIV stochastic division. For the terminology used above, see the SC-NeuroCore glossary.
The demo above runs entirely in your browser with a standard pseudo-random source; it illustrates the $1/\sqrt L$ behaviour but is not the bit-true LFSR datapath used for hardware generation.