Fast residue arithmetic multipliers based on signed-digit number system

Fast residue arithmetic multipliers based on a radix-2 signed-digit (SD) number are presented. 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, and the modulo m addition time is independent of the word length of operands. We propose two kinds of modulo m multipliers which are constructed using a modulo m SD adder and a binary tree of the adders and the modulo m multiplication are performed in a time proportional to p and log₂p, respectively. 16-digit residue arithmetic multiplier circuits have been designed using VHDL, and the results show that high speed residue arithmetic circuits can be implemented