Residue Arithmetic with a Signed-Digit Number System

摘要

A new comcept on residue arithmetic based on a radix-2 signed-digit(SD) number system is presented, by which memoryless residue arithmetic circuits using SD adders can be implemented. Conventional residue arithmetic circuits have been designed using binary number arith-metic system, but the carry propagation arises which limits the speed of arithmetic operations in residue mod-ules. In this paper, a p-digit radix-2 SD number system is introduced to simplify the residue operation. For a given modulus m, 2~p - 1 <= m <= 2~p + 2~p-1 - 1, in a residue number system(RNS), the modulo m addition is performed by using one or two p-digit SD adders. Since the modulo m addition time is independent of the word length of operands, the high speed residue arithmetic can be achieved. A modulo m multiplier is designed by using the modulo m SD adder and some registers.