IEEE Circuits and Systems Magazine - Q1 2021 - 20

stochastic bitstreams so as to achieve a trade-off between
precision and bitstream length.
The following sections show how SC can be applied
to design invertible logic on the current CMOS technology, based on Boltzmann machines [78], and to homomorphic encryption.
D. Hyperdimensional Representation
and Arithmetic
The circuits of the brain are composed of billions of
neurons, with each neuron typically connected to up to
10, 000 other neurons. This situation leads to more than
100 trillion modifiable synapses [69]. High-dimensional
modeling of neural circuits not only supports artificial
neural networks but also inspires parallel distributed
processing. It explores the properties of high-dimensional spaces, with applications in, for example, classification, pattern identification and discrimination.
HDC, inspired by the brain-like computing paradigm,
is supported by random high-dimensional vectors [70].
It looks at computing with very wide words, represented
by high-dimensional binary vectors, which are typically
called hyperdimensional vectors, with a dimensionality
on the order of thousands of bits. It is an alternative to
Support Vector Machines (SVMs) and CNN-based approaches for supervised classification. With Associative
Memory (AM), a pattern X can be stored using another
pattern A as the address, and X can be retrieved later
from the memory address A. However, X can also be
retrieved by addressing the memory with a pattern Al
similar to A.
The high number of bits in HDC are not used to improve the precision of the information to represent,
as it would be difficult to give an exact meaning to a
10,000-bit vector in the same way a traditional computing model does. Instead, they ensure robustness and
randomness by i) being tolerant to errors and component failure, which come from redundancy in the representation (many patterns mean the same thing and
thus are considered equivalent) and ii) having highly
structured information, as in the brain, to deal with the
arbitrariness of the neural code.
HDC starts with vectors drawn randomly from hyperspace and uses AM to store and access them. A space
of n =10,000-dimensional vectors and independent and
identically distributed (i.i.d.) components drawn from a
normal distribution with mean n = 0 can be considered
as a typical example. Points in the space can be viewed
as corners of a 10,000-dimensional unit hypercube, for
which the distance d ^ X, Y h between two vectors X, Y is
expressed using the Hamming metric. It corresponds
to the length of the shortest path between the corner
points along the edges (the distance is often normalized
20

IEEE CIRCUITS AND SYSTEMS MAGAZINE

to the number of dimensions so that the maximum distance, when the values of all bits differ, is 1). Assuming
that the distance ^k h from any point of the space to a
randomly drawn point follows a binomial distribution,
with p ^0 h = 0.5 and p ^1 h = 0.5:
f ^kh = c

10, 000
10, 000!
m 0.5 k 0.5 10,000 - k =
0.5 10,000
k
k! ^10, 000 - k h !
(32)

with mean n = 10, 000 # 0.5 = 5, 000 and variance VAR =
10, 000 # 0.5 # 0.5 = 2, 500 (the standard deviation v = 50).
This means that if vectors are randomly selected, they
differ by approximately 5,000 bits, with a normalized distance of 0.5. These vectors are therefore considered " unrelated " [70]. Although it is intuitive that half the space
has a normalized distance from a point of less than 0.5,
this statement is not true if we observe that it is only less
than a thousand-millionth closer than 0.47 and another
thousand-millionth farther than 0.53. This distribution
provides robustness to the hyperdimensional space, given that " nearly " all of the space is concentrated around
the 5,000 mean distance (0.5). Hence, a 10,000-bit vector
representing an entity may see a large number of bits,
e.g., a third, changing their values, by errors or noise,
and the resulting vector still identifies the correct one
because it is far from any " unrelated " vector.
The vector representation of patterns enables the use
of the body of knowledge on vector and matrix algebra to
implement hyperdimensional arithmetic. For example,
the componentwise addition of a set of vectors results
in a vector with the same dimensionality that may represent that set. The sum-vector values can be normalized to yield a mean vector. Moreover, a binary vector
can be obtained by applying a threshold. If there are no
duplicated elements in a set, the sum-vector is a possible
representative of the set that makes up the sum [70].
Another important arithmetic operation in HDC is
vector multiplication, which, as for SC with BR, can be
implemented with the bitwise logic XNOR operator (see
Fig. 8(c)). Reverting the order of the BR from ^1, -1 h to
^0, 1 h, the ordinary multiplication of binary vectors X
and Y can be implemented by the bitwise eXclusive-OR
(XOR). It is easy to show that XOR is commutative and
that each vector is its own inverse ^ X ) X = 0 h, where 0
is the unit vector ^ X ) 0 = X h . Multiplication can be considered as a mapping of points in the space: multiplying
vector X by M maps the vector into a new vector X M as
far from X as the number of 1s in M (represented by < M < )
(33). If M is a random vector, with half of the bits taking,
on average, a value 1, X M is " unrelated " to X, and it can
be said that multiplication randomizes it.
d^ X M , X h = < X M ) X < = < M ) X ) X < = < M <

(33)

FIRST QUARTER 2021

IEEE Circuits and Systems Magazine - Q1 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2021