Implementation issues of the two-level residue number system with pairs ofconjugate moduli

One of the most important considerations when designing residue number syst ems (RNS's) is the choice of the moduli set. This is due to the fact that t he dynamic range of the system, its speed, as well as its hardware complexi ty, depend on both the forms as well as the number of moduli chosen. In thi s paper, a new class of multimoduli RNS systems based on sets of forms {2(n 1) - 1, 2(n1) + 1, 2(n2) - 1, 2(n2) + 1, ..., 2(nL) + 1, 2(nL) + 1} is pres ented. The moduli 2(ni) -1 and 2(ni) + 1 are called conjugates of each othe r. The new RNS systems that rely on pairs of conjugate moduli result in har dware-efficient two-level implementations for the weighted-to-RNS and RNS-t o-weighted conversions, achieve very large dynamic ranges, and imply fast a nd efficient RNS processing. When compared with conventional systems of the same number of moduli and the same dynamic range, the proposed new systems offer the following benefits: 1) hardware savings of 25 to 40% for the wei ghted-to-RNS conversion and 2) a reduction of over 80% in the complexity of the final Chinese remainder theorem (CRT) involved in the RNS-to-weighted conversion. Thus, significant compromises between large dynamic ranges, fas t internal processing, and low complexity are achieved by the new systems.