A new Mixed Radix Conversion algorithm MRC-II

In this paper, we present an efficient and simplified algorithm for the Residue Number System (RNS) conversion to weighted number system which in turn will simplify the implementation of RNS sign detection, magnitude comparison, and overflow detection. The algorithm is based on the Mixed Radix Conversion (MRC). The new algorithm simplifies the hardware implementation and improves the speed of conversion by replacing a number of multiplication operations with small look-up tables. The algorithm requires less ROM size compared to those required by existing algorithms. For a moduli set consisting of eight moduli, the new algorithm requires seven tables to do the conversion with a total table size of 519 bits, while Szabo and Tanaka MRC algorithm [N.S. Szabo, R.I. Tanaka, Residue Arithmetic and its Application to Computer Technology, McGraw-Hill, New York, 1967; C.H. Huang, A fully parallel mixed-radix conversion algorithm for residue number applications, IEEE Transactions on Computers c-32 (4) (1983)] requires 28 tables with a total table size of 8960 bits; and Huang MRC algorithm (Huang, 1983) requires 36 tables with a total table size of 5760 bits.