IEEE Circuits and Systems Magazine - Q3 2020 - 20

Binary Inputs
(From Memory
Devices)

Stochastic
Sequences
Stochastic Number
Generator (SNG)
Array

Stochastic
Sequences
Stochastic
Computing
Circuits

Binary
Outputs
Probability
Estimators
(PEs)

Figure 1. Datapath of a stochastic computing system.

Figure 2. Stochastic encoding vs. rate coding. (a) Stochastic
unipolar encoding, (b) rate coding.

energy consumption. In addition, the costly SNGs and
PEs can account for a major part of the circuits in an
SC system [18].
To address this issue, we noticed that a stochastic
sequence can carry the information of a varying signal
with each bit encoding a value from the signal. This new
type of sequences is referred to as a dynamic stochastic
sequence (DSS). In a DSS, the sequence length encoding
each number is just 1 bit, so it can significantly improve
the performance and energy efficiency of a stochastic circuit. In this article, we present dynamic stochastic computing (DSC) using DSS's and discuss the efficient implementation of iterative accumulation-based computations,
including filtering, the Euler method for solving ordinary
differential equations (ODEs) and the gradient descent
(GD) algorithm in machine learning.

are '1's, so the probability of a '1' in the output sequence is
equal to the product of the probabilities of '1's of the two
input stochastic sequences, i.e., xy, whereas in conventional arithmetic, a multiplier requires a complex circuit.
Since numbers are represented by redundant random bits, a bit-flip usually incurs a relatively small error in the final result, so SC is fault-tolerant and robust
against moderate operational errors. However, if a bit
flip occurs at a more significant bit in a conventional circuit, it can introduce a large error [2], [3].
In fact, a stochastic sequence works in a similar manner to the rate coding [4] in a spiking neuron, as shown
in Fig. 2. With this coding, the frequency of spikes during
a time interval carries the information in a neuron [5],
similar to the stochastic encoding using the frequency
of the occurrence of '1' in SC. Inspired by the neuronal
coding, SC has been used to implement various machine
learning algorithms [6]-[17].
To achieve a high accuracy, however, a long sequence
is often required in SC due to stochastic fluctuations. A
long sequence in turn implies a high latency and a high

II. Background
Originally proposed in the 1960s, SC is intended to be a
low-cost alternative to conventional computing. In SC,
numbers are encoded by random binary bit streams or
stochastic sequences. The probability of each bit being '1' is considered to be the probability encoded by
a stochastic sequence and used in different mapping
schemes to encode numbers within different ranges [1].
Assume that x is the number to be encoded and that p
is the probability of a stochastic sequence. The simplest
mapping is to let x = p, i.e., the probability of the stochastic sequence is used to represent a real number within
[0,1]. This is referred to as the unipolar representation. In
order to expand the range to include negative values, the
bipolar representation takes a linear transformation of
the unipolar representation by x = ( p - 0.5 ) # 2, so that
the representation range is [-1, 1].
Recently, a sign-magnitude representation was proposed to expand the unipolar representation range by
adding an extra sign bit to a stochastic sequence [19]. The
same range is obtained as the bipolar -representation and

L
...010100101010110100...
N
p: Encoded Value
L
N : Number of '1's in the Sequence
p=

(a)
∆t

n (t ; t + ∆t)

A: Encoded Value
∆t
n (.): Number of Spikes in the Time Window
(b)

Siting Liu and Warren J. Gross are with the Department of Electrical and Computer Engineering, McGill University, Montreal, QC H3A 0E9, Canada, (e-mail:
siting.liu@mail.mcgill.ca; warren.gross@-mcgill.ca), Jie Han is with the Department of Electrical and Computer Engineering, University of Alberta, Edmonton,
AB T6G 1H9, Canada, (e-mail: jhan8@ualberta.ca).

IEEE CIRCUITS AND SYSTEMS MAGAZINE

THIRD QUARTER 2020

IEEE Circuits and Systems Magazine - Q3 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q3 2020