Stochastic Logic Computation

From The Circuits and Biology Lab at UMN

Jump to: navigation, search

Contents

Stochastic Logic Computation

Next Back

Basic Concept

A stochastic logic system is built on a logic circuit, but each input of the circuit is a

Bernoulli sequence. Then, the output of the circuit will also be a binary stochastic bit

stream (In certain cases, it is also Bernoulli sequence). The value in the stochastic

system is represented by the probability of the occurrence of a logical 1 in the

sequence. We usually represent stochastic bit stream in two formats, bipolar and

unipolar formats. In the unipolar case, the value y of a stochastic bit

stream X is

x = P(X = 1) = P(X)

whereas, in the bipolar case

x = 2P(X = 1) − 1 = 2P(X) − 1

Advantages of stochastic logic system include:

  1. Simple hardware implementation of some basic arithmetic operations. For example,

we can use a single AND gate to do multiplication. (For details, please see the next

section.)

  1. Fault tolerance. In stochastic bit stream, all of the bits have the same significance

and the significance of a single bit error is small and decreases with logner bit

stream.

  1. Parallelism. It seems that using a bit stream to represent a single value will

increased the number of clock cycles to accomplish a given computation. However,

we can duplicate the original circuit many times and do parallel computation. Figure

1 shows an example. The original serial computation will require 4 clock cycles to

finish, but using 4x Parellel, the computation cycles reduce to one. Parallelism

allows the tradeoff between time and area.

Image:Parallel.bmp
Figure 1: Parallel implementation (A) serial; (B) 2x parallel; (C) 4x parallel

There are some disadvantages of stochastic logic system. The main disadvantage

is the variance inherent in estimating the value of a stochastic bit stream. Assume

the bit stream X has totally N bits with each one of

probability p to be logical 1. If a stream has k bits to

be 1, then the value we estimated will be
v=\frac{k}{N}

The probability to get k bits is

P(k)=C_N^k p^k (1-p)^{N-k}

The expected value of v=\frac{k}{N} is

E(v)=\sum_{k=0}^N \frac{k}{N} P(k)=p

and the variance of v=\frac{k}{N} is

D(v)=E((v-E(v))^2)=\frac{p(1-p)}{N}

However, the variance will decrease if we use a longer bit stream at the cost of

longer computation time or larger circuit area.

Implementation of Basic Arithmetic Operations with Stochastic Logic

A. Multiplication

In the unipolar format, an AND gate performs the multiplication. Let the input of an

AND gate be two uncorrelated Bernoulli sequence A and

B. The output is also a Bernoulli sequence C. The

value represented by sequence C will be

c=P(C)=P(A)P(B)=ab\,

In the bipolar format, an XNOR gate performs the multiplication. Since \bar {P}=1-P, P(A)=\frac{a+1}{2}, P(B)=\frac{b+1}{2}, the value represented by

sequence C will be

c=2P(C)-1=2[P(A)P(B)+\bar{P}(A)\bar{P}(B)]-1=2\frac{(a+1)(b+1)+(1-a)(1 -b)}{4}-1=ab

B. Addition

Addition and subtraction are not closed operations on the interval [0,1] for unipolar format or [ − 1,1] for bipolar format. Therefore, it is

not possible to perform them, without a scaling operation. To perform addition with

scaling y=\sum_{i} S_i x_i\,, where Si are scaling

value such that \sum_{i} S_i=1\,, A multiplexer is used. It randomly

selects a given input i with the probability Siso that the output

probability will be a scaled sum of the input probabilities. Assume the output

sequence is Y, and input sequences are Xi s. We

have that

P(Y)=\sum_{i} S_i P(X_i)\,

For either unipolar or bipolar format, we will get

y=\sum_{i} S_i x_i\,

Analyzing Stochastic Logic System Built with Combinational Logic Circuits

Generally, the output value (represented by the output stochastic bit stream) of a

stochastic logic system is a function of its input values. The problem interested us is

that given an arbitrary combinational logic circuit building a stochastic logic system,

what is the function it performs and how can we get the function?

Problem Definition

Given a combinational logic circuit with n inputs

x_1,x_2,\cdots,x_n and output Boolean function y=f (x_1,x_2,\cdots,x_n), if its input bit streams represent values

p_1,p_2,\cdots,p_n, respectively and output bit stream represents

value po, what is the function p_o=F(p_1,p_2,\cdots,p_n) and how can we get it?

The Form of Function F

Here we only consider unipolar format representation of value. We can get the

function in bipolar format representation by simply changing F as

2F − 1 and substituting each variable pi with

\frac{p_i+1}{2}. The result for unipolar format is:


F is an integral-coefficient multivariate polynomial in the form of

F(x_1,x_2,\cdots,x_n)=\sum_{\alpha_1,\alpha_2,\cdots,\alpha_n \in \{0,1\}^n} A_{(\alpha_1,\alpha_2,\cdots,\alpha_n)} x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_n^{\alpha_n}

and satisfies

F(x_1,x_2,\cdots,x_n) \equiv f(x_1,x_2,\cdots,x_n), \forall (x_1,x_2,\cdots,x_n) \in \{0,1\}^n

Here the form of F means that each variable in each product term of

F has its power no more than 1.

====The method to get F from the Boolean function

f==== We assume here that the Boolean function f is only composed with

AND(\land), OR(\lor) and NOT(\lnot)

operations. (We can always change f into this form.)

First we construct a multivariate polynomial G which satisfies that

G(x_1,x_2,\cdots,x_n) \equiv f(x_1,x_2,\cdots,x_n), \forall (x_1,x_2,\cdots,x_n) \in \{0,1\}^n. We say that polynomial G

realizes Boolean function f

The construction of G is recursively defined:

  • Basic case: f = x, then G = x
  • NOT case: f=\lnot f_1 and we know G1 realizing

f1. Then, G = 1 − G1

  • AND case: f=f_1 \land f_2 and we know G1 and G2 realizing f1 and f2, respectively. Then,

G=G_1 \cdot G_2

  • OR case: f=f_1 \lor f_2 and we know G1 and G2 realizing f1 and f2, respectively. Then,

G=G_1+G_2-G_1 \cdot G_2

After we get G, we get F by setting to 1 the power of

each variable in a product term of G, if they have power more than 1

in that product term. For example, the product term x_1^2 x_2 in

G will be changed to x1x2 in F. We

call this step as normalization.

Example: Given Boolean function f=x_1 \lor (\lnot x_1 \land x_2), get

F

Solution: f can be composed as:

f_1=x_1\,
f_2=x_1\,
f_3=x_2\,
f_4=\lnot f_2
f_5=f_4 \land f_3
f_6=f_1 \lor f_5

we have

G_1=x_1\,
G_2=x_1\,
G_3=x_2\,
G_4=1-G_2=1-x_1\,
G_5=G_4 \cdot G_3 = x_2 - x_1 x_2
G_6=G_1+G_5-G_1 \cdot G_5 = x_1 + x_2 - x_1 x_2 - x_1 x_2 + x_1^2 x_2

Finally, we do normalization and get F = x_1 + x_2 - x_1 x_2 - x_1 x_2 + x_1^2 x_2 = x_1 + x_2 - x_1 x_2

Retrieved from "http://www.mriedel.ece.umn.edu/wiki/index.php/Stochastic_Logic_Computation"
Personal tools