Research PapersNo Access

Area Efficient Memoryless Reverse Converter for New Four Moduli Set ${2^{n - 1}, 2^{n} - 1, 2^{n} + 1, 2^{2 n + 1} - 1}$

Electronics and Communication Engineering Department, Motilal Nehru National Institute of Technology, Allahabad 211004, India

E-mail Address: rel1406@mnnit.ac.in

Corresponding author.

Search for more papers by this author

Raj Kumar

Electronics and Communication Engineering Department, Motilal Nehru National Institute of Technology, Allahabad 211004, India

E-mail Address: rajkumar.mnnit2013@gmail.com

Search for more papers by this author

, and

Ram Awadh Mishra

Electronics and Communication Engineering Department, Motilal Nehru National Institute of Technology, Allahabad 211004, India

E-mail Address: ramishra@mnnit.ac.in

Search for more papers by this author

https://doi.org/10.1142/S0218126618500755Cited by:5 (Source: Crossref)

Abstract

The efficiency of residue number system depends on the reverse converter due to several modulo operations like addition, subtraction and multiplication. In this paper, a design of new four moduli set ${2^{n - 1}, 2^{n} - 1, 2^{n} + 1, 2^{2 n + 1} - 1}$ , reverse converter is presented. The moduli set have moduli with length ranging from ( $n - 1$ ) to ( $2 n + 1$ )-bits. The reverse conversion for moduli set ${2^{n - 1}, 2^{n} - 1, 2^{n} + 1}$ has been optimized in existing state of art. Thus, proposed converter is based on two new moduli set ${2^{n - 1} (2^{2 n} - 1), 2^{2 n + 1} - 1}$ and utilizes the mixed radix conversion. This converter is memoryless, and occupies least area. The proposed converter is based on carry save adder (CSA) and modulo adder enabling more speed and less hardware complexity for dynamic range of $5 n$ -bit, offering good area-delay product.

This paper was recommended by Regional Editor Emre Salman.

Keywords:

References

