Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem. (English) Zbl 06905133
Summary: The residue number system (RNS) is an unconventional number system which can lead to parallel and fault-tolerant arithmetic operations. However, the complexity of residue-to-binary conversion for large number of moduli reduces the overall RNS performance, and makes it inefficient for nowadays high-performance computation systems. In this paper, we present an improved approximate Chinese remainder theorem (CRT) with the aim of performing efficient residue-to-binary conversion for general RNS moduli sets. To achieve this aim, the required number of fraction bits for accurate residue-to-binary conversion is derived. Besides, a method is proposed to substitute fractional calculations by similar computations based on integer numbers to have a hardware amenable algorithm. The proposed approach results in high-speed and low-area residue-to-binary converters for general RNS moduli sets. Therefore, with this conversion method, high dynamic range residue number systems suitable for cryptography and digital signal processing can be designed.
MSC:
| 65Y04 | Numerical algorithms for computer arithmetic, etc. |
| 65Y05 | Parallel numerical computation |
| 65Y20 | Complexity and performance of numerical algorithms |
| 65Y10 | Numerical algorithms for specific classes of architectures |
Keywords:
computer arithmetic; residue number systems; Chinese remainder theorem; residue-to-binary converter; residue arithmeticReferences:
| [1] | S. Antão and L. Sousa, The CRNS framework and its application to programmable and reconfigurable cryptography, ACM Trans. Archit. Code Optim. 9(4) (2013), article no. 33. doi: 10.1145/2400682.2400692. |
| [2] | S.F. Antão, J.C. Bajard, and L. Sousa, RNS based elliptic curve point multiplication for massive parallel architectures, Comput J. 55(5) (2011). pp. 629-647. |
| [3] | T. Arabi, VLSI challenges to more energy efficient devices, Proceedings of the IEEE International Conference on Embedded Computer Systems (SAMOS), Samos, Greece, 2010. |
| [4] | J.C. Bajard and L. Imbert, A full RNS implementation of RSA, IEEE Trans. Comput. 53(6) (2004), pp. 769-774. |
| [5] | M.A. Bayoumi and P. Srinivasan, Parallel arithmetic: from algebra to architecture, Proceedings of IEEE International Symposium on Circuits and Systems, New Orleans, LA, USA, 1990. |
| [6] | J.L. Beuchat, Some modular adders and multipliers for field programmable gate arrays, Proceedings of the International Symposium on Parallel and Distributed Processing, Nice, France, 2003. |
| [7] | B. Cao, C.H. Chang, and T. Srikanthan, A residue-to-binary converter for a new five-moduli set, IEEE Trans. Circuits Syst. I: Regular Pap. 54(5) (2007), pp. 1041-1049. · Zbl 1374.68013 |
| [8] | C.H. Chang, A.S. Molahosseini, A.A.E. Zarandi, and T.F. Tay, Residue number system: A new paradigm to datapath optimization for low-power and high-performance digital signal processing applications, IEEE Circuits Syst. Mag. 15(4) (2015), pp. 26-44. |
| [9] | J. Chen and J. Hu, Energy-efficient digital signal processing via voltage-over scaling-based residue number system, IEEE Trans. VLSI Syst. 21(7) (2013), pp. 1322-1332. |
| [10] | N.I. Chervyakov, P.A. Lyakhov, and M.G. Babenko, Digital filtering of images in a residue number system using finite-field wavelets, J. Autom. Control Comput. Sci. 48(3) (2014), pp. 180-189. |
| [11] | N.I. Chervyakov, M.G. Babenko, P.A. Lyakhov, I.N. Lavrinenko, An approximate method for comparing modular numbers and its application to the division of numbers in residue number systems, Cybernet. Syst. Anal. 50(6) (2014), pp. 977-984. · Zbl 1327.68340 |
| [12] | R. Chokshi, K.S. Berezowski, A. Shrivastava and S.J. Piestrak, Exploiting residue number system for power-efficient digital signal processing in embedded processors, Proceedings of International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, Grenoble, France, 2009, pp. 19-28. |
| [13] | M. Esmaeildoust, D. Schinianakis, H. Javashi, T. Stouraitis, and K. Navi, Efficient RNS implementation of elliptic curve point multiplication over GF(\(p\)), IEEE Trans. VLSI Syst. 21 (2013), pp. 1545-1549. |
| [14] | M. Gomathisankaran, A. Tyagi, and K. Namuduri, HORNS: A Homomorphic Encryption Scheme for Cloud Computing using Residue Number System, Proceedings of IEEE 45th Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA, 2011, pp. 1-5. |
| [15] | A. Hariri, K. Navi, and R. Rastegar, A new high dynamic range moduli set with efficient reverse converter, Comput. Math. Appl. 55(4) (2008), pp. 660-668. · Zbl 1138.68010 |
| [16] | C.Y. Hung and B. Parhami, An approximate sign detection method for residue numbers and its application to RNS division, Comput. Math. Appl. 27(4) (1994), pp. 23-35. · Zbl 0805.68059 |
| [17] | I. Koren, Computer Arithmetic Algorithms, 2nd ed., A K Peters, Natick, MA, 2002. · Zbl 0994.68186 |
| [18] | J.Y.S. Low and C.H. Chang, A new approach to the design of efficient residue generators for arbitrary moduli, IEEE Trans. Circuits Syst. - I: Regular Pap. 60(9) (2013), pp. 2366-2374. · Zbl 1468.65237 |
| [19] | P.M.F.M. Matutino, R. Chaves, and L. Sousa, Arithmetic-based binary-to-RNS converter modulo {2n±k} for jn-bit dynamic range, IEEE Trans. Very Large Scale Integr. Syst. 23(3) (2014), pp. 603-607. |
| [20] | A.S. Molahosseini and K. Navi, Study of the reverse converters for the large dynamic range four-moduli sets, in Applications of Digital Signal Processing, C.C. Laborde, Ed., InTech Press, 2011, Chapter 16, pp. 337-350. |
| [21] | A.S. 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\^{}{2n+1}−1} and {2\^{}{n}−1, 2\^{}{n}+1, 2\^{}{2n}, 2\^{}{2n+1}} based on new CRTs, IEEE Trans Circuits Syst. I: Regular Pap. 57(4) (2010), pp. 823-835. · Zbl 1468.68027 |
| [22] | R. Muralidharan and C.H. Chang, Radix-8 Booth encoded modulo 2\^{}{n}-1 multipliers with adaptive delay for high dynamic range residue number system, IEEE Trans. Circuits Syst. I: Regular Pap. 58(5) (2011), pp. 982-993. · Zbl 1468.94410 |
| [23] | K. Navi, A.S. Molahosseini, and M. Esmaeildoust, How to teach residue number system to computer scientists and engineers, IEEE Trans. Educ. 54(1) (2011), pp. 156-163. |
| [24] | A. Omondi and B. Premkumar, Residue Number Systems: Theory and Implementations, Imperial College Press, London, 2007. · Zbl 1149.68019 |
| [25] | B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs, 2nd ed., Oxford University Press, New York, 2010. |
| [26] | 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: Regular Pap. 54 (2007), pp. 1279-1292. |
| [27] | H. Pettenghi, R. Chaves, and L. Sousa, RNS reverse converters for moduli sets with dynamic ranges up to (8n+1)-bit, IEEE Trans Circuits Syst. I: Regular Pap. 60 (2013), pp. 1487-1500. · Zbl 1468.94211 |
| [28] | S.J. Piestrak, Design of residue generators and multioperand modular adders using carry-save adders, IEEE Trans. Comput. 43(1) (1994), pp. 68-77. |
| [29] | K.H. Rosen, Elementary Number Theory and its Applications, 6th ed., Addison-Wesley, Reading, MA, 2010. |
| [30] | R. Schneiderman, DSPs evolving in consumer electronics applications, IEEE Signal Process. Mag. 27(3) (2010), pp. 6-10. |
| [31] | T. Stouraitis and V. Paliouras, Considering the alternatives in low-power design, IEEE Circuits Dev. 7 (2001), pp. 23-29. |
| [32] | T.V. Vu, Efficient implementations of the Chinese Remainder Theorem for sign detection and residue decoding, IEEE Trans. Comput. 34(7) (1985), pp. 646-651. · Zbl 0566.94011 |
| [33] | C.H. Vun, A.B. Premkumar, and W. Zhang, A new RNS based DA approach for inner product computation, IEEE Trans. Circuits Syst. I: Regular Pap. 60(8) (2013), pp. 2139-2152. · Zbl 1468.94258 |
| [34] | S.C. Yang, Toward a wireless world, IEEE Technol. Soc. Mag. 26(2) (2007), pp. 32-42. |
| [35] | A.A.E. Zarandi, A.S. Molahosseini, M. Hosseinzadeh, S. Sorouri, S. Antao, and L. Sousa, Reverse converter design via parallel-prefix adders: Novel components, methodology and implementations, IEEE Trans. VLSI Syst. 23(2) (2015), pp. 374-378. |
| [36] | R. Zimmermann, Efficient VLSI implementation of modulo (2n±1) addition and multiplication, Proceedings of the IEEE International Symposium on Computer Arithmetic, Adelaide, Australia, 1999, pp. 158-167. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
