# Random Error Reduction Scheme for Combinational Stochastic Circuit

Authors: Ye Cheng; Jianhao Hu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

In conventional stochastic computation, all the input streams are Bernoulli sequences (BSs), which may result in large random error. To reduce random error and improve computational accuracy, some other sequences have been reported as alternatives to BSs. However, these sequences only apply to the specific stochastic circuits, have difficulties in hardware generation, or have length constraints. To this end, new sequences without these disadvantages should be considered. This paper proposes the random error analysis method for stochastic computation based on autocorrelation sequence (AS), which is more general than the conventional one based on BS. The analysis results show that we can use the proper ASs as input streams of stochastic circuits to reduce random error. On the basis of that conclusion, we propose the random error reduction scheme based on maximal concentrated autocorrelation sequence (MCAS) and BS, both of which are ASs. MCAS and BS are applicable to any combinational stochastic circuit, are easily generated by hardware, and have no length constraints, which avoid the disadvantages of sequences in the previous work. Moreover, we apply the proposed random error reduction scheme into several typical stochastic circuits as case studies. The simulation results confirm the effectiveness of the proposed scheme.


---

## Body

## 1. Introduction

Stochastic computation, first introduced in 1960s [1], has been widely used in many fields: neural network [2, 3], digital image processing [4–7], channel decoding [8–10], MIMO detection [11, 12], reliability evaluation [13], and so on. The main idea of stochastic computation is to represent continuous values with stochastic bit streams, which makes it possible to perform complex arithmetic computations with simple bitwise operations. One obvious advantage of stochastic computation is that the hardware implementation of the stochastic arithmetic is much simpler than the traditional arithmetic. For example, as shown in Figure 1, multiplication and scaling addition can be performed with an AND gate and a multiplexer, respectively. The simplicity of hardware also brings short critical path and high clock rate. Moreover, all the bits in a stochastic bit stream have the same significance. That means the stochastic arithmetic is unary coding arithmetic which has better fault tolerance than the traditional binary arithmetic. Recently, skew tolerance has also been introduced as another inherent advantage of stochastic computation.Figure 1
Stochastic circuit of arithmetic. (a) Multiplication; (b) scaling addition.
(a)
(b)Despite the above advantages, a disadvantage of stochastic computation is that the random fluctuations of stochastic bit streams introduce the random error, which causes the computation result to be a random variable. In [4], it is suggested that, in most cases, the random error will dominate the other errors such as quantization error and approximate error. Thus, the random error should be carefully investigated and addressed in stochastic computation area.Thus far, many statistical models for random error analysis have been proposed. They are all based on variance evaluations. In the early work, it is assumed that all the input streams of stochastic circuits are BSs. Qian et al. [4] propose the variance evaluation model base on BSs. However, in real application, the random error for stochastic arithmetic based on BSs is often too large. Therefore, people have made effects to reduce random error by using other sequences as input streams of stochastic circuits.Braendler et al. [3] employ two deterministic bit streams (DBSs) as input streams for the stochastic circuit AND gate. The output stream is also deterministic, which means there are no random fluctuations. Although it eliminates random fluctuations and improves computational accuracy, the use of these DBSs is narrowly restricted to the single AND gate. They can not apply to more complex stochastic circuits.Alaghi and Hayes [14] propose a general framework for analyzing stochastic circuits with correlated inputs. They demonstrate that using correlated inputs can significantly reduce the random error for some stochastic circuits. However, the use of correlated inputs has its limitation. For example, as illustrated in [15], if the two input streams applied to an AND gate are correlated, say, each has the same bit-pattern of value x, then the output will also have value x instead of x2. Hence, the AND gate will not perform multiplication if its inputs are correlated. Similarly, many other commonly used stochastic computational elements can not perform the expected arithmetic with correlated inputs, which largely restricts their applications in stochastic computation systems.Han et al. [13] use fixed-ones random-permutation sequences (FRSs) as input streams for stochastic circuits. They present the variance evaluation model for the basic stochastic computational elements, including AND gate and invert. Furthermore, they prove that the use of FRSs as input streams reduces random error for stochastic computation compared to the conventional use of BSs. FRSs can be wildly used in stochastic arithmetic. They apply to any combinational stochastic circuit. In [13], FRSs are generated by software and used as input streams of the stochastic circuit for reliability evaluation. However, the low cost hardware generation of FRS is difficult to implement. Thus, FRSs are not suitable for stochastic circuits with input streams generated by hardware.Najafi et al. [16] use pulse-width modulation (PWM) to time-encode values for more efficient stochastic computing. They represent values by periodic PWM signals. If two PWM signals are not harmonically related, stochastic multiplication of numbers represented by them obtains the best accuracy when running the operation for the least common multiple (LCM) or multiples of the LCM of the period of the inputs. For instance, X=3/5 is represented by a PWM signal with period of 5, namely, 1,1,0,0,0, and Y=1/3 is represented by a PWM signal with period of 3, namely, 1,0,0. The LCM of the period of X and Y is 15. Thus, when multiplying X and Y with an AND gate, let both of the two bit streams run for 15 clock cycles; that is, X=1,1,0,0,0,1,1,0,0,0,1,1,0,0,0, and Y=1,0,0,1,0,0,1,0,0,1,0,0,1,0,0. Taking the bitwise AND of X and Y, the output stream is Z=1,0,0,0,0,0,1,0,0,0,0,0,0,0,0, which represents 2/15=2/5×1/3. However, if the operation runs for only 10 clocks, that is, X=1,1,0,0,0,1,1,0,0,0, and Y=1,0,0,1,0,0,1,0,0,1, the output stream is Z=1,0,0,0,0,0,1,0,0,0, which represents 2/10, not the expected value. Similarly, some other stochastic arithmetic, using PWM signals as input streams, can get the expected results only if the operations run for the required time. Hence, we can see that there are length constrains on stochastic computation based on PWM signals. The length of input streams is not flexible but determined by the period of input streams.From above, we can see that the main issues of stochastic arithmetic based on different input streams are as follows:(i)
BSs: large random error;(ii)
DBSs or correlated inputs: only applicable for the specific stochastic circuits;(iii)
FRSs: difficulties in hardware generation;(iv)
PWM signals: length constraints.To avoid these disadvantages, we need to use other proper sequences as input streams. Considering the autocorrelation between different bits of a sequence, we propose the notion of AS. And then we analyze the random error of stochastic arithmetic on the assumption that input streams are ASs. By definition, BS can be seen as a special AS with equivalent autocorrelation coefficients. Thus, the proposed random error analysis method based on AS is more general than the conventional one based on BS.According to our analysis results, if proper ASs are used as input streams, the random error can be reduced. Based on that conclusion, we investigate how to reduce random error for any combinational stochastic circuit by employing MCASs and BSs, both of which are ASs, as input streams. Then, We adopt several typical stochastic circuits as case studies and find that the use of MCASs and BSs can significantly improve the calculation performance. MCAS has no difficulties in hardware generation and the hardware cost of the MCAS generator is merely the same as that of the conventional BS generator. Moreover, from the simulation results, the random error reduction scheme based on MCAS and BS is valid for any input stream length and has no length constraints. Hence, by using MCASs and BSs as input streams, we avoid the disadvantages in the previous work and achieve the following goals:(i)
Random error reduction: the random error is reduced compared to using only BSs as input streams;(ii)
Wide applications: the random error reduction scheme based on MCAS and BS is applicable to any combinational stochastic circuit;(iii)
Easy hardware generation: the MCAS and BS generator are easily implemented by hardware;(iv)
Flexible length: the MCAS and BS have no length constraints.Parts of this paper are based on our prior work entitled “Random Error Analysis and Reduction for Stochastic Computation Based on Autocorrelation Sequence,” which has been presented at the IEEE International Symposium on Circuits and Systems (ISCAS), 2014. In the conference paper, we briefly present a general random error analysis method for stochastic computation and illustrate how to reduce random error for a typical stochastic circuit. Compared with the conference version, this journal manuscript has more new contents updated and more insightful discussion, which are stated as follows:(i)
Detailed illustration of the general random error analysis method is provided.(ii)
The random error reduction scheme for any combination stochastic circuit is proposed.(iii)
The complete mathematical proof for the effectiveness of the proposed random error reduction scheme is given.(iv)
More typical stochastic circuits are presented as case studies.The rest of the paper is structured as follows: Section2 analyzes the random error based on AS. Section 3 illustrates the random error reduction scheme based on MCAS and BS for any combinational stochastic circuit. Section 4 presents several typical case studies. Section 5 gives simulation results. Finally, we give conclusions and future directions of research.


