Page 486 - DSP Integrated Circuits

11.4 Residue Number Systems 471

For a given integer number x and moduli set {rail, i = 1, 2,..., p, we may find
the elements (rj, r2,..., r p) of the RNS by the relation

where q{, m{, and r^ are integers, x can be written as

The advantage of RNS is that the arithmetic operations (+, -, *) can be per-
formed for each residue independently of all the other residues. Individual arithmetic
operations can thus be performed by independent operations on the residue. The Chi-
2
nese remainder theorem is of fundamental importance in residue arithmetic.
Theorem 11.1

where © is a general arithmatic operation, module m^, such as
addition, subtraction, or multiplication.
As can be seen, each residue digit is dependent only on the corresponding
residue digits of the operands.

EXAMPLE 11.5
Use a residue number system with the modules 5, 3, and 2 to add the numbers 9
and 19 and multiply the numbers 8 and 3. Also determine the number range.
The number range is D = 5 • 3 • 2 = 30

A number range corresponding to more than 23 bits can be obtained by choos-
ing the following mutual prime factors 29,27, 25,23,19. Then D = m\- m^ -...- m§
23
= 8, 554, 275 > 2 . Each residue is represented in the common weighted binary
number system as a 5-bit number.
RNS is restricted to fixed-point operations and gives no easily obtainable
information about the size of the numbers. For example, it is not possible to deter-
mine directly which is the closest number— i.e., comparison of numbers, overflow
detection, and quantization operations are difficult. Hence, in order to round off an

2
- After the Chinese mathematician Sun-Tsii, AD 100.