Number Conversions between RNS and Mixed-Radix Number System Based on Modulo (2p - 1) Signed-Digit Arithmetic
Shugang Wei · 2005
In this paper, new hardware algorithms converting the numbers of a residue number system (RNS) into and from the mixed-radix number system(MRNS) using a radix-two signed-digit (SD) arithmetic circuits are presented. In each residue digit of the RNS integers mi= (2pi- 1) are used as the moduli and the modulo miaddition and multiplication can be performed by an end-around-carry SD adder and a binary modulo miSD adder tree, respectively. Therefore, the modulo miaddition time is independent of the word length of operands, and the modulo mimultiplication can be performed in a time proportional to log2pi. An efficient method for calculating a multiplicative inverse number of a modulus is also presented by using the SD arithmetic. By the use of the fast SD arithmetic circuits, number converters of RNS-to-MRNS and MRNS-to-RNS can be implemented with shorter delay time than that using a binary number system