## 2. Random Error Analysis Method

### 2.1. Expectation and Variance

In stochastic computation, a stochastic bit streamX with length of n can be written as (1)X=X1,X2,…,Xn,Xi∈0,1,i=1,2,…,n.The expectation of X is defined by (2)EX=E1n∑i=1nXi=1n∑i=1nEXi,and the variance of X is defined by (3)VarX=Var1n∑i=1nXi=1n2Var∑i=1nXi.Consider an arithmetic operationF with k normalized input numbers x1,x2,…,xk and a result z, which can be expressed by z=F(x1,x2,…,xk). In the stochastic implementing of F, each input number xr, 1⩽r⩽k, is represented by the corresponding stochastic bit stream, denoted by Xr, where EXr=xr. We employ these stochastic bit streams as input streams of stochastic circuit. Then, the stochastic computational result, denoted by z′, can be obtained from the output stream Z as follows: (4)z′=1n∑i=1nZi.There are two important statistics for stochastic arithmetic. The first one is the expectation of output stream. Sincez′ should be an unbiased estimator of the actual result z, we have (5)Ez′=z=Fx1,x2,…,xk.From (2) and (4), (5) can be rewritten as EZ=z=F(x1,x2,…,xk). Thus, the expectation of output stream indicates the arithmetic operation performed by stochastic circuit.Another important statistic is the variance of output stream. Considering thatz′ is an unbiased estimator of the actual result z, random error can be calculated in the form of mean square error (MSE) as (6)MSE=Ez′-z2=Ez′-Ez′2=Varz′.By (3) and (6), MSE=VarZ. Therefore, the random error for stochastic computation can be measured by the variance of output stream.


### 2.2. Autocorrelation Sequence

For a bit streamX with length of n, the correlation between two different bits can be measured by autocorrelation coefficient, which is defined by RijX=EX(i)X(j), 1⩽i<j⩽n. For example, if X is a BS, its autocorrelation coefficients are RijX=(EX)2, 1⩽i<j⩽n; that is, all the autocorrelation coefficients of BS are equivalent to the square of its expectation.In the practical applications, input streams may have a variety of autocorrelation coefficients. Considering that, we propose AS, whose autocorrelation coefficients are not necessarily equivalent to each other.Definition 1.
A bit streamX, which represents the probability x, is called an AS on the following condition: EX=x.From Definition1, AS is more general compared to BS and BS can be seen as special case of AS whose autocorrelation coefficients are equivalent to the square of its expectation.


### 2.3. Random Error Analysis Based on AS

For clarity, we define the following notations: let BI denote the case that all the input streams are BSs; let AI denote the case that all the input streams are ASs; letE(BI) denote the expectation of output stream Z in the case of BI; let E(AI) denote the expectation of output stream Z in the case of AI; let Var(BI) denote the variance of output stream Z in the case of BI; let Var(AI) denote the variance of output stream Z in the case of AI.For any stochastic circuit, we expect that the arithmetic computed in the case of AI is the same as that in the case of BI. As illustrated in Section2.1, the expectation of output stream indicates the arithmetic operation performed by stochastic circuit. Hence, the expectations of output stream should be equivalent to each other in the two cases and we have (7)E(AI)=E(BI).Equation (7) is the essential condition for the random error analysis in the case of AI. On the premise of (7), the random error base on AS can be measured by the variance of the output stream Z as follows: (8)VarAI=1n2Var∑i=1nZi=1n2∑i=1n∑j≠iEZiZj-EZiEZj+1n2∑i=1nVarZi=1nEBI-E2BI+1n2∑i=1n∑j≠iEZiZj.Example 2.
As shown in Figure1, two stochastic bit streams X1 and X2 are employed as the input streams for an AND gate. When X1 and X2 are BSs, EX1(i)=EX1, EX2(i)=EX2, i=1,2,3,…,n. The expectation of output streams can be calculated as (9)EBI=1n∑i=1nEX1iX2i=1n∑i=1nEX1EX2=EX1EX2.Now, consider that the input streams X1 and X2 are ASs with the following properties: EX1(i)=EX1 or EX2(i)=EX2, i=1,2,3,…,n. Without losing generality, we suppose that EX1(i)=EX1. The expectation of output stream can be calculated as (10)EAI=1n∑i=1nEX1iX2i=1nEX1∑i=1nEX2i=EX1EX2.By (9) and (10), (7) is satisfied. Thus, the random error can be calculated by (8) as follows: (11)VarAI=1nEX1EX2-EX12EX22+1n2∑i=1n∑j≠iRijX1RijX2.Hence, the variance of output stream in the case of AI is determined by the expectations and autocorrelation coefficients of input streams.


### 2.4. AI Affection Evaluation

In order to evaluate how much AI affects the random error, we propose differential variance, denoted byDV, where DV=Var(AI)-Var(BI). As suggested in [4], the variance of output stream in the case of BI can be calculated by (12)VarBI=EBI1-EBIn.Then we have the following theorem.Theorem 3.
The range of DV is as follows:(13)E2BI-EBIn⩽DV⩽n-1nEBI-E2BI.Proof.
See our prior work [17].According to Theorem3, the upper bound of DV is nonnegative and the lower bound of DV is nonpositive. Thus, DV can be positive, which indicates that the improper use of AS will result in the increase of random error. On the other hand, DV can be negative, which indicates that the proper use of AS will reduce random error. Therefore, we get the following conclusions.(i)
Since the random error in the case of AI can be less than that in the case of BI, the random error reduction scheme based on AS is feasible.(ii)
Since the random error in the case of AI can be greater than that in the case of BI, it is important to select proper AS to avoid this situation.


## 2.1. Expectation and Variance

In stochastic computation, a stochastic bit streamX with length of n can be written as (1)X=X1,X2,…,Xn,Xi∈0,1,i=1,2,…,n.The expectation of X is defined by (2)EX=E1n∑i=1nXi=1n∑i=1nEXi,and the variance of X is defined by (3)VarX=Var1n∑i=1nXi=1n2Var∑i=1nXi.Consider an arithmetic operationF with k normalized input numbers x1,x2,…,xk and a result z, which can be expressed by z=F(x1,x2,…,xk). In the stochastic implementing of F, each input number xr, 1⩽r⩽k, is represented by the corresponding stochastic bit stream, denoted by Xr, where EXr=xr. We employ these stochastic bit streams as input streams of stochastic circuit. Then, the stochastic computational result, denoted by z′, can be obtained from the output stream Z as follows: (4)z′=1n∑i=1nZi.There are two important statistics for stochastic arithmetic. The first one is the expectation of output stream. Sincez′ should be an unbiased estimator of the actual result z, we have (5)Ez′=z=Fx1,x2,…,xk.From (2) and (4), (5) can be rewritten as EZ=z=F(x1,x2,…,xk). Thus, the expectation of output stream indicates the arithmetic operation performed by stochastic circuit.Another important statistic is the variance of output stream. Considering thatz′ is an unbiased estimator of the actual result z, random error can be calculated in the form of mean square error (MSE) as (6)MSE=Ez′-z2=Ez′-Ez′2=Varz′.By (3) and (6), MSE=VarZ. Therefore, the random error for stochastic computation can be measured by the variance of output stream.


