Research PaperNo Access

A Residue-to-Binary Converter with an Adjustable Structure for an Extended RNS Three-Moduli Set

Department of Computer Engineering, Princess Sumaya University for Technology, Amman 11941, Jordan

https://doi.org/10.1142/S0218126619501263Cited by:12 (Source: Crossref)

Abstract

In earlier publications, many researchers have addressed the problem of residue-to-binary conversion for the popular moduli set $(2^{n}, 2^{n} - 1, 2^{n} + 1)$ , where $n$ is a positive integer greater than 1. In this paper, we are proposing, potentially, the fastest converter ever for this moduli set with the least hardware requirements. Moreover, the paper revisits the extended three-moduli set $(2^{n + p}, 2^{n} - 1, 2^{n} + 1)$ , where $p$ is a positive integer such that $0 < p \leq n$ . This paper proposes an efficient residue-to-binary converter with an adjustable structure. The proposed structure allows increasing the dynamic range at a cost of two gates per bit. When compared with a similar published work for the extended moduli set, the proposed extended converter showed significant reductions in area by 9.9–13.4%, in delay by 16.9–24.1% and in power consumption by 10.6–16.7%.

This paper was recommended by Regional Editor Zoran Stamenkovic.

Keywords:

References

1. M. A. Soderstrand, W. Jenkins, G. Jullien and F. Taylor (eds.), Residue Number System Arithmetic: Modern Applications in Digital Signal Processing (IEEE Press, New York, 1986). Google Scholar
2. T. Keller, T. H. Liew and L. Hanzo , Adaptive redundant residue number system coded multi-carrier modulation, IEEE J. Sel. Areas Commun. 18 (2000) 2292–2301. Web of Science, Google Scholar
3. J. Bajard, N. Meloni and T. Plantard , Efficient RNS bases for cryptography, Proc. 17th IMACS World Congr.: Scientific Computation, Applied Mathematics and Simulation (2005), pp. 1–7. Google Scholar
4. A. Hiasat and O. Hasan , Bit-serial architecture for rank order and stack filters, Integr., VLSI J. 36 (2003) 3–12. Web of Science, Google Scholar
5. A. Hiasat and A. Khateeb , Efficient digital sweep oscillator with extremely low sweep rates, IEEE Proc. Circuits Devices Syst. 145 (1998) 409–414. Web of Science, Google Scholar
6. M. Esmaeildoust, D. Schinianakis, H. Javashi, T. Stouraitis and K. Navi , Efficient RNS implementation of elliptic curve point multiplication over GF(p), IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21 (2013) 1545–1549. Web of Science, Google Scholar
7. C.-H. Chang, A. S. Molahosseini, A. A. E. Zarandi and T. F. Tay, Residue number systems: A new paradigm to datapath optimization for low-power and high-performance digital signal processing applications, IEEE Circuits Syst. Mag. 15 (2015) 26–44. Google Scholar
8. X. Zheng, B. Wang, C. Zhou, X. Wei and Q. Zhang , Parallel DNA arithmetic operation with one error detection based on 3-moduli set, IEEE Trans. Nanosci. 15 (2016) 499–507. Web of Science, Google Scholar
9. L. Sousa, S. Antao and P. Martins, Combining residue arithmetic to design efficient cryptographic circuits and systems, IEEE Circuits Syst. Mag. 16 (2016) 6–32. Google Scholar
10. A. S. Molahosseini, L. S. de Sousa and C.-H. Chang , Embedded Systems Design with Special Arithmetic and Number Systems (Springer, New York, 2017). Google Scholar
11. P. Bernardson , Fast memoryless, over 64 bits, residue to binary converter, IEEE Trans. Circuits Syst. 32 (1985) 298–300. Google Scholar
12. K. M. Ibrahim and S. N. Saloum , An efficient residue to binary converter design, IEEE Trans. Circuits Syst. 35 (1988) 1156–1158. Google Scholar
13. A. Sweidan and A. Hiasat , New efficient memoryless, residue to binary converter, IEEE Trans. Circuits Syst. 35 (1988) 1441–1444. Google Scholar
14. S. Piestrak , A high-speed realization of a residue to binary number system converter, IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process. 42 (1995) 661–663. Google Scholar
15. D. Gallaher, F. Petry and P. Srinivasan , The digital parallel method for fast RNS to weighted number system conversion for specific moduli $(2^{k} - 1, 2^{k}, 2^{n} + 1)$ , IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process. 48 (1997) 53–57. Google Scholar
16. A. Dhurkadas , Comments on: A high speed realization of a residue to binary number system converter, IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process. 45 (1998) 446–447. Google Scholar
17. M. Bhardwaj, A. B. Premkumar and T. Srikanthan , Breaking the $2 n$ bit carry propagation barrier in residue number system converter for the $(2^{n} - 1, 2^{n}, 2^{n} + 1)$ moduli set, IEEE Trans. Circuits Syst. I, Fundam. Theory Appl. 45 (1998) 998–1002. Google Scholar
18. R. Conway and J. Nelson , Fast converter for 3 moduli RNS using new property of CRT, IEEE Trans. Comput. 48 (1999) 852–860. Web of Science, Google Scholar
19. Z. Wang, G. A. Jullien and W. C. Miller , An improved residue-to-binary converter, IEEE Trans. Circuits Syst. I, Fundam. Theory Appl. 47 (2000) 1437–1440. Web of Science, Google Scholar
20. A. Hiasat and H. Abdel-Aty-Zohdy , Residue to binary arithmetic converter for the moduli $(2^{k}, 2^{k} - 1, 2^{k - 1} - 1)$ , IEEE Trans. Circuits Syst. II, Analog. Digit. Signal Process. 45 (1998) 204–209. Google Scholar
21. W. Wang, M. Swamy, M. Ahmad and Y Wang , A high-speed residue-to-binary converter for the three-moduli $(2^{k}, 2^{k} - 1, 2^{k - 1} - 1)$ , IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process. 47 (2000) 1576–1581. Google Scholar
22. Y. Wang, X. Song, M. Aboulhamid and H. Shen , Adder-based residue to binary number converter for $(2^{n} - 1, 2^{n}, 2^{n} + 1)$ , IEEE Trans. Signal Process. 50 (2002) 1772–1779. Web of Science, Google Scholar
23. W. Wang, M. Swamy, M. Ahmad and Y. Wang , A study of the residue-to-binary converters for the three-moduli sets, IEEE Trans. Circuits Syst. I, Fundam. Theory Appl. 50 (2003) 235–243. Google Scholar
24. 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. Archit. 49 (2003) 53–58. Web of Science, Google Scholar
25. P. V. A. Mohan , RNS-to-binary converter for a new three-moduli set $(2^{n + 1} - 1, 2^{n}, 2^{n} - 1)$ , IEEE Trans. Circuits Syst. II, Express Briefs 54 (2007) 775–779. Web of Science, Google Scholar
26. A. Hiasat , An efficient reverse converter for the three-moduli set $(2^{n + 1} - 1; 2^{n}; 2^{n} - 1)$ , IEEE Trans. Circuits Syst. II, Express Briefs 64 (2017) 962–966. Web of Science, Google Scholar
27. T. Tomczak, Fast sign detection for RNS ( $2^{n} - 1, 2^{n}, 2^{n} + 1)$ , IEEE Trans. Circuits Syst. I, Regul. Pap. 55 (2008) 1502–1511. Google Scholar
28. M. Xu, R. Yao and F. Luo , Low-complexity sign detection algorithm for RNS ${2^{n} - 1, 2^{n}, 2^{n} + 1}$ , IEICE Trans. Electron. E95-C (2012) 1552–1556. Web of Science, Google Scholar
29. L. Sousa and P. Srgio Alves Martins , Efficient sign identification engines for integers represented in the RNS extended 3-moduli set ${2^{n} - 1, 2^{n + k}, 2^{n} + 1}$ , Electron. Lett. 50 (2014) 1138–1139. Web of Science, Google Scholar
30. S. Kumar and C.-H. Chang , A new fast and area-efficient adder-based sign detector, IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 24 (2016) 2608–2612. Web of Science, Google Scholar
31. A. Hiasat , A sign detector for a group of three-moduli sets, IEEE Trans. Comput. 65 (2016) 3580–3590. Web of Science, Google Scholar
32. C. H. Chang, J. Low and S. Yung, Simple, fast, and exact RNS scaler for the three-moduli set $(2^{n} - 1, 2^{n}, 2^{n} + 1)$ , IEEE Trans. Circuits Syst. I, Regul. Pap. 58 (2011) 2686–2697. Google Scholar
33. A. Hiasat , A efficient RNS scalers for the extended three-moduli set $(2^{n} - 1, 2^{n + p}, 2^{n} + 1)$ , IEEE Trans. Comput. 66 (2017) 1253–1260. Web of Science, Google Scholar
34. L. Sousa , 2ⁿ RNS scalers for extended 4-moduli sets, IEEE Trans. Comput. 64 (2015) 3322–3334. Web of Science, Google Scholar
35. H. Pettenghi, R. Chaves and L. Sousa , $(2^{n} + 1, 2^{n + k}, 2^{n} - 1)$ : A new RNS moduli set extension, Proc. EUROMICRO Symp. Digital System Design (DSD04) (2004), pp. 210–217. Google Scholar
36. R. Chaves and L. Sousa , Improving residue number system multiplication with more balanced moduli sets and enhanced modular arithmetic structures, IET Comput. Digit. Tech. 5 (2007) 472–480. Web of Science, Google Scholar
37. R. Chokshi, K. S. Berezowski, A. Shrivastava and S. J. Piestrak , Exploiting residue number system for power-efficient digital signal processing in embedded processors, Proc. ACM Int. Conf. Compilers, Architecture and Synthesis for Embedded Systems (2009), pp. 19–27. Google Scholar
38. P. V. 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, Regul. Pap. 54 (2007) 1245–1254. Google Scholar
39. A. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei and S. Timarchi, 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^{2 n}, 2^{n} + 1, 2^{2 n} + 1)$ based on new CRTs, IEEE Trans. Circuits Syst. I, Regul. Pap. 57 (2010) 823–835. Google Scholar
40. L. Sousa and S. Anto , 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)$ , IEEE Trans. Circuits Syst. II, Express Briefs 59 (2012) 244–248. Web of Science, Google Scholar
41. A. Hiasat , A residue to binary converter for the extended four moduli set ${2^{n} - 1; 2^{n} + 1; 2^{2 n} + 1; 2^{2 n + p}}$ , IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 25 (2017) 2188–2192. Web of Science, Google Scholar
42. A. Hiasat, A reverse converter and sign detectors for an extended RNS five moduli set, IEEE Trans. Circuits Syst. I, Regul. Pap. 64 (2017) 111–121. Google Scholar
43. P. Patronik and S. Piestrak, Design of reverse converters for the new RNS moduli set ${2^{n} + 1, 2^{n} - 1, 2^{n}, 2^{n - 1} + 1}$ ( $n$ odd), IEEE Trans. Circuits Syst. I, Regul. Pap. (2014) 3436–3449. Google Scholar
44. A. Hiasat , VLSI implementation of new arithmetic residue to binary decoders, IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 13 (2005) 153–158. Web of Science, Google Scholar
45. B. Cao, C.-H. Chang and T. Srikanthan, A residue-to-binary converter for a new five-moduli set, IEEE Trans. Circuits Syst. I, Regul. Pap. 54 (2007) 1041–1049. Google Scholar
46. H. Ahmadifar and G. Jaberipur , A new residue number system with 5-moduli set: $(2^{2 q}, 2^{q} \pm 3, 2^{q} \pm 1)$ , Comput. J. 58 (2015) 1548–1565. Web of Science, Google Scholar
47. H. Pettenghi, R. Chaves and L. Sousa, RNS reverse converters for moduli sets with dynamic ranges up to $(8 n + 1)$ -bit, IEEE Trans. Circuits Syst. I, Regul. Pap. 60 (2013) 1487–1500. Google Scholar
48. H. Pettenghi, R. Chaves and L. Sousa , Method to design general RNS reverse converters for extended moduli set, IEEE Trans. Circuits Syst. II, Express Briefs 60 (2013) 877–881. Web of Science, Google Scholar
49. C.-H. Chang and S. Kumar , Area-efficient and fast sign detection for four-moduli set RNS $(2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2 n} + 1)$ , Proc. IEEE Int. Symp. Circuits and Systems (2014), pp. 1540–1543. Google Scholar
50. L. Kalamboukas, D. Nikolos, C. Efstathiou, H. T. Vergos and J. Kalamatianos , High-speed parallel-prefix modulo $2^{n} - 1$ adders, IEEE Trans. Comput. 49 (2000) 673–680. Web of Science, Google Scholar