Design and Analysis of Efficient Maximum/Minimum Circuits for Stochastic Computing

In stochastic computing (SC), a real-valued number is represented by a stochastic bit stream, encoding its value in the probability of obtaining a one. This leads to a significantly lower hardware effort for various functions and provides a higher tolerance to errors (e.g., bit flips) compared to binary radix representation. The implementation of a stochastic max/min function is important for many areas where SC has been successfully applied, such as image processing or machine learning (e.g., max pooling in neural networks). In this work, we propose a novel shift-register-based architecture for a stochastic max/min function. We show that the proposed circuit has significantly higher accuracy than state-of-the-art architectures for uncorrelated bit streams at comparable hardware costs. Moreover, we analytically proof the correctness of the proposed circuit and provide a new error analysis, based on the individual bits of the stochastic streams. Interestingly, the analysis reveals that for a certain practical bit stream length a finite optimal shift register length exists and it allows to determine the optimal length.