IEEE Circuits and Systems Magazine - Q1 2021 - 36

[151]. First, numbers can be represented as sequences of
bits through stochastic representations. Since most FHE
schemes support batching as an acceleration technique
for the processing of multiple bits in parallel, one can
map stochastic representations to batching slots to efficiently implement multiplications and scaled additions
(19). Unlike traditional Boolean circuits, the amount of
bits required for stochastic computing is flexible, allowing for a flexible correspondence between the unencrypted and encrypted domains.
The homomorphic systems based on SC in [151] target
the approximation of continuous functions. These functions are first approximated with Bernstein polynomials
in a black-box manner. Hence, function development can
take place with traditional programming paradigms, providing an automated way to produce FHE circuits. A stochastic sequence of bits is encrypted in a single cryptogram. It was concluded that stochastic representations
are more widely applicable, while a fixed-point binary
representation provides better performance [151].
A quantum computer efficiently factors an arbitrary
integer [153], which makes the widely used RSA publickey cryptosystem insecure. It is based on reducing this
computation to a special case of a mathematical problem known as the Hidden Subgroup Problem (HSP)
[154], [155] (HSP is a group theoretic generalization of
the problem of periodicity determination). The Abelian
quantum hidden subgroup algorithms in [153], [156] are
based on the Quantum Fourier Transform (QFT). The
QFT, the counterpart to the Discrete Fourier Transform
(DFT) in the classical computing model, is the basis of
many quantum algorithms [152], [157], [158].
V. Conclusions and future research
This survey covers the main types of nonconventional
arithmetic from a holistic perspective, highlighting their
practical interest. Several different classes of nonconventional arithmetic are reviewed, such as LNS, RNS,
SC and HDC, and their usage in various emergent applications, with different features and based on new
technologies, is discussed. We show the importance
of nonconventional number representation and arithmetic not only to implement fast, reliable, and efficient
systems but also to shape the usage of the technology.
For example, SC is useful for FHE, enabling the processing of multiple bits in parallel for batching, but is also
important to perform approximate computing on nanoscale memristor crossbars and to overcome the deep
pipelining nature of AQFP logic devices. Similarly, RNS is
suitable for machine learning and cryptographic applications, but it is also quite useful to mitigate the instability of biochemical reactions for DNA-based computing
and to reduce the cost of arithmetic systems for inte36

IEEE CIRCUITS AND SYSTEMS MAGAZINE

grated nanophotonics technology. Hyperdimensional
representation and arithmetic, inspired by brain-like
computing, adopt high-dimensional binary vectors to
introduce randomness and achieve reliability in HDC.
This type of nonconventional number representation offers a strong basis for in-memory computation, being a
promising candidate for taking advantage of the physical attributes of nanoscale memristive devices to perform online training, classification and prediction.
One of the main conclusions that can be drawn from
this survey is that the investigation of nonconventional
arithmetic must take into account all the dimensions of
the systems, which includes not only computer arithmetic theory but also technology advances and the
demands of emergent applications. For example, the results of further investigations of the randomness characteristics of SC and HDC may also impact applications
that might benefit from approximate computations [66].
At the technological level, these classes of arithmetic
may benefit from the ease of nanotechnologies in generating the required random numbers [79] while improving the robustness to noise [171]. The efficiency offered
by SC and HDC results in important savings both in
terms of the integration area and hardware cost, which
make these number representations suitable for the development of autonomous cyberphysical [161] and Internet of Things (IoT) processors [73].
Further research on LNS and RNS should target difficult operations in the respective domains, namely,
addition and subtraction in the logarithmic domain
and division and comparison in the RNS domain. The
accuracy and the implementation cost under different
technologies are key aspects for the practical usage
of this nonconventional arithmetic. In that respect,
the development of tools such as the Computing with
the Residue Number System (CRNS), which automates
the design of systems based on RNS for exploring the
increasing parallelism available in computing devices,
is also important [162]. The redundancy of the RRNS
and the randomness of SC and HDC make them suitable for improving reliability [113] and supporting the
heterogeneous integration of multiple emerging nanotechnologies [106]. Moreover, it will be very useful to
investigate efficient converters between nonconventional systems that allow them to be used together in
different components of heterogeneous systems and
for different applications.
New paradigms of computation will also become the
focus of research on nonconventional computer arithmetic. The less disruptive, more straightforward path of
research is the combination of nonconventional arithmetic with approximate computing. While for SC, this combination is natural, for the other nonpositional number
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