Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

7.2 RESIDUE NUMBER SYSTEM CONVERSION

7.2.1 Introduction

The residue number system (RNS) is not widely used in practice; nevertheless, in some specific classes of algorithms, the RNS can provide an important speed-up by replacing operations on large numbers by parallel processing on small size operands ([GAR1959], [SZA1967]). A residue number system is defined as a system of s natural numbers {m_i} called moduli, the greatest of which is generally denoted m. The RNS representation of a given integer N, with respect to {m_i}, is the vector r, the components of which, called residues modulo-m_i, are the s successive remainders of the integer divisions N/m_i. Residues are denoted

The least common multiple (lcm) of a system {m_i} is the range, denoted M, of the related RNS system, that is, the quantity of different integers that can be represented in the system. Whenever a system {m_i} consists of pairwise prime moduli, the associated RNS is said to be nonredundant. Selection of moduli, as small as possible, maximizes the speed of RNS arithmetic operations, as operand sizes never exceed the size of greatest modulus m. The most important drawbacks of the RNS are the complexity of overflow detection and the conversion process. Whenever those operations are not critical in the overall complexity of the application at hand, the RNS is fully justified.

7.2.2 Base-B to RNS Conversion

The most intuitive ...