A New Residue Number System with 5-Moduli Set: {2(2q), 2(q) +/- 3, 2(q) +/- 1}

作者：Ahmadifar H; Jaberipur G^*

来源：Computer Journal, 2015, 58(7): 1548-1565.

DOI：10.1093/comjnl/bxu084

• Chinese remainder theorem
• computer arithmetic
• residue number systems
• reverse RNS conversion

Residue number system (RNS) parameterized moduli sets almost always contain a power-of-two modulo (e.g. 2(iq)), where the corresponding computation channel and residue generator are the most efficient when compared with other non-power-of-two moduli (e.g. 2(jq) +/- delta). Furthermore, inclusion of a power-of-two modulo leads to efficient use of the new Chinese remainder theorem for reverse conversion. However, few reverse conversion schemes and modulo-(2(q) +/- 3) arithmetic operators have been recently reported for F ={2(q) +/- 3, 2(q) +/- 1}, where it appears that devising similar reverse conversion schemes for the more useful 5-moduli set F boolean OR {2(iq)} is too challenging that no such moduli set has been yet proposed. Therefore, we propose the arithmetically balanced moduli set P ={2(2q), 2(q) +/- 3, 2(q) +/- 1} and study the corresponding problems of binary to RNS conversion and the reverse, where adder-only solutions (with neither costly read-only-memories nor multipliers) are presented. We state and prove some lemmas and theorems to obtain at the required infinite geometric series to express the multiplicative inverses as power-of-two polynomials. Different groupings of moduli are investigated and more feasible cases are set aside for realization of four reverse converters showing cost/speed trade-off that are evaluated analytically and by synthesis. Both forward and reverse converters are designed and implemented via multi-operand addition realized via fast parallel architectures.

• 出版日期2015-7