## 2.2. Autocorrelation Sequence

For a bit streamX with length of n, the correlation between two different bits can be measured by autocorrelation coefficient, which is defined by RijX=EX(i)X(j), 1⩽i<j⩽n. For example, if X is a BS, its autocorrelation coefficients are RijX=(EX)2, 1⩽i<j⩽n; that is, all the autocorrelation coefficients of BS are equivalent to the square of its expectation.In the practical applications, input streams may have a variety of autocorrelation coefficients. Considering that, we propose AS, whose autocorrelation coefficients are not necessarily equivalent to each other.Definition 1.
A bit streamX, which represents the probability x, is called an AS on the following condition: EX=x.From Definition1, AS is more general compared to BS and BS can be seen as special case of AS whose autocorrelation coefficients are equivalent to the square of its expectation.


## 2.3. Random Error Analysis Based on AS

For clarity, we define the following notations: let BI denote the case that all the input streams are BSs; let AI denote the case that all the input streams are ASs; letE(BI) denote the expectation of output stream Z in the case of BI; let E(AI) denote the expectation of output stream Z in the case of AI; let Var(BI) denote the variance of output stream Z in the case of BI; let Var(AI) denote the variance of output stream Z in the case of AI.For any stochastic circuit, we expect that the arithmetic computed in the case of AI is the same as that in the case of BI. As illustrated in Section2.1, the expectation of output stream indicates the arithmetic operation performed by stochastic circuit. Hence, the expectations of output stream should be equivalent to each other in the two cases and we have (7)E(AI)=E(BI).Equation (7) is the essential condition for the random error analysis in the case of AI. On the premise of (7), the random error base on AS can be measured by the variance of the output stream Z as follows: (8)VarAI=1n2Var∑i=1nZi=1n2∑i=1n∑j≠iEZiZj-EZiEZj+1n2∑i=1nVarZi=1nEBI-E2BI+1n2∑i=1n∑j≠iEZiZj.Example 2.
As shown in Figure1, two stochastic bit streams X1 and X2 are employed as the input streams for an AND gate. When X1 and X2 are BSs, EX1(i)=EX1, EX2(i)=EX2, i=1,2,3,…,n. The expectation of output streams can be calculated as (9)EBI=1n∑i=1nEX1iX2i=1n∑i=1nEX1EX2=EX1EX2.Now, consider that the input streams X1 and X2 are ASs with the following properties: EX1(i)=EX1 or EX2(i)=EX2, i=1,2,3,…,n. Without losing generality, we suppose that EX1(i)=EX1. The expectation of output stream can be calculated as (10)EAI=1n∑i=1nEX1iX2i=1nEX1∑i=1nEX2i=EX1EX2.By (9) and (10), (7) is satisfied. Thus, the random error can be calculated by (8) as follows: (11)VarAI=1nEX1EX2-EX12EX22+1n2∑i=1n∑j≠iRijX1RijX2.Hence, the variance of output stream in the case of AI is determined by the expectations and autocorrelation coefficients of input streams.


## 2.4. AI Affection Evaluation

In order to evaluate how much AI affects the random error, we propose differential variance, denoted byDV, where DV=Var(AI)-Var(BI). As suggested in [4], the variance of output stream in the case of BI can be calculated by (12)VarBI=EBI1-EBIn.Then we have the following theorem.Theorem 3.
The range of DV is as follows:(13)E2BI-EBIn⩽DV⩽n-1nEBI-E2BI.Proof.
See our prior work [17].According to Theorem3, the upper bound of DV is nonnegative and the lower bound of DV is nonpositive. Thus, DV can be positive, which indicates that the improper use of AS will result in the increase of random error. On the other hand, DV can be negative, which indicates that the proper use of AS will reduce random error. Therefore, we get the following conclusions.(i)
Since the random error in the case of AI can be less than that in the case of BI, the random error reduction scheme based on AS is feasible.(ii)
Since the random error in the case of AI can be greater than that in the case of BI, it is important to select proper AS to avoid this situation.


## 3. Random Error Reduction Scheme

In the last section, we find that the proper use of AS is able to reduce the random error for stochastic computation. On the basis of that conclusion, we will discuss how to employ ASs as input streams for the combinational stochastic circuit to reduce the random error.


### 3.1. Combinational Stochastic Circuit

For any combinational stochastic circuit, the relationship between input streams and output stream can be expressed by(14)Zi=∑l1l2⋯lkAl1l2⋯lkX1il1X2il2⋯Xkilk,where Al1,k is a constant integer and lr∈{0,1}, 1⩽r⩽k. For convenience of illustration, we denote l1,k by the subscript l1l2⋯lk. The formulation Al1,kX1(i)l1X2(i)l2⋯Xk(i)lk, where Al1,k≠0, is called a product term and denoted by Pl1,ki. Then, (14) can be rewritten as Z(i)=∑l1,k∈SpPl1,ki, where Sp=l1,k:Al1,k≠0. For the product term Pl1,ki, if lr=1, Xr is called a factor of Pl1,ki. Let M(r) denote the set of subscripts of product terms that have Xr as a factor; that is, M(r)=l1,k:lr=1,l1,k∈Sp. Similarly, let N(l1,k) denote the set of subscripts of input streams that are factors of Pl1,ki; that is, N(l1,k)=r:lr=1,1⩽r⩽k.Definition 4.
An input streamXr is called a positive input stream (PIS), if it satisfies (15)∑l1,k∈MrPl1,kiXri⩾0,∀X1i,X2i,…,Xr-1i,Xr+1i,…,Xki.The set of subscripts of PISs in stochastic circuit is denoted by Spis.Example 5.
Consider the stochastic circuit with Boolean function as follows:Z(i)=X1(i)∧X2(i)∨X3(i), and we have (16)Zi=X1iX2i1-X3i+X1iX2iX3i+X1i1-X2iX3i+1-X1iX2iX3i+1-X1i1-X2iX3i,which can be rewritten in the form of (14) as (17)Zi=X1iX2i+X3i-X1iX2iX3i.
There are three product terms andZ(i)=P110i+P001i-P111i. X1 is a factor of P110i and P111i, X2 is a factor of P110i and P111i, and X3 is a factor of P001i and P111i. Therefore, M(1)={110,111}, M(2)={110,111}, and M(3)={001,111}. Meanwhile, P110i has X1 and X2 as factors, P001i has X3 as a factor, and P111i has X1, X2, and X3 as factors. Hence, N(110)={1,2}, N(001)={3}, and N(111)={1,2,3}.In order to see whetherX1 is a PIS, by (17), we have (18)∑l1,3∈M1Pl1,3iX1i=X2i-X2iX3i=0,X2i=0,X3i=0,1,X2i=1,X3i=0,0,X2i=0,X3i=1,0,X2i=1,X3i=1.∀X2(i), X3(i), (∑l1,3∈M(1)Pl1,3i)/X1(i)⩾0. Thus, (15) is satisfied, and X1 is a PIS. Similarly, X2 and X3 are also PISs. Spis for the stochastic circuit in Example 5 is {1,2,3}.


