Number Conversions between RNS and Mixed-Radix Number System Based on Modulo (2p - 1) Signed-Digit Arithmetic

摘要

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 m_i = (2 ^p _i - 1) are used as the moduli and the modulo m _i addition and multiplication can be performed by an end-around-carry SD adder and a binary modulo m_i SD adder tree, respectively. Therefore, the modulo m_i addition time is independent of the word length of operands, and the modulo m_i multiplication can be performed in a time proportional to log₂ p_i. 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