Residue Number System Reverse Converters

Print

Converters for RNS Four-Moduli sets:

The usage of the RNS can provide great advantages for the parallelization of algorithms. However, it requires efficient converters to convert from the RNS representation to binary in order for the utilization of this system to be profitable. Examples for such four-moduli sets are {2n+1,2n-1,2n,22n+1-1}, {2n+1,2n-1,2n,22n+1+1}, {2n+1,2n-1,22n,22n+1}, {2n+1,2n-1,22n,22n+1-1} and {2n+1,2n-1,22n+1-3,22n-2}.

The Chinese Remainder Theorem (CRT) and the Mixed Radix Conversion (MRC) have been the main approaches to build these converters.

Concerning the moduli sets {2n+1,2n-1,2n,22n+1-1} we present an HDL description concerning a converter using the MRC with a divide and conquer approach, and another HDL description of a converter based on the CRT, namely the commonly called new CRTs, as proposed in [1].

Concerning the moduli sets {2n+1,2n-1,2n,22n+1+1} we present an HDL description concerning a converter using the MRC with a divide and conquer approach, and another HDL description of a converter based on the CRT, namely the commonly called new CRTs, as proposed in [2].

Concerning the moduli sets {2n+1,2n-1,22n,22n+1} we present an HDL description concerning a converter using the MRC with a divide and conquer approach, and another HDL description of a converter based on the CRT, namely the commonly called new CRTs, as proposed in [1].

Concerning the moduli sets {2n+1,2n-1,22n,22n+1-1} we present an HDL description concerning a converter using the MRC with a divide and conquer approach.

Concerning the moduli sets {2n+1,2n-1,22n+1-3,22n-2} we present an HDL description of a converter based on the CRT, namely the commonly called new CRTs, as proposed in [3].

The aforementioned HDL descriptions are based on a VHDL library following the one proposed by Zimmerman in [4], and can be obtained here.

 

References:

[1]  A. S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, and S. Timarchi, “Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n+1,2n-1,2n,22n+1-1} and {2n+1,2n-1,22n,22n+1} Based on New CRTs,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57, no. 4, pp. 823-835, 2010.

[2]  P. V. A. Mohan and A. B. Premkumar, “RNS-to-binary converters for two four-moduli {2n-1,2n,2n+1,2n+1-1} and {2n-1,2n,2n+1,2n+1+1},” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 54, no. 6, pp. 1245-1254, 2007.

[3]  W. Zhang and P. Siy, “An efficient design of residue to binary converter for four moduli set {2n+1,2n-1,22n+1-3,22n-2} based on new CRT II,” Information Sciences, vol. 178, no. 1, pp. 264-279, 2008.

[4]  R. Zimmermann, “VHDL Library of Arithmetic Units,” in International Forum on Design Languages - FDL, 1998, pp. 1-6. Online. Available: http://www.iis.ee.ethz.ch/~zimmi/arith_lib.html

IBM Research  IST link  INESC-ID link  Sips link