Fast reverse converter Architecture for Balanced Five Moduli Set {2n, 2n+1, 2n-1, 2n+1-1, 2n-1-1}

Mohammad Esmaeildoust, Sakineh Sharifi


In this paper fast residue-to-binary converter for the moduli sets {2n, 2n+1, 2n-1, 2n+1-1, 2n-1-1} will be presented. The reverse converter architecture has three step designs includes Chinese Reminder Theorem (CRT) in first step and mixed radix conversion (MRC) for second and third steps. Comparison with the state-of-the-arts works in literature confirms that the proposed architecture improves the speed of residue-to-binary conversion and has excellence in hardware saving.

Full Text:



K. Navi, A. S. Molahosseini, and M. Esmaeildoust, “How to teach residue number system to computer scientists and engineers?”IEEETrans.Edu., vol. 54, no. 1, pp. 156–163, Feb. 2011.

N.S. Szabo and R.I. Tanaka. Residue Arithmetic and its Applications to Computer Technology, McGraw Hill.NewTork, 1967.

K.A. Gbolagade, R. Chaves, L. Sousa, and S.D. Cotofana .Residue-to-Binary Converters for the {22n+1 − 1, 22n, 2n – 1} Moduli set. 2nd IEEE International Conference on Adaptive Science and Technology.pp. 26 - 33, Accra, Ghana. December, 2009.

W. Wang, M. N. S. Swamy, and M. O. Ahmad, “Moduli s RNS for efficient VLSI implementation,” in Proc. IEEE Int. Symp.Circuits Syst., 2003, pp. 25–28.

P.V. Ananda Mohan, D.V. Poornaiah, Novel RNS to binary converters, 1991 IEEE International Symposium on Circuits and Systems, Part 3 (of 5), Jun 11–14, IEEE, Piscataway, NJ, USA, Singapore, Singapore, 1991, pp. 1541–1544.

C.Y. Chen, An efficient parity detection technique using the two-moduli set f2h _ 1; 2h þ 1g, Information Sciences 22 (176) (2006)3426–3430.

A.A. Hiasat, New design for a sign detector and a residue to binary converter, in: Proceedings of the Tenth IASTED International Conference. Applied Informatics, 10–12 February, Acta Press, Innsbruck, Austria, 1992, pp. 110–113.

A.A. Hiasat, An arithmetic residue to binary conversion technique, Integration, the VLSI Journal 36 (1–2) (2003) 13–25.

D. Kang, J. Ryu, J. Cho, A higher-speed architecture for residue to binary number system conversion, in: Proceedings of Ninth International Symposium on Integrated Circuits, Devices and Systems, 3–5 September, Nanyang Technological University,Singapore, 2001, pp. 246–249.

J. Mathew, D. Radhakrishnan, T. Srikanthan, Fast residue-to-binary converter architectures, 42nd Midwest Symposium on Circuits and Systems, 8–11 August, IEEE, Las Cruces, NM, USA, 2000, pp. 1090–1093.

S.J. Piestrak, A high speed realization of a residue to binary system converter, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 42 (10) (1995) 661–663.

Y. Wang, M.N. Swamy, M.O. Ahmad, Residue-to-binary number converters for three moduli sets, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 46 (2) (1999) 180–183.

Z. Wang, G.A. Jullien, W.C. Miller, An efficient 3-modulus residue to binary converter, in: Proceedings of the 39th Midwest Symposium on Circuits and Systems, 18–21 August, IEEE, Ames, IA, USA, 1996, pp. 1305–1308.

P.V.A. Mohan, A.B. Premkumar. RNS-to-binary converters for two four-moduli sets {2n, 2n+ 1, 2n-1, 2n+ 1-1} and {2n, 2n+ 1, 2n-1, 2n+ 1+ 1},vol,IEEE Trans. Circuits Syst. I, Reg. Papers54, no. 6, pp. 1245–1254, Jun. 2007.

B. Cao, T. Srikanthan, and C. H. Chang, “Efficient reverse converter for the our-moduli sets {2n, 2n+ 1, 2n-1, 2n+ 1-1} and {2n, 2n+ 1, 2n-1, 2n- 1- 1},” Proc. IEE Comput. Digit.Tech.687–696, 2005.

P. V. A. Mohan, “New reverse converters for the moduli set {2n-3, 2n-1, 2n+ 1, 2n+ 3},” Elsevier J. Electron. Commun.(AEU)vol. 62,no. 9, pp. 643–658, 2008.

A. Hariri, K. Navi, and R. Rastegar, “A newhigh dynamic range moduli set with efficient reverse converter,” Elsevier J. Comput. Math.WithAppl., vol. 55, no. 4, pp. 660–668, 2008.

B. Cao, C. H. Chang, and T. Srikanthan, “An efficient reverse converter for the 4-moduli set{2n-1,2n,2n+1,22n+1} base on the newChinese remainder theorem,” IEEE Trans. Circuits Syst. I, Reg. Papersvol.50, no. 10, pp. 1296–1303, 2003.