1. N. S. Szabo and R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw Hill, New York, 1967). Google Scholar
2. B. Parhami, Computer Arithmetic, Algorithms and Hardware Design (Oxford University Press, 2000). Google Scholar
3. P. V. A. Mohan, Residue Number Systems: Algorithms and Architectures (Kluwer, Norwell, 2002). Crossref, Google Scholar
4. A. Omondi and B. Premkumar, Residue Number Systems: Theory and Implementations (Imperial College Press, London, 2007). Link, Google Scholar
5. R. A. Patel, M. Benaissa and S. Boussakta, Efficient new approach for modulo $2^{n} - 1$ addition in RNS, IEE Proc.-Comput. Digit. Tech. 153 (2006) 399–405. https://doi.org/org/1049/ip-cdt:20050166 Crossref, Web of Science, Google Scholar
6. J. Chen and J. Hu, Energy-efficient digital signal processing via voltage-overscaling-based residue number system, IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21 (2013) 1322–1332. https://doi.org/org/10.1109/TVLSI.2012.2205953 Crossref, Web of Science, Google Scholar
7. R. Zimmermann, Efficient VLSI implementation of modulo ( $2^{n} \pm 1$ ) addition and multiplication, Proc. 14th IEEE Symp. Computer Arithmetic (Adelaide, 1999), pp. 158–167. Google Scholar
8. C. H. Vun, A. B. Premkumar and W. Zhang, A new RNS based DA approach for inner product computation, IEEE Trans. Circuits Syst. - I 60 (2013) 2139–2152. https://doi.org/org/10.1109/TCSI.2013.2239164 Crossref, Web of Science, Google Scholar
9. D. Schinianakis and T. Stouraitis, Multifunction residue architecture for cryptography, IEEE Trans. Circuits Syst. - I 61 (2014) 1156–1169. https://doi.org/org/10.1109/TCSI.2013. 2283674 Crossref, Web of Science, Google Scholar
10. W. Wang, M. N. S. Swamy and M. O. Ahmad, Moduli selection in RNS for efficient VLSI implementation, Proc. 4th IEEE Int. Symp. Circuits and Systems (Bangkok, 2003), pp. 512–515. Google Scholar
11. S. Bi and W. J. Gross, The mixed-radix Chinese remainder theorem and its applications to residue comparison, IEEE Trans. Comput. 57 (2008) 1624–1632. https://doi.org/org/10.1109/TC.2008.126 Crossref, Web of Science, Google Scholar
12. Y. Wang et al., Adder based residue to binary number converters ${2^{n} - 1, 2^{n}, 2^{n} + 1}$ , IEEE Trans. Signal Process. 50 (2002) 1772–1779. https://doi.org/org/10.1109/TSP.2002.1011216 Crossref, Web of Science, Google Scholar
13. W. Wang et al., A high-speed residue-to-binary converter for three-moduli ${2^{k}, 2^{k} - 1, 2^{k - 1} - 1}$ RNS and a scheme for its VLSI implementation, IEEE Trans. Circuits Syst. - II: Analog. Digit. Signal Process. 47 (2000) 1576–1581. Crossref, Google Scholar
14. P. V. Ananda Mohan and A. B. Premkumar, RNS-to-binary converters for two four-moduli sets ${2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1}$ and ${2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} + 1}$ , IEEE Trans. Circuits Syst. I: Reg. Papers 54 (2007) 1245–1254, doi: org/10.1109/TCSI.2007.895515. Google Scholar
15. P. V. Ananda Mohan, New reverse converters for the moduli set ${2^{n} - 3, 2^{n} - 1, 2^{n} + 1, 2^{n} + 3}$ , Int. J. Electron. Commun. (AEÜ) 62 (2008) 643–658. https://doi.org/org/10.1016/j.aeue.2007.08.008 Crossref, Web of Science, Google Scholar
16. P. V. Ananda Mohan, Reverse converters for a new moduli set ${2^{2 n} - 1, 2^{n}, 2^{2 n} + 1}$ , Circuits Syst. Signal Process. 26 (2007) 215–227. https://doi.org/org/10.1007/s00034-006-0219-y Crossref, Web of Science, Google Scholar
17. M. Reza, N. Mehdi and K. Navi, Efficient reverse converters for 4-moduli sets ${2^{2 n - 1} - 1, 2^{n}, 2^{n} + 1, 2^{n} - 1}$ and ${2^{2 n - 1}, 2^{2 n - 1} - 1, 2^{n} + 1, 2^{n} - 1}$ based on CRTs algorithm, Circuits Syst. Signal Process. 33 (2014) 3145–3163. https://doi.org/org/10.1007/s00034-014-9798-1 Web of Science, Google Scholar
18. L. Sousa and S. Antão, MRC-based RNS reverse converters for the four-moduli sets ${2^{n} + 1, 2^{n} - 1, 2^{n}, 2^{2 n + 1} - 1}$ and ${2^{n} + 1, 2^{n} - 1, 2^{2 n}, 2^{2 n + 1} - 1}$ , IEEE Trans. Circuits Syst. II 59 (2012) 244–248. https://doi.org/org/10.1109/TCSII.2012.2188456 Crossref, Google Scholar
19. A. S. Molahosseini, Improving the delay of residue-to-binary converter for four-moduli set, Adv. Elect. Comput. Engg. 11 (2011) 37–42. https://doi.org/org/10.4316/AECE.2011.02006 Crossref, Web of Science, Google Scholar
20. A. S. Molahosseini et al., Efficient reverse converter designs for the new 4-moduli sets ${2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2 n + 1} - 1}$ and ${2^{n} + 1, 2^{n} - 1, 2^{2 n}, 2^{2 n} + 1}$ based on new CRTs, IEEE Trans. Circuits Syst. I, Reg. Papers 57 (2010) 823–835, doi: org/10.1109/TCSI.2009.2026681. Google Scholar
21. E. K. Bankas and K. A. Gbolagade, A new efficient RNS reverse converter for the 4-moduli set ${2^{n}, 2^{n} + 1, 2^{n} - 1, 2^{2 n + 1} - 1}$ , Int. J. Computer, Control, Quant. Inf. Engg. 8 (2014) 318–322. http://scholar.waset.org/1999.4/9997730 Google Scholar
22. B. Cao, C. H. Chang and T. Srikanthan, An efficient reverse converter for the 4-moduli set ${2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2 n} + 1}$ based on new Chinese remainder theorem, IEEE Trans. Circuits Syst. I, Fundam. Theory Appl. 50 (2003) 1296–1303. https://doi.org/org/10.1109/TCSI.2003.817789 Crossref, Google Scholar
23. A. S. Molahosseini et al., An efficient architecture for designing reverse converters based on a general three-moduli set, J. Syst. Arch. 54 (2008) 929–934. https://doi.org/org/10.1016/j.sysarc.2008.03.006 Crossref, Web of Science, Google Scholar
24. P. Patronik and S. J. Piestrak, Design of reverse converters for general RNS moduli sets ${2^{k}, 2^{n} - 1, 2^{n} + 1, 2^{n + 1} - 1}$ and ${2^{k}, 2^{n} - 1, 2^{n} + 1, 2^{n - 1} - 1}$ (n even), IEEE Trans. Circuits Syst. I 61 (2014) 1687–1700. https://doi.org/org/10.1109/TCSI.2013.2290843 Crossref, Google Scholar
25. H. Pettenghi, R. Chaves and L. Sousa, Method to design general RNS reverse converters for extended moduli sets, IEEE Trans. Circuits Syst. II, Exp. Briefs 60 (2013) 877–881. https://doi.org/org/10.1109/TCSII.2013.2286433 Crossref, Web of Science, Google Scholar
26. A. Hiasat and A. Sweidan, Residue number system to binary converter for the moduli set $(2^{n - 1}, 2^{n} - 1, 2^{n} + 1)$ , J. Syst. Arch. 49 (2003) 53–58. https://doi.org/org/10.1016/S1383-7621(03)00062-6 Crossref, Web of Science, Google Scholar
27. A. Tyagi, A reduced-area scheme for carry-select adders, IEEE Trans. Comput. 42 (1993) 1163–1170. https://doi.org/org/10.1109/12.257703 Crossref, Web of Science, Google Scholar
28. A. S. Molahosseini et al., Rethinking reverse converter design: From algorithms to hardware components, 2014 14th Int. Symp. Integrated Circuits (ISIC) (IEEE, 2014). https://doi.org/org/10.1109/ISICIR.2014.7029561 Google Scholar