### 3.2. Mathematical Model Based on MCAS and BS

Definition 6.
If a bit streamX has the following properties: (19)Xi=1,1⩽i⩽nEX,0,else,where n is the length of X, it is called an MCAS.
For instance, an MCAS withn=8 and EX = 3/8 is as follows: 1, 1, 1, 0, 0, 0, 0, 0.Consider the combinational stochastic circuit with thek input streams X1,X2,…,Xk and an output stream Z. In order to indicate the sequence type for each input stream, we introduce the state vector V=(V1,V2,…,Vk), where (20)Vr=MCAS,ifXrisanMCAS,BS,ifXris  a  BS.There are totally 2k possible states forV. For instance, if k=2, the four possible states are follows: (MCAS, MCAS), (MCAS, BS), (BS, BS), and (BS, MCAS). The expectation and variance of output stream Z, when state vector isV, are denoted by E(V) and Var(V), respectively.As discussed in Section2.3, in order to guarantee that the arithmetic computed by the combinational stochastic circuit, when state vector isV, is the same as that in the case of BI,V should satisfy (21)EV=EBI.On the premise of (21), if the state vectorV satisfies (22)VarV⩽VarBI,then the random error is not greater than that in the case of BI. Thus, the state vectorV satisfying (21) and (22) represents a random error reduction scheme for the combinational stochastic circuit.In order to describe the properties of state vectorV, we define the following notations. Let Sm denote the set of subscripts of input streams that are MCASs; that is, Sm={r:Vr=MCAS}. Let Sl1,k denote the set of subscripts of input streams that are MCASs and factors of Pl1,ki; that is, Sl1,k=r:Vr=MCAS,r∈Nl1,k. Let Spm denote the set of subscripts of product terms, of which at least one factor is an MCAS; that is, Spm=l1,k:Nl1,k∩Sm≠∅,l1,k∈Sp. Let Spb denote the set of subscripts of product terms whose factors are all BSs; that is, Spb=l1,k:Nl1,k∩Sm=∅,l1,k∈Sp. For instance, in Example 5, assuming that the state vector V=(MCAS,BS,BS), then Sm=1, S110=1, S001=∅, S111={1}, Spm={110,111}, and Spb={001}. We also denote by S the cardinal of the set S. Using the above notations, we have the following lemmas and theorems.Lemma 7.
For any combinational stochastic circuit, if the state vectorV satisfies (23)Sl1,k⩽1,∀l1,k∈Sp,then one has that E(V)=E(BI).Proof.
See AppendixA.Lemma 8.
Two input streamsX1 and X2, which are both MCASs, have the following properties: (24)∑i=1n∑j≠iEX1i=nn-1EX1,(25)∑i=1n∑j≠iEX2j=nn-1EX2,(26)∑i=1n∑j≠iEX1iEX2j⩽nn-1EX1EX2.Proof.
See AppendixB.Theorem 9.
For any combinational stochastic circuit, if the state vectorV satisfies (27)Sm=1,then one has E(V)=E(BI), and VarV⩽Var(BI).Proof.
See AppendixC. Lemmas 7 and 8 will be used in the proof.Theorem 10.
For any combinational stochastic circuit, if the state vectorV satisfies (28)Sm⊆Spis,(29)Sl1,k⩽1,∀l1,k∈Sp,then one has E(V)=E(BI), and Var(V)⩽Var(BI).Proof.
See AppendixD. Lemmas 7 and 8 will be used in the proof.Theorems9 and 10 give two different sufficient conditions for the state vector satisfying (21) and (22), respectively. On the basis of the two theorems, we will propose the random error reduction scheme for any combinational stochastic circuit in the next subsection.


### 3.3. Random Error Reduction Scheme Based on MCAS and BS

In this subsection, we illustrate how to get the state vectorV which represents the random error reduction scheme based on MCAS and BS for any combinational stochastic circuit. Specific steps are stated in Algorithm 1.Algorithm 1:Random error reduction scheme based on MCAS and BS.
Requrie: The combinational stochastic circuit implementing arithmetic;
Ensure: The state vector V representing the random error reduction scheme;
(1) Express the relationship between input streams and output stream in the form of (14).
(2) Obtain Spis. If Spis is a null set, go to step (3), otherwise, skip step (3) and go to step (4).
(3) If Spis is a null set, we determine which input streams are specified as MCASs and obtain
Sm by the following criteria: (a) Eq. (27) should be satisfied, i.e., only one input stream is
specified as MCAS; (b) on the premise of (a), let Spm be maximal. Then, we skip step (4) and
go to step (5).
(4) If Spis is not a null set, we determine which input streams are specified as MCASs and
obtain Sm by the following criteria: (a) Eq. (28) should be satisfied, i.e., only PISs are likely
to be specified as MCASs; (b) Eq. (29) should be satisfied, i.e., for each product term, at most
one factor is specified as MCAS; (c) on the premise of (a) and (b), let Spm be maximal.
Then, we go to step (5).
(5) The input streams not belonging to Sm are specified as BSs. From above, we determine
each input stream should be specified as MCAS or BS and obtain the state vectorV.Now, we prove that the state vectorV obtained from Algorithm 1 satisfies (21) and (22). Consider the following two cases: (I) Spis is a null set; (II) otherwise. In case (I), the valid steps are (1), (2), (3), and (5). From criterion (a) in step (3), (27) is satisfied. According to Theorem 9, the state vectorV obtained from these steps satisfies (21) and (22). In case (II), the valid steps are (1), (2), (4), and (5). From criterion (a) and (b) in step (4), (28) and (29) are satisfied. According to Theorem 10, the state vectorV obtained from these steps also satisfies (21) and (22). Therefore, in both cases, the state vectorV obtained from the corresponding steps satisfies (21) and (22).


### 3.4. Hardware Cost and Power Consumption

In conventional stochastic computation, the input streams for stochastic circuits are all BSs. However, in the proposed random error reduction scheme, some input streams are specified as MCASs. Different input streams are generated by different generators. The hardware structures of the MCAS generator and the BS generator are shown in Figure2. The MCAS generator consists of an n-bit comparator and an n-bit upcounter, while the BS generator consists of an n-bit comparator and an n-bit Liner Feedback Shift Register (LFSR), where 2n is the length of the input stream to be generated. In stochastic computation system, all the MCAS generators can share the same n-bit upcounter. By contrast, each BS generator requires a different n-bit LFSR. Thus, the total hardware cost of MCAS generators is usually lower than that of BS generators. That is to say, the proposed random error reduction scheme does not require any additional hardware cost.Figure 2
Hardware structure of the input stream generators: (a) MCAS generator; (b) BS generator.
(a)
(b)Moreover, due to a lower switching activity, MCAS generator will have less dynamic power consumption than BS generator, which is another inherent advantage of our random error reduction scheme.


## 3.1. Combinational Stochastic Circuit

