How Does Stochastic Computing Multiply with an AND Gate?

Stochastic computing is an alternative computing paradigm that represents numbers as probabilities within random bitstreams rather than using traditional binary positional notation. By encoding values as the frequency of ones in a sequence of bits, complex arithmetic operations can be simplified into basic logic gates. In particular, multiplying two probabilities requires only a single two-input AND gate, offering significant hardware savings and fault tolerance at the cost of longer computation times and lower precision.

Representing Probabilities as Bitstreams

In conventional digital systems, a number is represented using weighted bits, where each bit position corresponds to a power of two. In stochastic computing, a number \(p \in [0, 1]\) is represented in unipolar format by a random bitstream \(X\) of length \(N\). The value of the number is defined as the probability that any given bit \(X_i\) in the stream is equal to \(1\):

\[P(X_i = 1) = p\]

For example, the value \(0.5\) can be represented by a bitstream where approximately half of the bits are \(1\) and half are \(0\), such as 10100110. Unlike binary numbers, the position of each bit carries no weight; only the overall ratio of ones to the total number of bits matters.

To represent signed numbers in the range \([-1, 1]\), stochastic computing uses a bipolar representation. In this format, a value \(x\) is mapped to a probability \(p\) using the relation:

\[x = 2p - 1\]

Here, a bitstream containing all zeros represents \(-1\), a stream with an equal number of ones and zeros represents \(0\), and a stream of all ones represents \(1\).

Multiplying with a Single AND Gate

When two unipolar stochastic bitstreams \(X\) and \(Y\) are fed into a standard two-input AND gate, the output bitstream \(Z\) produces a \(1\) at position \(i\) if and only if both \(X_i = 1\) and \(Y_i = 1\).

If the two input bitstreams are statistically independent, the probability of the output bit being \(1\) is the product of the individual probabilities:

\[P(Z_i = 1) = P(X_i = 1 \text{ and } Y_i = 1) = P(X_i = 1) \cdot P(Y_i = 1) = p_x \cdot p_y\]

This means a single AND gate, which occupies minimal silicon area and consumes very little power, performs exact probabilistic multiplication. In contrast, a conventional binary multiplier requires arrays of adders and shift registers, scaling quadratically with bit width.

For bipolar bitstreams, multiplication is performed using a single XNOR gate instead of an AND gate, because the truth table of an XNOR gate matches the sign rules of signed multiplication.

The Requirement for Independence

The accuracy of AND-gate multiplication relies heavily on the statistical independence of the input bitstreams. If the two streams are correlated—for example, if they are generated using the same pseudo-random number generator seed—the output will not equal \(p_x \cdot p_y\). In the extreme case where \(X\) and \(Y\) are identical bitstreams, feeding them into an AND gate simply outputs \(X\) itself, yielding \(p_x\) instead of \(p_x^2\).

To maintain independence, stochastic circuits use separate random number sources, such as Linear Feedback Shift Registers (LFSRs) with different seeds or taps, or low-discrepancy sequences like Sobol sequences.

Advantages and Trade-offs

Stochastic computing offers two major advantages over traditional binary arithmetic:

• Hardware Simplicity: Arithmetic units shrink from hundreds or thousands of transistors down to single logic gates, making them ideal for massively parallel tasks like neural networks and image processing.
• Fault Tolerance: Because every bit has equal weight, a single bit-flip caused by noise or radiation only changes the represented value by \(\pm \frac{1}{N}\), whereas a bit-flip in the most significant bit of a binary number can cause a catastrophic error.

However, these benefits come with trade-offs. Achieving high precision requires very long bitstreams, as the variance of the estimate decreases proportionally to \(\frac{1}{\sqrt{N}}\). Generating long, uncorrelated random bitstreams also introduces energy and area overhead from the random number generators, which can offset the savings of the simple logic gates if not carefully amortized across many operations.