IEEE Circuits and Systems Magazine - Q1 2021 - 15

Once a is known, the basis extension is finally computed with (17).
x 2, i =

/ M 1, i G

i=1

M -1,1i

m 1, i

x i H m 1,i - aM 1

(17)
m 2, i

Performing efficient RNS arithmetic requires the selection of the most suitable moduli set for the problem
at hand. The size of the set and the width of the moduli
are mainly defined by the dynamic range and the desired parallelism. Features usually considered to select
the moduli are i) the efficiency of the modular arithmetic for each channel (the term " channel " is usually adopted to designate a residue and the modular arithmetic
units associated with it), which typically leads to values
near a power of two; ii) the balancing of the moduli set,
since the slowest channel defines the overall performance; and iii) the cost of the reverse converters, with
some moduli sets allowing efficient arithmetic channels
at the cost of more complex reverse converters and
others tailored to the result in simple reverse conversion circuits due to the mathematical relations between
the moduli [45]. Altogether, the most used moduli sets
are composed of modulus 2 v ! k, with v ! " n, 2n , and
k ! " -1, 0, +1 , [35].
Alternative binary codings can be explored for modular arithmetic in each RNS channel. Thermometer Coding (TC) and One-Hot Coding (OHC) are among some of
the most used ones [46]. The value of a number in TC
is expressed by the number of 1's in the string of bits
[47], which means that it is a nonpositional redundant
number representation. Typically, for simplicity, a runlength of 1's is placed at one end of the string. For the
OHC, the only valid combinations in a string of bits are
those with only a single bit '1' and all the others '0'. For
the OHC, the bit '1' position directly indicates the value
of the number. k and k + 1 bits are required to represent
integers between 0 and k in TC and OHC, respectively.
For example, for k = 7, the number 4 can be represented
in TC by the stream " 0001111, " while in the OHC, it can
be represented by the combination " 00010000. " The TC
is often used in Digitalto-Analog Converters (DACs), as
it leads to less glitching than binary-weighted codings.
The OHC is used in Finite State Machines (FSMs), as it
avoids the use of decoders: a single '1' bit directly identifies the state. The TC and OHC codings are most advantageous for RNS moduli that result in small and medium
dynamic ranges [46]-[48].
Several RNS-based processors have been developed,
for example, a fully programmable RISC Digital Signal
Processor (RDSP) [167] and hardware/software RNSbased units [49]. The RDSP is a 5-stage pipeline processor with the RNS-based AU partially located in the third
FIRST QUARTER 2021

and fourth pipeline stages, as depicted in Fig. 6. The
most popular 3-moduli set " 2 n - 1, 2 n, 2 n + 1 , is balanced
by extending the binary channel to 2 2n; the reverse converter is distributed by the two aforementioned pipeline stages, while, for the multiply-accumulate (MAC)
unit, the multiplier is located in the third stage, and the
accumulator operates in parallel to the load/store units
in the fourth pipeline stage. The experimental results
obtained for the RDSP in the CMOS 250 nm technology
show that not only are the circuit area and the power
consumption significantly lower but also a speedup is
obtained in comparison to a similar DSP using a data
path based on binary arithmetic.
An AU based on a moduli set that comprises a larger modulus 2 k and all the other moduli of type 2 n - 1
assumes that the selected moduli fit the typical word
size of a Central Processing Unit (CPU), for example,
64 bits [49]. Adopting a hardware-software approach,
RNS adders, subtractors and multipliers are implemented in the hardware, while the reverse conversion and
nonlinear operations are implemented in the software.
A minimum set of instructions includes not only forward
conversion (residue), modular addition (add_m) and
modular multiplication (mult_m) but also instructions
that operate on positional number representations,
such as add, sub, AND and SHR (logical shift right). It
supports changing the dynamic range at runtime in a
simple manner, which in turn can result in a reduction in
both power consumption and execution time.
Although the RNS was proposed mainly for fixedpoint arithmetic, it has also been used for floating-point
units [50], [51]. To operate on FP numbers, the mantissa
and the exponent are individually converted and processed in the RNS domain. For example, to multiply two
FP numbers, both mantissas are multiplied and exponents are added in the RNS domain.
A variant of RNS, the Redundant Residue Number
System (RRNS) addresses different purposes [52] but
is mainly used for error detection and correction. Since
the residues are independent of each other, introducing
redundant moduli in the set of original (information)
moduli, usually called the legitimate, the representation can be extended to the illegitimate range to detect
residue errors and, in some cases, correct them. If a result falls into the illegitimate range, it can be concluded
that i) one or more residue digit errors exist as long
as the number of residue digit errors is not more than
twice the number of redundant moduli and ii) errors
can be corrected by subtracting the error digits from
the residue digits, assuming that the number of residue
errors does not exceed the number of redundant moduli [35]. For example, applying the RRNS 3-moduli set
" 2 n - 1, 2 n + 1, 2 n + 1 , and considering the legitimate
IEEE CIRCUITS AND SYSTEMS MAGAZINE

IEEE Circuits and Systems Magazine - Q1 2021

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