For any combinational stochastic circuit, the relationship between input streams and output stream can be expressed by(14)Zi=∑l1l2⋯lkAl1l2⋯lkX1il1X2il2⋯Xkilk,where Al1,k is a constant integer and lr∈{0,1}, 1⩽r⩽k. For convenience of illustration, we denote l1,k by the subscript l1l2⋯lk. The formulation Al1,kX1(i)l1X2(i)l2⋯Xk(i)lk, where Al1,k≠0, is called a product term and denoted by Pl1,ki. Then, (14) can be rewritten as Z(i)=∑l1,k∈SpPl1,ki, where Sp=l1,k:Al1,k≠0. For the product term Pl1,ki, if lr=1, Xr is called a factor of Pl1,ki. Let M(r) denote the set of subscripts of product terms that have Xr as a factor; that is, M(r)=l1,k:lr=1,l1,k∈Sp. Similarly, let N(l1,k) denote the set of subscripts of input streams that are factors of Pl1,ki; that is, N(l1,k)=r:lr=1,1⩽r⩽k.Definition 4.
An input streamXr is called a positive input stream (PIS), if it satisfies (15)∑l1,k∈MrPl1,kiXri⩾0,∀X1i,X2i,…,Xr-1i,Xr+1i,…,Xki.The set of subscripts of PISs in stochastic circuit is denoted by Spis.Example 5.
Consider the stochastic circuit with Boolean function as follows:Z(i)=X1(i)∧X2(i)∨X3(i), and we have (16)Zi=X1iX2i1-X3i+X1iX2iX3i+X1i1-X2iX3i+1-X1iX2iX3i+1-X1i1-X2iX3i,which can be rewritten in the form of (14) as (17)Zi=X1iX2i+X3i-X1iX2iX3i.
There are three product terms andZ(i)=P110i+P001i-P111i. X1 is a factor of P110i and P111i, X2 is a factor of P110i and P111i, and X3 is a factor of P001i and P111i. Therefore, M(1)={110,111}, M(2)={110,111}, and M(3)={001,111}. Meanwhile, P110i has X1 and X2 as factors, P001i has X3 as a factor, and P111i has X1, X2, and X3 as factors. Hence, N(110)={1,2}, N(001)={3}, and N(111)={1,2,3}.In order to see whetherX1 is a PIS, by (17), we have (18)∑l1,3∈M1Pl1,3iX1i=X2i-X2iX3i=0,X2i=0,X3i=0,1,X2i=1,X3i=0,0,X2i=0,X3i=1,0,X2i=1,X3i=1.∀X2(i), X3(i), (∑l1,3∈M(1)Pl1,3i)/X1(i)⩾0. Thus, (15) is satisfied, and X1 is a PIS. Similarly, X2 and X3 are also PISs. Spis for the stochastic circuit in Example 5 is {1,2,3}.


## 3.2. Mathematical Model Based on MCAS and BS

Definition 6.
If a bit streamX has the following properties: (19)Xi=1,1⩽i⩽nEX,0,else,where n is the length of X, it is called an MCAS.
For instance, an MCAS withn=8 and EX = 3/8 is as follows: 1, 1, 1, 0, 0, 0, 0, 0.Consider the combinational stochastic circuit with thek input streams X1,X2,…,Xk and an output stream Z. In order to indicate the sequence type for each input stream, we introduce the state vector V=(V1,V2,…,Vk), where (20)Vr=MCAS,ifXrisanMCAS,BS,ifXris  a  BS.There are totally 2k possible states forV. For instance, if k=2, the four possible states are follows: (MCAS, MCAS), (MCAS, BS), (BS, BS), and (BS, MCAS). The expectation and variance of output stream Z, when state vector isV, are denoted by E(V) and Var(V), respectively.As discussed in Section2.3, in order to guarantee that the arithmetic computed by the combinational stochastic circuit, when state vector isV, is the same as that in the case of BI,V should satisfy (21)EV=EBI.On the premise of (21), if the state vectorV satisfies (22)VarV⩽VarBI,then the random error is not greater than that in the case of BI. Thus, the state vectorV satisfying (21) and (22) represents a random error reduction scheme for the combinational stochastic circuit.In order to describe the properties of state vectorV, we define the following notations. Let Sm denote the set of subscripts of input streams that are MCASs; that is, Sm={r:Vr=MCAS}. Let Sl1,k denote the set of subscripts of input streams that are MCASs and factors of Pl1,ki; that is, Sl1,k=r:Vr=MCAS,r∈Nl1,k. Let Spm denote the set of subscripts of product terms, of which at least one factor is an MCAS; that is, Spm=l1,k:Nl1,k∩Sm≠∅,l1,k∈Sp. Let Spb denote the set of subscripts of product terms whose factors are all BSs; that is, Spb=l1,k:Nl1,k∩Sm=∅,l1,k∈Sp. For instance, in Example 5, assuming that the state vector V=(MCAS,BS,BS), then Sm=1, S110=1, S001=∅, S111={1}, Spm={110,111}, and Spb={001}. We also denote by S the cardinal of the set S. Using the above notations, we have the following lemmas and theorems.Lemma 7.
For any combinational stochastic circuit, if the state vectorV satisfies (23)Sl1,k⩽1,∀l1,k∈Sp,then one has that E(V)=E(BI).Proof.
See AppendixA.Lemma 8.
Two input streamsX1 and X2, which are both MCASs, have the following properties: (24)∑i=1n∑j≠iEX1i=nn-1EX1,(25)∑i=1n∑j≠iEX2j=nn-1EX2,(26)∑i=1n∑j≠iEX1iEX2j⩽nn-1EX1EX2.Proof.
See AppendixB.Theorem 9.
For any combinational stochastic circuit, if the state vectorV satisfies (27)Sm=1,then one has E(V)=E(BI), and VarV⩽Var(BI).Proof.
See AppendixC. Lemmas 7 and 8 will be used in the proof.Theorem 10.
For any combinational stochastic circuit, if the state vectorV satisfies (28)Sm⊆Spis,(29)Sl1,k⩽1,∀l1,k∈Sp,then one has E(V)=E(BI), and Var(V)⩽Var(BI).Proof.
See AppendixD. Lemmas 7 and 8 will be used in the proof.Theorems9 and 10 give two different sufficient conditions for the state vector satisfying (21) and (22), respectively. On the basis of the two theorems, we will propose the random error reduction scheme for any combinational stochastic circuit in the next subsection.


## 3.3. Random Error Reduction Scheme Based on MCAS and BS

In this subsection, we illustrate how to get the state vectorV which represents the random error reduction scheme based on MCAS and BS for any combinational stochastic circuit. Specific steps are stated in Algorithm 1.Algorithm 1:Random error reduction scheme based on MCAS and BS.
Requrie: The combinational stochastic circuit implementing arithmetic;
Ensure: The state vector V representing the random error reduction scheme;
(1) Express the relationship between input streams and output stream in the form of (14).
(2) Obtain Spis. If Spis is a null set, go to step (3), otherwise, skip step (3) and go to step (4).
(3) If Spis is a null set, we determine which input streams are specified as MCASs and obtain
Sm by the following criteria: (a) Eq. (27) should be satisfied, i.e., only one input stream is
specified as MCAS; (b) on the premise of (a), let Spm be maximal. Then, we skip step (4) and
go to step (5).
(4) If Spis is not a null set, we determine which input streams are specified as MCASs and
obtain Sm by the following criteria: (a) Eq. (28) should be satisfied, i.e., only PISs are likely
to be specified as MCASs; (b) Eq. (29) should be satisfied, i.e., for each product term, at most
one factor is specified as MCAS; (c) on the premise of (a) and (b), let Spm be maximal.
Then, we go to step (5).
(5) The input streams not belonging to Sm are specified as BSs. From above, we determine
each input stream should be specified as MCAS or BS and obtain the state vectorV.Now, we prove that the state vectorV obtained from Algorithm 1 satisfies (21) and (22). Consider the following two cases: (I) Spis is a null set; (II) otherwise. In case (I), the valid steps are (1), (2), (3), and (5). From criterion (a) in step (3), (27) is satisfied. According to Theorem 9, the state vectorV obtained from these steps satisfies (21) and (22). In case (II), the valid steps are (1), (2), (4), and (5). From criterion (a) and (b) in step (4), (28) and (29) are satisfied. According to Theorem 10, the state vectorV obtained from these steps also satisfies (21) and (22). Therefore, in both cases, the state vectorV obtained from the corresponding steps satisfies (21) and (22).


