Modular Multipliers Using a Modified Residue Addition Algorithm with Signed-Digit Number Representation
Shugang Wei · 2009
Abstract — In this paper, we present multipliers using a modified addition algorithm modulo m with a signed-digit(SD) number representation where m = 2 n − 1, 2 n or 2 n + 1. To simplify an SD modular adder, new addition rules are proposed for generating the intermediate sum and carry with a binary number representation. By using the new codes for intermediate sum and carry and the end-around carry architecture, the proposed modulo m addition requires less hardware and short delay time for the residue addition than previous methods. A modulo m multiplier can be implemented by a binary modulo m adder tree. Compared to previous work, the circuit area and delay time of the multiplier are improved by 21 % and 30%, respectively. Keywords: Residue number system, Signed-Digit Number, Residue arithmetic, modular addition, modular multiplier 1