A Multiplicative Inverse Algorithm Based on Modulo (2p - 1) Signed-Digit Arithmetic for Residue to Weighted Number Conversion

The multiplicative inverse numbers are needed for converting the numbers in a residue number system (RNS) into a weighted number. In this paper, a new hardware algorithm is presented by use of a radix-two signed-digit (SD) arithmetic for the multiplicative inverse calculation modulo m_i = (2^p-1), where m_i is a modulus in the RNS. The calculation of an multiplicative inverse number can be implemented only by carry-free SD additions. An efficient serial residue-to-weighted number converter with the number inversion circuit is also proposed. By circuit design and simulation, the proposed converter using SD arithmetic has high speed performance compared to that based on binary arithmetic.