## 3.4. Hardware Cost and Power Consumption

In conventional stochastic computation, the input streams for stochastic circuits are all BSs. However, in the proposed random error reduction scheme, some input streams are specified as MCASs. Different input streams are generated by different generators. The hardware structures of the MCAS generator and the BS generator are shown in Figure2. The MCAS generator consists of an n-bit comparator and an n-bit upcounter, while the BS generator consists of an n-bit comparator and an n-bit Liner Feedback Shift Register (LFSR), where 2n is the length of the input stream to be generated. In stochastic computation system, all the MCAS generators can share the same n-bit upcounter. By contrast, each BS generator requires a different n-bit LFSR. Thus, the total hardware cost of MCAS generators is usually lower than that of BS generators. That is to say, the proposed random error reduction scheme does not require any additional hardware cost.Figure 2
Hardware structure of the input stream generators: (a) MCAS generator; (b) BS generator.
(a)
(b)Moreover, due to a lower switching activity, MCAS generator will have less dynamic power consumption than BS generator, which is another inherent advantage of our random error reduction scheme.


## 4. Case Study

For better understanding of the random error reduction scheme based on MCAS and BS, we take several typical stochastic circuits as case studies. We assume that all the input streams are uncorrelated.


### 4.1. Case Study 1: AND Gate

In this case study, we illustrate how to get the random error reduction scheme whenSpis is not a null set. An AND gate in stochastic logic implements a binary operator multiplication as z=x1x2. We obtain the state vectorV satisfying (21) and (22) from the steps given in Algorithm 1.(1)
The relationship between input streams and output stream can be written asZ(i)=X1(i)X2(i).(2)
∀X2(i), (∑l1,2∈M(1)Pl1,2i)/X1i=X2(i)⩾0, and, ∀X1(i), (∑l1,2∈M(1)Pl1,2i)/X2(i)=X1(i)⩾0. Thus, by Definition 4, X1 and X2 are PISs, and Spis={1,2}. Since Spis is not a null set, skip step (3) and go to step (4).(3)
SinceSpis is not a null set, this step is skipped.(4)
SinceX1 and X2 are PISs, by criterion (a), both of them are likely to be specified as MCASs. Hence, as shown in the first column of Table 1, Sm is chosen from the following candidates: {1}, {2}, and {1,2}. For each candidate of Sm, we get all the corresponding Sl1,2 and see whether criterion (b) is satisfied. If it is, the candidate is valid. For example, if Sm={1}, S11={1}. Moreover, there is only one product term P11i, and Sp={11}. Then, ∀l1,2∈Sp, Sl1,2⩽1, which is equivalent to (29). Criterion (b) is satisfied and the set {1} is a valid candidate. Similarly, the set {2} is also a valid candidate. However, if Sm={1,2}, S11=1,2, which is opposed to (29). Thus, criterion (b) is not satisfied and the set {1,2} is not a valid candidate. For each valid candidate, we get the corresponding Spm. As shown in the last column of Table 1, when Sm = {1} or {2}, Spm is maximal, and criterion (c) is satisfied. From above, the set Sm satisfying all the criteria in step (4) can be written as Sm={1}or{2}. Without loss of generality, we set Sm={1}, and X1 is specified as an MCAS. Then, go to step (5).(5)
X2 is specified as a BS. Thus, the state vector V=(MCAS,BS).Table 1
Candidates information in case study 1.
Sm
S
11
Valid
S
p
m
S
p
m
{
1
}
{
1
}
Yes
{
11
}
1
{
2
}
{
2
}
Yes
{
11
}
1
{
1,2
}
{
1,2
}
No
Not concerned
Not concerned


### 4.2. Case Study 2: XOR Gate

In this case study, we illustrate how to get random error reduction scheme whenSpis is a null set. An XOR gate in stochastic logic implements the arithmetic as follows: z=x1+x2-2x1x2. We obtain the state vectorV satisfying (21) and (22) from the steps given in Algorithm 1.(1)
The relationship between input streams and output stream can be written in the form of (14) as Z(i)=X1(i)+X2(i)-2X1(i)X2(i).(2)
IfX2i=1, (∑l1,2∈M(1)Pl1,2i)/X1(i)=-1, and if X1(i)=1, (∑l1,2∈M(1)Pl1,2i)/X2(i)=-1. Thus, by Definition 4, X1 and X2 are not PISs, and Spis is a null set. Then, go to step (3).(3)
By criterion (a), only one ofX1 and X2 can be specified as an MCAS. Hence, as shown in the first column of Table 2, Sm is chosen from the following candidates: {1} and {2}. For each candidate, we get the corresponding Spm. As shown in the last column of Table 2, when Sm = {1} or {2}, Spm is maximal, and criterion (b) is satisfied. From above, the set Sm satisfying all the criteria in step (4) can be written as Sm={1}or{2}. Without loss of generality, we set Sm={1}, and X1 is specified as an MCAS. Then, skip step (4) and go to step (5).(4)
SinceSpis is a null set, this step is skipped.(5)
X2 is specified as a BS. Thus, the state vector V=(MCAS,BS).Table 2
Candidates information in case study 2.
Sm
S
10
S01
S
11
S
p
m
S
p
m
1
1
Null
{
1
}
10,11
2
2
Null
2
{
2
}
01,11
2


### 4.3. Case Study 3: Stochastic Logic Implementing Bernstein Polynomial