A. A. Hiasat, “VLSI implementation of new arithmetic residue to binarydecoders,” IEEE Trans. Very Large Scale Integr. (VLSI) 1, pp. 153–158, Jan. 2005.

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,2n+1,22n+1} and {2n-1, 2n+ 1, 22n, 22n+ 1},Based on New CRTs,” IEEE Trans. Circuits Syst.I: Reg. Papers, vol 57, no. 4, pp.823–834 April 2010.

W. Zhang and P. Siy, “An efficient design of residue to binary converterfor four moduli set {2n-1,2n+1,22n-2,2n+1-3}based on newCRT II,” J. Inf. Sci., vol. 178, no. 1, pp. 264–279,2008.

A.S. Molahosseini, K. Navi, “A Reverse Converter for the Enhanced Moduli Set {2n-1,2n+1,22n,22n+1-1}Using CRT and MRC,”IEEE Annual Symposium on VLSI.Pp 456–457, 2010.

B. Cao, C. H. Chang, and T. Srikanthan, “A residue-to-binary converter for a new five-moduli set,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 54, no. 5, pp. 1041–1049, May 2007.

Soderstrand, M.A., Ed. (1986) Residue Number System Arithmetic:Modern Applications in Digital Signal Processing (IEEE Press,New York).

N Keivan, M Esmaeildoust, AS Molahosseini, “A General Reverse Converter Architecture with Low Complexity and High Performance”, IEICE TRANSACTIONS on Information and Systems 94 (2), (2011) 264-273.

B. Cao, T. Srikanthan, C.H. Chang, “Efficient reverse converters for the four-moduli sets {2n–1, 2n, 2n+1, 2n+1–1} and {2n–1, 2n, 2n+1, 2n–1–1},” IEE Proc. Comput. Digit.Tech., vol. 152, 687–96, 2005.

S.J. Piestrak, “Design of residue generators and multioperand modular adders using carry-save adders”, IEEE Trans. Comput., Vol. 423, pp. 68–77, 1994.

Reto Zimmermann, “Lecture notes on Computer Arithmetic: Principles, Architectures and VLSI Design,” Integrated System Laboratory, Swiss Federal Institute of Technology (ETH) Zurich, Mar, 16, 1999.

S.J. Piestrak, “A high speed realization of a residue to binary converter”, IEEE Trans. Circuits Syst. II, Analog.Digit. Signal Process., Vol. 42, pp. 661–663, Oct. 1995.

R. Zimmermann, “Efficient vlsi implementation of modulo (2n ± 1) addition and multiplication,” in 14th IEEE Symposium on Computer Arithmetic, 1999.

R. Conway and J. Nelson, “Improved RNS FIR Filter Architectures,” IEEE Transactions On Circuits and Systems II, Vol. 51, No. 1, pp. 26-28, 2004.

B. D. Tseng , G. A. Jullien and W. C. Miller "Implementation of FFT Structures Using the Residue Number System", IEEE Trans. Computers, vol. C-28, no. 11, pp.831 -845 1979.

W. Wei et al., “RNS application for digital image processing,” Proceedings of the 4th IEEE international workshop on system-on-chip for real time applications, Canada, pp. 77-80, 2004.

S. Yen, S. Kim, S. Lim and S. Moon, “RSA Speedup with Chinese Remainder Theorem Immune against Hardware Fault Cryptanalysis,” IEEE Transactions on Computers, vol. 52, no. 4, pp. 461-472, 2003.

M. Esmaeildoust, D. Schinianakis, H.Javashi, T. Stouraitis, K. Navi, "Efficient RNS Implemenation of Elliptic Curve Point Multiplication Over GF(p)," IEEE Transaction on Very Large Scale Integration (VLSI) Systems, Vol. 21 , No. 8, 1545 – 1549, 2013.

M. Esmaeildoust, A. Kaabi, “High Speed Reverse Converter for the Five Moduli Set {2n, 2n-1, 2n+1, 2n-3, 2n-1-1}”, TJMCS, pp. 438-450, 2014.

Mohammad Esmaeildoust, Keivan Navi and Mohammad Reza Taheri, “High speed reverse converter for new five-moduli set {2n, 22n+1-1, 2n/2-1, 2n/2+1, 2n+1}”, IEICE Electron. Express, Vol. 7, No. 3, (2010) 118-125.

A. S. Molahosseini , C. Dadkhah and K. Navi "A new five-moduli set for efficient hardware implementation of the reverse converter", IEICE Electron. Exp., vol. 6, no. 14, pp.1006 -1012, 2009.

L. Kalampoukas "High-speed parallel-prefix modulo 2n-1 adders", IEEE Trans. Comput., vol. 49, no. 7, pp.673 -679, 2000.

C. Efstathiou , H. T. Vergos and D. Nikolos "Fast parallel-prefix modulo 2n+1 adder", IEEE Trans. Comput., vol. 53, no. 9, pp.1211 -1216, 2004.

R. A. Patel, M. Benaissa , N. Powell and S. Boussakta "Novel power-delay-area-efficient approach to generic modular addition", IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 54, no. 6, pp.1279 -1292, 2007.