Synthesizing Stochastic Logic
From The Circuits and Biology Lab at UMN
Contents |
Synthesizing Stochastic Logic
Motivation
Stochastic logic computation is built on logic circuit and processes information encoded by stochastic bit streams. It could be shown [1] that it implements a multivariate polynomial. With some specific configuration of the probability to be 1 of the input bit streams, it computes a univariate polynomial y = f(x). Our question here is: given an arbitrary univariate polynomial, how to generate a stochastic logic system to implement the given polynomial?
Synthesizing Method
Our method is based on decomposing a given power-basis polynomial into a Bernstein polynomial. Then, we build a system, which is a generalization of a multipexer (shown in Figure 1). It has n selecting inputs x1, x2, ... xn and n+1 data inputs z0, z1, ... zn. The data input zi is selected if and only if i out of n selecting inputs are 1. We configure the input bit streams so that the selecting inputs have their probability to be 1 chosen as x and the data inputs have their probability to be 1 chosen as the Bernstein coefficients. Then, the output stream y has probability to be 1 as the value of the given polynomial evaluated on x.
For more information, please look at the reference below.
The Advantage of Stochastic Logic
The major advantage of stochastic logic is that it is more tolerant to the input noise than deterministic logic.
In deterministic logic, the data is generally encoded as a binary radix. In a noisy environment, bit flips afflict all the bits with equal probability. In the worst case, the most significant bit gets flipped, resulting in relative error of 1/2 on the input value.
In contrast, in a stochastic implementation, the data is represented as the fractional weight on a bit stream of length N. Thus, a single bit flip only changes the input value by 1/N, which is minuscule in comparison.
For more information, please look at the reference below.
