High-Speed Residue Arithmetic System Using Signed-Digit Number Representation

点击翻译按钮获取中文摘要

A novel residue arithmetic algorithm using radix-2 signed-digit(SD) number representation is presented. By the algorithm, 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. We introduced a p-digit radix-2 SD number system to simplify the residue operation. The proposed algorithm is also applied to the high reliable arithmetic system and the RSA public-key encryption processor.・ Based on the presented residue SD addition circuits, 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_2p.・ A fast residue checker for the error detection of arithmetic circuits has been presented. The residue checker consists of a number of residue arithmetic circuits such as adders, multipliers and binary-to-residue converters based on radix-two signed-digit(SD) number arithmetic. The proposed modulo m (m = 2^P ± 1) adder is designed with a p-digit SD adder, so that the modulo m addition time is independent of the word length of operands.・ A modulo m addition can be implemented by using two SD adders, one for SD addition and another for the modular operation with the complement of m,m^*. A modular multiplication is performed by repeating the modular shift and the modular addition operations in a radix-two SD number representation. By using a booth recording method, the speed of a modular multiplication becomes twice as fast as original one.