The Logic of Random Pulses: Stochastic Computing

Recent developments in the field of electronics has brought about nano-scale
devices, whose operation can only be described in probabilistic terms. In contrast
with the conventional "deterministic" computing that has dominated the digital
world for decades, we investigate a fundamentally different technique that is
probabilistic by nature, namely, stochastic computing (SC). In SC, numbers are
represented by bit-streams of 0's and 1's, in which the probability of seeing
a 1 denotes the value of the number. The main benefit of SC is that complex
arithmetic computation can be performed by simple logic circuits. For example,
a single (logic) AND gate performs multiplication.

In this dissertation we begin with a comprehensive survey of SC and its applications.
We highlight its main challenges, which include long computation time
and low accuracy, as well as the lack of a general design method. We then address
all the important challenges. We introduce a new SC circuit design method,
called STRAUSS, that generates efficient SC circuits for arbitrary target functions.
We then address the problems arising from correlation among stochastic
numbers (SNs). In particular, we show that correlation, contrary to general belief,
can sometimes serve as a resource in SC circuit design. We also show that unlike
conventional circuits, SC circuits can tolerate high error rates and are hence useful
in many new applications that involve non-deterministic behavior of the underlying
circuitry. Finally, we show how SC's properties can be exploited in the design
of efficient image-processing circuits that are useful in retinal implants.