In this case study, we illustrate how to get the random error reduction scheme for the stochastic logic implementing Bernstein polynomial with coefficients in the unit interval. A Bernstein polynomial of degreek, denoted by Bk(x), is defined by Bk(x)=∑i=0kbikixi(1-x)k-i, where each bi is a constant coefficient. In [4], Qian et al. propose the stochastic circuit for the Bernstein polynomial with coefficients in the unit interval, which is shown in Figure 3. For a Bernstein polynomial of degree k, there are 2k+1 input streams: X1,X2,…,X2k+1, with the following properties: EX1=b0, EX2=b1,…,EXk+1=bk, and EXk+2=EXk+3=⋯=EX2k+1=x. For simplicity, we will take the Bernstein polynomial of degree 2 as an example, where (30)Zi=X1i1-X4i1-X5i+X2iX4i1-X5i+X2i1-X4iX5i+X3iX4iX5i.We obtain the state vectorV satisfying (21) and (22) from the steps given in Algorithm 1. (1)
The relationship between input streams and output stream can be rewritten in the form of (14) as (31)Zi=X1i-X1iX4i-X1iX5i+X1iX4iX5i+X2iX4i+X2iX5i-2X2iX4iX5i+X3iX4iX5i.(2)
∀X2(i),X3(i),X4(i),X5(i), (∑l1,5∈M(1)Pl1,5i)/X1(i)=1-X4(i)-X5(i)+X4(i)X5(i)⩾0. Thus, by Definition 4, X1 is a PIS. Similarly, X2 and X3 are also PISs, and Spis={1,2,3}. Since Spis is not a null set, skip step (3) and go to step (4).(3)
SinceSpis is not a null set, this step is skipped.(4)
SinceX1, X2, and X3 are PISs, by criterion (a), all of them are likely to be specified as MCASs. Hence, as shown in the first column of Table 3, Sm is chosen from the following candidates: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, and {1,2,3}. For each candidate of Sm, we get all the corresponding Sl1,5 and see whether criterion (b) is satisfied. If it is, the candidate is valid. For example, if Sm={1}, then S10000=1, S10010={1}, S10001={1}, S10011={1}, S01010=∅, S01001=∅, S01011=∅, and S00111=∅. Moreover, there are eight product terms, and Sp={10000,10010,10001,10011,01010,01001,01011, 00111}. Hence, ∀l1,5∈Sp,  Sl1,5⩽1, which is equivalent to (29). Criterion (b) is satisfied and the set {1} is a valid candidate. Similarly, the other sets in the first column of Table 3 are also valid candidates. For each valid candidate, we get the corresponding Spm. As shown in the last column of Table 3, when Sm={1,2,3}, Spm is maximal, and criterion (c) is satisfied. From above, the set Sm satisfying all the criteria in step (4) can be written as Sm={1,2,3}. Then, go to step (5).(5)
X4 and X5 are specified as BSs. Thus, the state vector V=(MCAS,MCAS,MCAS,BS,BS).Table 3
Candidates information in case study 3.
Sm
S
10000
S
10010
S
10001
S10011
S01010
S
01001
S
01011
S
00111
Valid
S
p
m
{1}
{
1
}
{
1
}
{
1
}
{
1
}
Null
Null
Null
Null
Yes
4
{2}
Null
Null
Null
Null
{
2
}
{
2
}
{
2
}
Null
Yes
3
{3}
Null
Null
Null
Null
Null
Null
Null
{
3
}
Yes
1
{2,3}
Null
Null
Null
Null
{
2
}
{
2
}
{
2
}
{
3
}
Yes
4
{1,2}
{
1
}
{
1
}
{
1
}
{
1
}
{
2
}
{
2
}
{
2
}
Null
Yes
7
{1,3}
{
1
}
{
1
}
{
1
}
{
1
}
Null
Null
Null
{
3
}
Yes
5
{1,2,3}
{
1
}
{
1
}
{
1
}
{
1
}
{
2
}
{
2
}
{
2
}
{
3
}
Yes
8Figure 3
Stochastic logic implementing Bernstein polynomial.Similarly, we can get the state vectorV satisfying (21) and (22) for the stochastic circuit implementing Bernstein polynomial of degree n, which can be written as V=(MCAS,MCAS︸n+1,BS,BS).


## 4.1. Case Study 1: AND Gate

In this case study, we illustrate how to get the random error reduction scheme whenSpis is not a null set. An AND gate in stochastic logic implements a binary operator multiplication as z=x1x2. We obtain the state vectorV satisfying (21) and (22) from the steps given in Algorithm 1.(1)
The relationship between input streams and output stream can be written asZ(i)=X1(i)X2(i).(2)
∀X2(i), (∑l1,2∈M(1)Pl1,2i)/X1i=X2(i)⩾0, and, ∀X1(i), (∑l1,2∈M(1)Pl1,2i)/X2(i)=X1(i)⩾0. Thus, by Definition 4, X1 and X2 are PISs, and Spis={1,2}. Since Spis is not a null set, skip step (3) and go to step (4).(3)
SinceSpis is not a null set, this step is skipped.(4)
SinceX1 and X2 are PISs, by criterion (a), both of them are likely to be specified as MCASs. Hence, as shown in the first column of Table 1, Sm is chosen from the following candidates: {1}, {2}, and {1,2}. For each candidate of Sm, we get all the corresponding Sl1,2 and see whether criterion (b) is satisfied. If it is, the candidate is valid. For example, if Sm={1}, S11={1}. Moreover, there is only one product term P11i, and Sp={11}. Then, ∀l1,2∈Sp, Sl1,2⩽1, which is equivalent to (29). Criterion (b) is satisfied and the set {1} is a valid candidate. Similarly, the set {2} is also a valid candidate. However, if Sm={1,2}, S11=1,2, which is opposed to (29). Thus, criterion (b) is not satisfied and the set {1,2} is not a valid candidate. For each valid candidate, we get the corresponding Spm. As shown in the last column of Table 1, when Sm = {1} or {2}, Spm is maximal, and criterion (c) is satisfied. From above, the set Sm satisfying all the criteria in step (4) can be written as Sm={1}or{2}. Without loss of generality, we set Sm={1}, and X1 is specified as an MCAS. Then, go to step (5).(5)
X2 is specified as a BS. Thus, the state vector V=(MCAS,BS).Table 1
Candidates information in case study 1.
Sm
S
11
Valid
S
p
m
S
p
m
{
1
}
{
1
}
Yes
{
11
}
1
{
2
}
{
2
}
Yes
{
11
}
1
{
1,2
}
{
1,2
}
No
Not concerned
Not concerned


## 4.2. Case Study 2: XOR Gate

In this case study, we illustrate how to get random error reduction scheme whenSpis is a null set. An XOR gate in stochastic logic implements the arithmetic as follows: z=x1+x2-2x1x2. We obtain the state vectorV satisfying (21) and (22) from the steps given in Algorithm 1.(1)
The relationship between input streams and output stream can be written in the form of (14) as Z(i)=X1(i)+X2(i)-2X1(i)X2(i).(2)
IfX2i=1, (∑l1,2∈M(1)Pl1,2i)/X1(i)=-1, and if X1(i)=1, (∑l1,2∈M(1)Pl1,2i)/X2(i)=-1. Thus, by Definition 4, X1 and X2 are not PISs, and Spis is a null set. Then, go to step (3).(3)
By criterion (a), only one ofX1 and X2 can be specified as an MCAS. Hence, as shown in the first column of Table 2, Sm is chosen from the following candidates: {1} and {2}. For each candidate, we get the corresponding Spm. As shown in the last column of Table 2, when Sm = {1} or {2}, Spm is maximal, and criterion (b) is satisfied. From above, the set Sm satisfying all the criteria in step (4) can be written as Sm={1}or{2}. Without loss of generality, we set Sm={1}, and X1 is specified as an MCAS. Then, skip step (4) and go to step (5).(4)
SinceSpis is a null set, this step is skipped.(5)
X2 is specified as a BS. Thus, the state vector V=(MCAS,BS).Table 2
Candidates information in case study 2.
Sm
S
10
S01
S
11
S
p
m
S
p
m
1
1
Null
{
1
}
10,11
2
2
Null
2
{
2
}
01,11
2


## 4.3. Case Study 3: Stochastic Logic Implementing Bernstein Polynomial

