IEEE Circuits and Systems Magazine - Q1 2021 - 14

" X

mi

M=

1 # i # n , is unique for any 0 # X 1 M,
n

% mi

(9)

in (12) is widely disseminated in the design of efficient
arithmetic, in particular for linear processing [35], [36].
X % Y 8 " x1 % y1

i=1

%:+,- ,)

The CRT asserts that there is a bijection, formally described in Lemma 2.
Lemma 2
Let m 1, f, m n be n pairwise co-prime integers and M =
% ni = 1 m i . The CRT asserts that there is a bijection between
Z M and Z m 1 # f # Z m n .
Z M ) Z m1 # f # Z mn .

(10)

Proof. Consider n = 2 and two co-prime numbers m 1, and
m 2 . The modular inverse m 1-1 = m 1-1 m 2 and m 2-1 = m 2-1 m 1
exist since m 1 and m 2 are co-prime numbers [165]. Thus,
the value Y satisfies the equation for X:
Y = x 1 m 2 m -2 1 + x 2 m 1 m -1 1

M = m1 # m2

since Y m 1 = x 1 and Y m 2 = x 2 .
It remains to be shown that no other solutions exist
modulo M, which means X / Y ( mod M ). By contradiction, it is assumed that ^ X ! Y h 1 M and X m i = Y m i ,
which means X - Y m i = 0, i = 1, 2. Hence, (X - Y ) is the
Least Common Multiple (LCM) of m i . However, this contradicts the fact that m i are pairwise co-prime; thus, the
LCM is M. We can represent an element of Z M by one
element of Z m 1 and one element of Z m 2 , and vice versa.
The CRT can now be proven for an arbitrary number
n (number of co-prime integers) m 1 1 # i # n by induction. Defining M i = M/m i and M i-1 = M i- 1 m i , the previous equation for Y becomes:
X=

n

/ x i # M i # M i-1

i=1

M

Y
and X is the unique solution in the ring Z M .
Moreover, for m 1, f, m n pairwise co-prime integers
and M = m 1 # f # m n , the CRT also asserts the following
ring isomorphism [33]:
Z M " Z m1 # f # Z mn
X " f ^ X h = ^ x 1, f x n h
= ^ X m 1, f X m nh,

(11)

which allows carrying the ring operations on the residues for each modulo independently.
Thus, RNS is a nonpositional number system based
on smaller residues, the quantity and range of which are
controlled by the chosen pairwise co-prime moduli set
[34]. Each residue corresponds to a " digit, " and " digits "
can be processed in parallel. The direct application of
RNS properties to addition and multiplication expressed
14

IEEE CIRCUITS AND SYSTEMS MAGAZINE

mn ,

, f, x n % y n

m1

(12)

RNS has been proposed mainly for fixed-point arithmetic, accommodating also numbers with signs in the
range 6- M/2 : M/2 h. The main limitation of RNS-based
arithmetic is related to the operations, such as division,
comparison, sign and overflow detection, which are difficult to implement with non-weighted number representations. These require a combination of the residues to
reach some type of positional representation, i.e., the
partial or complete application of the RNS-to-binary (reverse) conversion, supported by the CRT or the Mixed
Radix Conversion (MRC) [37], [38]. Although both approaches use modular operations, the CRT carries out
the computation in a single step over a large modular
sum X (M i = M/m i, M -i 1 m i is the multiplicative inverse of
M i , and a is an integer) (13).
X=

n

/ Mi

M -i 1

mi

n

xi

i=1

=
M

/ Mi

M -i 1

mi

x i - aM

(13)

i=1

On the other hand, the MRC uses shorter modulo arithmetic with an iterative procedure:
X = y 1 + m 1 # ^ y 2 + m 2 # ^ y 3 + m 3 # ^g hhh
y1 = x1
y 2 = ^ x 2 - y 1 h # m 1-1 m 2 m 2
y 3 = ^^ x 3 - y 1 h # m 1-1
g

m3

- y 2 h # m 2-1

m3 m3

(14)

Algorithms for RNS division [39], comparison [40], [41],
sign detection [42], scaling [43], and reduction [44] have
been proposed for specific moduli sets. Basis Extension
(BE) is often used in those algorithms to extend the representation of an RNS moduli set (often called a basis) S 1 to another S 2 . Consider the two bases S 1 = " m 1, 1, f, m 1,n 1 , and
n1
S 2 = " m 2, 1, f, m 2,n 2 , with dynamic ranges M 1 = % i =1 m 1, i
n2
and M 2 = % i =1 m 2, i , respectively (GCD (M 1, M 2) = 1) . If an
error of aM 1 is tolerated, the residues associated with the
second basis can be computed as in [44]:
x 2, i = X l

n1

m 2, i

=

/ M 1, i

M 1-,1i

i=1

m 1, i

xi

(15)
m 2, i

For applications that do not tolerate this error, a
method to perform the exact extension requires an
e x tra modulus (m e), with the corresponding residue x e = X m e , to enable the computation of a parameter [142]
a = ^ G X lH m e - x e h M -1 1

mi me

(16)
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
