AND Gate Multiplication in Stochastic Computing

Stochastic computing represents continuous numerical values as probabilities within random binary bitstreams, enabling complex arithmetic operations to be performed with minimal digital hardware. In this paradigm, a standard Boolean AND gate acts as an arithmetic multiplier for two independent unipolar bitstreams. This article explains how stochastic number representation works, the mathematical principle that allows a simple logic gate to perform multiplication, the critical role of statistical independence, and the advantages and trade-offs of this architecture.

Stochastic Bitstream Encoding

In stochastic computing under the unipolar encoding scheme, a real number \(x\) in the interval \([0, 1]\) is represented by a sequence of random binary bits where the value corresponds to the probability of observing a logic high (1):

\[P(X = 1) = x\]

For example, to represent the value \(0.75\), a pseudo-random bitstream generator produces a sequence where approximately 75% of the clock cycles output a 1 and 25% output a 0. In an 8-bit sample, a stream such as 1, 1, 0, 1, 1, 1, 0, 1 contains six ones and two zeros, representing the ratio \(6/8 = 0.75\).

How the AND Gate Performs Multiplication

A standard two-input digital AND gate evaluates two logic inputs, \(A\) and \(B\), to produce an output \(C = A \land B\). The output is 1 if and only if both \(A = 1\) and \(B = 1\).

In probabilistic terms, the expected value of the output bitstream \(C\) is the joint probability that both inputs are simultaneously high:

\[P(C = 1) = P(A = 1 \text{ and } B = 1)\]

According to the laws of probability, if event \(A\) and event \(B\) are statistically independent, the joint probability is the product of their individual probabilities:

\[P(A = 1 \text{ and } B = 1) = P(A = 1) \times P(B = 1)\]

Substituting the encoded numerical values:

\[c = a \times b\]

Because the AND gate outputs a 1 only during clock cycles where both independent input streams emit a 1, the long-term frequency of 1s at the output converges exactly to the product of the two input probabilities.

Step-by-Step Example

Assume two independent bitstreams representing \(a = 0.5\) and \(b = 0.5\):

• Stream A (\(a = 0.5\)): 1, 0, 1, 0, 1, 0, 1, 0 (4 ones out of 8 bits)
• Stream B (\(b = 0.5\)): 1, 1, 0, 0, 1, 1, 0, 0 (4 ones out of 8 bits)

Passing both streams through a standard AND gate cycle by cycle:

• Bit 1: 1 AND 1 = 1

• Bit 2: 0 AND 1 = 0

• Bit 3: 1 AND 0 = 0

• Bit 4: 0 AND 0 = 0

• Bit 5: 1 AND 1 = 1

• Bit 6: 0 AND 1 = 0

• Bit 7: 1 AND 0 = 0

• Bit 8: 0 AND 0 = 0

• Output Stream C: 1, 0, 0, 0, 1, 0, 0, 0 (2 ones out of 8 bits)

The output stream represents \(2/8 = 0.25\), which equals \(0.5 \times 0.5\).

The Requirement of Statistical Independence

The accuracy of AND gate multiplication depends entirely on the statistical independence (uncorrelation) of the input streams. If correlation exists, the multiplication fails:

• Maximum Positive Correlation: If stream \(A\) is identical to stream \(B\), \(A \land A = A\). The output evaluates to \(a\) instead of \(a^2\).
• Negative Correlation: If the 1s in stream \(A\) align exclusively with 0s in stream \(B\), the output evaluates to \(0\), regardless of the individual values.

To maintain calculation accuracy, stochastic computing architectures utilize uncorrelated Linear Feedback Shift Registers (LFSRs) or different random number seeds to generate each input bitstream.

Advantages and Trade-Offs

Advantages

• Ultra-Low Silicon Area: A standard binary multiplier requires hundreds or thousands of logic gates (adders, shift registers). Stochastic multiplication requires only a single AND gate.
• High Fault Tolerance: A single bit flip due to cosmic radiation or hardware noise causes only a minimal, transient fluctuation in the overall probability value, making it highly robust against soft errors.
• Simple Interconnects: Routing arithmetic signals across a chip requires only a single physical wire per stream rather than wide multi-bit parallel buses.

Trade-Offs

• Exponential Latency: To double the precision of a stochastic calculation (equivalent to adding 1 bit in conventional binary), the bitstream length must be quadrupled, leading to high latency and energy consumption for high-precision tasks.
• Random Number Generation Overhead: While the computing logic is minimal, generating high-quality, uncorrelated random bitstreams requires dedicated circuitry (such as LFSRs and comparators) at the input stages.