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

摘要

One of the most important considerations when designing residue number systems (RNSs) is the choice of the moduli set; this is due to the fact that the dynamic range of the system, its speed, as well as its hardware complexity, depend on both the forms as well as the number of moduli chosen; In this paper, a new class of multimoduli RNSs based on sets of forms {2/sup n(1)/-1, 2/sup n(1)/+1, 2/sup n2/-1, 2/sup n(2)/+1, /spl middot//spl middot//spl middot/, 2/sup n(L)/-1, 2/sup n(L)/+1} is presented. The moduli 2/sup n(i)/-1 and 2/sup n(i)/+1 are called conjugates of each other. The new RNSs that rely on pairs of conjugate moduli result in hardware-efficient two-level implementations for the weighted-to-RNS and RNS-to-weighted conversions, achieve very large dynamic ranges, and imply fast and 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 weighted-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, fast internal processing, and low complexity are achieved by the new systems.