## 2 Related Work
### Stochastic Computing  
SC, as an innovative computing paradigm, can represent a numerical value between 0 and 1 through the use of random bit streams. The probability of the logical 1 appearing within a random sequence corresponds to its representation result; for instance, the random sequence 01100010 contains five zeros and three ones; hence, the probability value of this  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Observation Window of MSD Algorithm** & **3-Symbol** & **5-Symbol** & **7-Symbol** \\ \hline Number of real multiplications & 400 N & 2624 N & 14,592 N \\ \hline Number of real additions & 376 N & 2528 N & 14,208 N \\ \hline \hline \end{tabular}
\end{table}
Table 1: The computational complexity of the MSD algorithm.  
sequence is determined to be three-eighths. As probability values are characterized by finite-length sequences, errors are inevitably present. In accordance with the Law of Large Numbers, as the length of a random sequence increases, the precision of its probability value tends to increase.  
The conversion between binary data and random sequences is important in the realm of SC. This is primarily accomplished through stochastic number generators (SNGs), and the conversion equation can be expressed as  
\[X(t)=\left\{\begin{array}{rl}&1\quad x\geq n(t)\\ &0\quad x<n(t)\end{array}\right. \tag{19}\]  
where \(X(t)\) is the stochastic sequence, \(n(t)\) is the random number, and \(x\) denotes the binary data to be converted.  
Figure 3 illustrates the structure of the SNG, which encompasses a pseudo-random number generator and a comparator. Through comparing the input binary data with the generated random numbers, the binary data are subsequently transformed into a stream of single-bit data. Furthermore, SC requires a stochastic number converter (SNC) to transform random bit sequences into binary data. The equation for the SNC can be expressed as  
\[x=\frac{1}{L}\sum_{t=1}^{L}X(t) \tag{20}\]  
where \(L\) is the sequence length. The SNC can be implemented through a counter in hardware circuits. When the logical 1 appears in the random sequence, the counter increments by one; otherwise, the counter remains unchanged.  
Beyond the basic SNG and SNC units, the logical implementation of numerical operations is also of paramount importance in the context of SC. Given that SC involves performing computations through single-bit streams, numerous intricate operations traditionally executed in binary computing can be effectively implemented using logic gate circuits within the SC framework. As an illustration, a multiplier can be dramatically simplified to an AND gate.  
Figure 4 shows the stochastic multiplier based on the AND gate. Consider two random bit streams, \(X_{1}\) and \(X_{2}\), with probability values of \(\frac{6}{8}\) and \(\frac{4}{8}\), respectively. When these two bit streams pass through an AND gate circuit, the output is the logical 1 only when both \(X_{1}\) and \(X_{2}\) are the logical 1 at the same position. Consequently, the AND gate circuit can perform stochastic multiplication. Compared to binary computing, the complexity is substantially lower in the SC multiplier. As a result, the SC offers a significant reduction in hardware resource overhead.  
Figure 4 also illustrates a limitation of stochastic multipliers. The SC can only provide an approximate result, which is a random variable centered around the precise result as its expectation. As the length of the sequences increases and the correlation between the two sequences decreases, the variance in calculation will gradually diminish. Therefore, it is necessary to strike a balance between computational efficiency and precision, which is a pivotal consideration in SC design.  
Figure 3: Stochastic number generator.