Moduli selection in RNS for efficient VLSI implementation

In this paper, we carry out a study on an important issue concerning the use of residue numbers in the design of digital systems, namely, the moduli selection. Based on a new formulation of the Chinese remainder theorem and the efficient residue-to-binary (R/B) converters designed therefrom, we propose a guideline for the selection of the low-cost moduli sets for different dynamic ranges. These sets consist of the low-cost moduli of the form 2ⁿ, ( 2ⁿ-1) or (2ⁿ + 1), which can offer simplified modulo adders and multipliers. It is shown that for medium dynamic ranges (less than 22 bits), the three-moduli set {2ⁿ,2ⁿ + 1,2ⁿ - 1} is the most efficient one in terms of the design of a complete RNS system. On the other hand, for large dynamic ranges (equal to or larger than 22 bits), the general-moduli set in the form (2ⁿ, 2ⁿ + 1,2ⁿ - 1,2ⁿ ±1,...,2ⁿ, ±1), with a length greater than three, is the most efficient one. These results provide the possibility of a wide range of applications of the residue number system in the design of DSP, telecommunication and cryptography systems.