Stochastic Circuit Synthesis by Cube Assignment

Stochastic computing (SC) is an unconventional computation paradigm, in which digital circuits are adopted to compute on stochastic bit streams. The value represented by a stochastic bit stream is the probability of obtaining a one in the stream. Stochastic circuits are highly tolerant to bit flip errors. Compared to the conventional binary computing, SC can perform complicated arithmetic computations with simple circuits. With such advantages, SC has been applied in a number of applications. This raises recent interests in developing general methods to automatically synthesize stochastic circuits. However, the synthesis problem is different from and more complicated than the traditional logic synthesis, due to the special solution space of the problem. In this paper, we propose a novel method to synthesize a high-quality stochastic circuit. Our method is based on assigning cubes (i.e., product terms) to the on-set of the Boolean function. A heuristic breadth-first search algorithm is proposed to search for a good stochastic circuit in the solution space. Our experimental results showed that the proposed method can produce better circuits than the state-of-the-art methods.