Designing Accurate and Low-Cost Stochastic Circuits

Stochastic computing (SC) is an unconventional computing approach that processes data represented by pseudo-random bit-streams called stochastic numbers (SNs). It enables arithmetic functions to be implemented by tiny, low-power logic circuits, and is highly error-tolerant. These properties make SC practical for applications that need massive parallelism or operate in noisy environments where conventional binary designs are too costly or too unreliable. SC has recently come to be seen as an attractive choice for tasks such as biomedical image processing and decoding complex error-correcting codes. Despite its desirable properties, SC has features that limit its usefulness, including insufficient accuracy and an inadequate design theory. Accuracy is especially vulnerable to correlation among interacting SNs and to the random fluctuations inherent in SC's data representation. This dissertation examines the major factors affecting accuracy using analytical and experimental approaches based on probability theory and circuit simulation, respectively. We devise methods to quantify the error effects in stochastic circuits by means of probabilistic transfer matrices and Bernouilli processes. These methods make it possible to compare the impact of errors on conventional and stochastic circuits under various conditions. We then analyze correlation in detail and show that correlation-induced errors can be reduced by the careful insertion of delay elements, a de-correlation technique called isolation. Noting that different logic functions can have the same stochastic behavior when constant SNs are applied to their inputs, we show how to partition logic functions into stochastic equivalence classes (SECs). We derive a procedure for identifying SECs, and apply SEC concepts to the synthesis and optimization of stochastic circuits. While addition, subtraction and multiplication have well-known and simple SC implementations, this is not true for division. We study stochastic division methods and propose a new type of stochastic divider that combines low cost with high accuracy. Finally, we turn to the design of general stochastic circuits and investigate a desirable property of SNs called monotonic progressive precision (MPP) whereby accuracy increases steadily with bit-stream length. We develop an SC design technique which produces results that are accurate and have good MPP. The dissertation concludes with some ideas for future research.