
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Novel Residue Arithmetic Hardware Algorithm Using a SignedDigit Number Representation
Shugang WEI Kensuke SHIMIZU
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E83D
No.12
pp.20562064 Publication Date: 2000/12/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Theory/Models of Computation Keyword: symmetric residue number system, signeddigit(SD) number representation, SD adder, binary modulo m adder tree, modulo m multiplication,
Full Text: PDF>>
Summary:
A novel residue arithmetic algorithm using radix2 signeddigit (SD) number representation is presented. By this representation, memoryless residue arithmetic circuits using SD adders can be implemented. Conventional residue arithmetic circuits have been designed using binary number arithmetic system, but the carry propagation arises which limits the speed of arithmetic operations in residue modules. In this paper, a pdigit radix2 SD number system is introduced to simplify the residue operation. For a modulus m, 2^{p}1 m 2^{p}+2^{p1}1, in a residue number system (RNS), the modulo m addition is performed by using two pdigit SD adders, one for the addition and one for the residue operation. Thus, the modulo m addition time is independent of the word length of operands. When m=2^{p} or m= 2^{p} 1, the modulo m addition is implemented by using only one SD adder. Moreover, a modulo m multiplier is constructed using a binary modulo m SD adder tree, and the modulo m multiplication can be performed in a time proportional to log _{2} p. The VHDL implementation method for the presented algorithm is also discussed. The design and simulation results of some residue arithmetic circuits show that high speed residue arithmetic circuits can be obtained by the presented algorithms.

