MVLSC Home · Issue Contents · Forthcoming Papers
Characterizing Polynomial Arithmetic with Stochastic Circuits
Patrick Holec, Weikang Qian, Marc Riedel and Ivo Rosenberg
In this work, we outline a novel algorithm for the computation of real coefficient polynomials using stochastic circuits. Also, we prove that there exists restricted regions in polynomial space that no stochastic circuit can compute. Through the use of the fundamental theorem of algebra, we can obtain a finite set of roots 𝑟1, . . . , 𝑟1 ∈ ℂ for a target polynomial 𝑃𝑖(𝑡) of the 𝑖th degree. If a polynomial contains roots exclusive to the accessible regions of the complex plane, a stochastic circuit is guaranteed to exist which represents the target polynomial as 𝐴 · 𝑃(𝑡) where 0 < 𝐴 < 1 or, in certain cases, 𝐴 = 1. When these solutions exist, the number of logic gates and the overall delay of the circuit is significantly less than those described by previous solutions to this problem.
Keywords: Stochastic computing, probabilistic circuits, polynomials