In this case study, we illustrate how to get the random error reduction scheme for the stochastic logic implementing Bernstein polynomial with coefficients in the unit interval. A Bernstein polynomial of degreek, denoted by Bk(x), is defined by Bk(x)=∑i=0kbikixi(1-x)k-i, where each bi is a constant coefficient. In [4], Qian et al. propose the stochastic circuit for the Bernstein polynomial with coefficients in the unit interval, which is shown in Figure 3. For a Bernstein polynomial of degree k, there are 2k+1 input streams: X1,X2,…,X2k+1, with the following properties: EX1=b0, EX2=b1,…,EXk+1=bk, and EXk+2=EXk+3=⋯=EX2k+1=x. For simplicity, we will take the Bernstein polynomial of degree 2 as an example, where (30)Zi=X1i1-X4i1-X5i+X2iX4i1-X5i+X2i1-X4iX5i+X3iX4iX5i.We obtain the state vectorV satisfying (21) and (22) from the steps given in Algorithm 1. (1)
The relationship between input streams and output stream can be rewritten in the form of (14) as (31)Zi=X1i-X1iX4i-X1iX5i+X1iX4iX5i+X2iX4i+X2iX5i-2X2iX4iX5i+X3iX4iX5i.(2)
∀X2(i),X3(i),X4(i),X5(i), (∑l1,5∈M(1)Pl1,5i)/X1(i)=1-X4(i)-X5(i)+X4(i)X5(i)⩾0. Thus, by Definition 4, X1 is a PIS. Similarly, X2 and X3 are also PISs, and Spis={1,2,3}. Since Spis is not a null set, skip step (3) and go to step (4).(3)
SinceSpis is not a null set, this step is skipped.(4)
SinceX1, X2, and X3 are PISs, by criterion (a), all of them are likely to be specified as MCASs. Hence, as shown in the first column of Table 3, Sm is chosen from the following candidates: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, and {1,2,3}. For each candidate of Sm, we get all the corresponding Sl1,5 and see whether criterion (b) is satisfied. If it is, the candidate is valid. For example, if Sm={1}, then S10000=1, S10010={1}, S10001={1}, S10011={1}, S01010=∅, S01001=∅, S01011=∅, and S00111=∅. Moreover, there are eight product terms, and Sp={10000,10010,10001,10011,01010,01001,01011, 00111}. Hence, ∀l1,5∈Sp,  Sl1,5⩽1, which is equivalent to (29). Criterion (b) is satisfied and the set {1} is a valid candidate. Similarly, the other sets in the first column of Table 3 are also valid candidates. For each valid candidate, we get the corresponding Spm. As shown in the last column of Table 3, when Sm={1,2,3}, Spm is maximal, and criterion (c) is satisfied. From above, the set Sm satisfying all the criteria in step (4) can be written as Sm={1,2,3}. Then, go to step (5).(5)
X4 and X5 are specified as BSs. Thus, the state vector V=(MCAS,MCAS,MCAS,BS,BS).Table 3
Candidates information in case study 3.
Sm
S
10000
S
10010
S
10001
S10011
S01010
S
01001
S
01011
S
00111
Valid
S
p
m
{1}
{
1
}
{
1
}
{
1
}
{
1
}
Null
Null
Null
Null
Yes
4
{2}
Null
Null
Null
Null
{
2
}
{
2
}
{
2
}
Null
Yes
3
{3}
Null
Null
Null
Null
Null
Null
Null
{
3
}
Yes
1
{2,3}
Null
Null
Null
Null
{
2
}
{
2
}
{
2
}
{
3
}
Yes
4
{1,2}
{
1
}
{
1
}
{
1
}
{
1
}
{
2
}
{
2
}
{
2
}
Null
Yes
7
{1,3}
{
1
}
{
1
}
{
1
}
{
1
}
Null
Null
Null
{
3
}
Yes
5
{1,2,3}
{
1
}
{
1
}
{
1
}
{
1
}
{
2
}
{
2
}
{
2
}
{
3
}
Yes
8Figure 3
Stochastic logic implementing Bernstein polynomial.Similarly, we can get the state vectorV satisfying (21) and (22) for the stochastic circuit implementing Bernstein polynomial of degree n, which can be written as V=(MCAS,MCAS︸n+1,BS,BS).


## 5. Simulation Results and Comparison

The simulation platform for evaluating the random error in stochastic circuits is shown in Figure4. Assume that the stochastic circuit is with k input streams X1,X2,…,Xk, which represent k variables for the corresponding arithmetic. We randomly select 5000 sample points of EX1,EX2,…,EXk from [0, 1]. These sample points are used in both stochastic computation and float-point computation. The random error can be measured by the average of the absolute difference between the stochastic computation results (SCR) and the floating-point computation results (FCR) on these sample points. In order to simulate the generic and common circumstance, we used the same LFSR for all the input stream generators and just change the seed value. The size of LFSR equals the square root of length of input streams. For the sake of illustrating that the random error reduction scheme is valid for any input stream length, the length of input streams is chosen to be 2m, where m=5,6,…,12. We compare the random error based on MCAS and BS with that based on other sequences on the following benchmarks.(1)
AND gate: the random error reduction scheme based on MCAS and BS for the stochastic logic AND gate is as follows:X1 is specified as an MCAS, and X2 is specified as a BS. For comparison, as shown in Figure 5, we give the simulation results in the following cases: (a) X1 is an MCAS, and X2 is a BS; (b) X1 and X2 are both BSs [4]; (c) X1 and X2 are both FRSs [14]; (d) X1 and X2 are DBSs as illustrated in [3].(2)
XOR gate: the random error reduction scheme based on MCAS and BS for the stochastic logic XOR gate is as follows:X1 is specified as an MCAS, and X2 is specified as a BS. For comparison, as shown in Figure 6, we give the simulation results in the following cases: (a) X1 is an MCAS, and X2 is a BS; (b) X1 and X2 are both BSs [4]; (c) X1 and X2 are both FRSs [14].(3)
Stochastic logic implementing Bernstein polynomial: two Bernstein polynomials are referred to in [4]. The one used for approximating gamma correction function is of degree 6 and with the following coefficients: b0=0.0955, b1=0.7207, b2=0.3476, b3=0.9988, b4=0.7017, b5=0.9695, and b6=0.9939. The other used for synthesizing polynomials is of degree 3 and with the coefficients as follows: b0=0.2500, b1=0.6250, b2=0.3750, and b3=0.7500. We denote the stochastic circuit implementing the former Bernstein polynomial by B1 and the later by B2. As illustrated in case study 3, the random error reduction scheme based on MCAS and BS for B1 is as follows: X1,X2,…,X7 are specified as MCASs, and X8,X9,…,X13 are specified as BSs. Meanwhile, that for B2 is as follows: X1,X2,…,X5 are specified as MCASs, and X6,X7,…,X9 are specified as BSs. As shown in Figure 7, we give the simulation results for B1 in three cases: (a) X1,X2,…,X7 are MCASs, and X8,X9,…,X13 are BSs; (b) all the input streams are BSs; (c) all the input streams are FRSs. Similarly, as shown in Figure 8, we also give out the simulation results for B2 in three cases: (a) X1,X2,…,X5 are MCASs, and X6,X7,…,X9 are BSs; (b) all the input streams are BSs [4]; (c) all the input streams are FRSs [14].Figure 4
Simulation platform for evaluating random error.Figure 5
Simulation results for AND gate.Figure 6
Simulation results for XOR gate.Figure 7
Simulation results forB1.Figure 8
Simulation results forB2.From the simulation results for the above benchmarks, we have the following conclusions.(i)
For all the benchmarks, the random error based on MCAS and BS is smaller than that based on BS with any sequence length. Hence, the proposed random error reduction scheme is effective for those stochastic circuits.(ii)
In benchmark 1, DBSs have the best performance. However, they are only suitable for this specific stochastic circuit. By comparison, the proposed MCASs and BSs can be used in any combination stochastic circuit.(iii)
FRSs have better performance than MCASs and BSs in benchmarks 1 and 2, and vice versa in benchmark 3. Considering the difficulties in hardware generation for FRSs, the proposed MCASs and BSs, easily generated by hardware, have much wider applications.(iv)
For all the benchmarks, the random error reduction scheme based on MCAS and BS is valid for any input stream length. Hence, the proposed random error reduction scheme has no length constraints.


## 6. Conclusion

In this paper, we propose a general random error analysis method based on AS. According to the analysis results, we find it feasible to reduce random error for stochastic computation by using proper ASs as input streams. Then, we present the random error reduction scheme based on MCAS and BS, which has the advantages of wide applications, easy hardware implementation, and flexible length. Both the theoretical analysis and simulation results confirm the effectiveness of the proposed scheme. In the future work, we will further study the features of ASs and apply them into more complex stochastic circuits.



---

*Source: 4038765-2017-10-08.xml*