Fast and Power Efficient Signed/Unsigned RNS Comparator & Sign Detector

Torabi, Z.; Belghadr, Armin

doi:10.22061/jecei.2022.8321.505

Document Type : Original Research Paper

Authors

Z. Torabi ¹
Armin Belghadr ²

¹ Department of Computer Systems Architecture, Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran.

² Department of Computer Science and Engineering, Shahid Beheshti University, Tehran, Iran.

https://doi.org/10.22061/jecei.2022.8321.505

Abstract

Background and Objectives: Residue number system (RNS) is considered as a prominent candidate for high-speed arithmetic applications due to its limited carry propagation, fault tolerance, and parallelism in “Addition”, “Subtraction”, and “Multiplication” operations. Whereas, “Comparison”, “Division”, “Scaling”, “Overflow Detection” and “Sign Detection” are considered as complicated operations in residue number systems, which have also received a surge of attention in a multitude of publications.
Efficient realization of Comparators facilitates other hard-to-implement operations and extends the spectrum of RNS applications. Such comparators can substitute the straightforward method (i.e. converting the comparison operands to binary and comparing them with wide word binary comparators) to compare RNS numbers.
Methods: Dynamic Range Partitioning (DRP) method has shown advantages for comparing unsigned RNS numbers in the 3-moduli sets {2^n,2^n±1} and {2^n,2^n-〖1,2〗^(n+1)-1}, in comparison with other methods. In this paper, we employed DRP components and designed a unified unit that detects the sign of operands and also compares numbers, for the 5-moduli set γ={2^2n,2^n±1,2^n±3}. This unit can be used for comparison of signed and also unsigned RNS numbers in the moduli set γ.
Results: Synthesized comparison results reveal 47% (54%) speed-up, 35% (32%) less area consumption, 25% (24%) lower power dissipation, and 60% (65%) less energy for n=8 (16) in comparison to the straightforward signed comparator.
Conclusion: According to the results of this study, DRP method for sign detection and comparison operations outperforms other methods in different moduli sets including 5-moduli set γ={2^2n,2^n±1,2^n±3}.

Keywords

Main Subjects

Computer Arithmetic

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit: http://creativecommons.org/licenses/by/4.0/

Publisher’s Note

JECEI Publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Publisher

Shahid Rajaee Teacher Training University

References

[1] G. C. Cardarilli, L. D. Nunzio, R. Fazzolari, A. Nannarelli, M. Petricca, M. Re, “Design space exploration based methodology for residue number system digital filters implementation,” IEEE Trans. Emerging Top. Comput., 10(1): 186-198, 2020.

[2] I. Z. Alhassan, E. D. Ansong, G. Abdul-Salaam, S. Alhassan, “Enhancing image security during transmission using residue number system and k-shuffle,” Earthline J. Math. Sci., 4(2): 399-424, 2020.

[3] D. Schoinianakis, “Residue arithmetic systems in cryptography a survey on modern security applications,” J. Cryptographic Eng., 10(3): 249-267, 2020.

[4] M. A. Belhamra, E. M. Souidi, “Steganography over Redundant Residue Number System Codes,” J. Inf. Secur. Appl., 51: 102434, 2020.

[5] M. I. Youssef, A. E. Emam, M. Abd Elghany, “Image multiplexing using residue number system coding over MIMO-OFDM communication system,” Int. J. Electr. Comput. Eng., 9(6): 4815-4825, 2019.

[6] L. Sousa, P. Martins, “Sign detection and number comparison on RNS 3-Moduli sets {2^n - 1, 2^(n+x), 2^n+1},” Circ. Syst. Signal Process., 36: 1224-1246, 2017.

[7] C. Y. Hung, B. Parhami, “An approximate sign detection method for residue numbers and its application to RNS division,” Comput. Math. Appl., 27: 23–35, 1994.

[8] T. Tomczak, “Fast sign detection for RNS (2ⁿ−1,2ⁿ,2ⁿ+1),” IEEE Trans. Circuits Syst. I Regul. Pap., 55(6): 1502–1511, 2008.

[9] Z. Torabi, G. Jaberipur, “Fast low energy RNS comparators for 4-moduli sets {2ⁿ±1, 2ⁿ, m} with m∈{2ⁿ⁺¹±1, 2ⁿ⁻¹−1} ", Integr. VLSI J., 55: 155-161, 2016.

[10] S. Bi, W. J. Gross, “The mixed-radix Chinese remainder theorem and its applications to residue comparison,” IEEE Trans. Comput., 57(12): 1624-1632, 2008.

[11] Y. Wang, X. Song, M. Aboulhamid, “A new algorithm for RNS magnitude comparison based on new Chinese remainder theorem II,” in Proc. Ninth Great Lakes Symposium on VLSI: 362-365, 1999.

[12] M. Lu, J. S. Chiang, “A novel division algorithm for the residue number system,” IEEE Trans. Comput., 1: 1026–1032, 1992.

[13] G. Dimauro, S. Impedovo, G. Pirlo, A. Salzo, “RNS architectures for the implementation of the diagonal function,” Inf. Process. Lett., 73: 189–198, 2000.

[14] L. Sousa, “Efficient method for magnitude comparison in RNS based on two pairs of conjugate moduli,” in Proc. IEEE Symposium on Computer Arithmetic (ARITH): 240-250, 2007.

[15] S. Kumar, C. H. Chang, TF Tay, “New algorithm for signed integer comparison in {2^(n+k),2^n - 1, 2^n+1, 2^(N ±1) -1} and its efficient hardware implementation,” IEEE Trans. Circuits Syst. I: Reg. Pap., 64(6): 1481-1493, 2016.

[16] K. Isupov, “Using floating-point intervals for non-modular computations in residue number system,” IEEE Access, 8: 58603-58619, 2020.

[17] Z. Torabi, G. Jaberipur, “Low-power/cost RNS comparison via partitioning the dynamic range,” IEEE Trans. Very Large Scale Integr. VLSI Syst., 24(5): 1849-1857, 2016.

[18] Z. Torabi, A. Belghadr, “Efficient RNS comparator via dynamic range partitioning: The case of {2^N - 1, 2^N, 2^(N+1) -1},” CSI J. Comput. Sci. Eng., 16(2): 38-43, 2019.

[19] K. Isupov, “High-performance computation in residue number system using floating-point arithmetic,” Comput., 9(2): 9-24, 2021.

[20] V. A. Krasnobayev, A. S. Yanko, S. A. Koshman. "A method for arithmetic comparison of data represented in a residue number system," Cybern. Syst. Anal., 52(1): 145-150, 2016.

[21] V. Krasnobayev, S. Koshman, K. Myslyvtsev,, K. Kuznetsova, , T. Ivko, T. Katkova, “Method of arithmetic comparison of data in the residue numeral system,” in Proc. IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S&T): 483-487, 2019.

[22] M. Babenko, S. J. Piestrak, N. Chervyakov, M. Deryabin, “The study of monotonic core functions and their use to build RNS number comparators,” Electron., 10(9): 1041, 2021.

[23] M. Babenko, M. Deryabin, S. J. Piestrak, P. Patronik, N. Chervyakov, A. Tchernykh, A. Avetisyan, “RNS number comparator based on a modified diagonal function,” Electron., 9(11): 1784, 2020.

[24] H. Ahmadifar, G. Jaberipur, “A new residue number system with 5-Moduli Set: {2^2q, 2 ^q ±3, 2 ^q±1},” The Comput. J., 58: 1548-1565, 2014.

[25] M. Mojahed, A. S. Molahosseini, A. A. E. Zarandi, “A multifunctional unit for reverse conversion and sign detection based on the 5-moduli set,” Comput. Sci., 22(1), 2021.

[26] N. S. Szabó, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology. New York, NY, SA: McGraw-Hill, 1967.

[27] L. Sousa, P. Martins, “Efficient sign identification engines for integers represented in RNS extended 3-moduli set {2ⁿ − 1, 2ⁿ ^{+ k} , 2ⁿ + 1},” 50(16): 1138-1139, 2014.

[28] M. Xu, Z. Bian, R. Yao, “Fast sign detection algorithm for the RNS moduli set {2^{n+ 1}-1, 2^{n}-1, 2^{n}\},” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 23(2): 379-383, 2014.

[29] Y. Wang, “New Chinese remainder theorems,” in Proc. IEEE Asilomar Conference on Signals, Systems and Computers: 165-171, 1998.

[30] P. Boyvalenkov, N. I. Chervyakov, P. Lyakhov, N. Semyonova, A. Nazarov, M. Valueva, G. Boyvalenkov, D. Bogaevskiy, D. Kaplun, “Classification of moduli sets for residue number system with special diagonal function,” IEEE Access, 8: 156104-156116, 2020.

[31] M. Valueva, G. Valuev, N. Semyonova, P. Lyakhov, N. Chervyakov, D. Kaplun, D. Bogaevskiy, “Construction of residue number system using hardware efficient diagonal function,” Electron., 8(6): 694, 2019.

[32] G. Dimauro, S. Impedovo, G. Pirlo, “A new technique for fast number comparison in the residue number system,” IEEE Trans. Comput., 42(5): 608-612, 1993.

[33] B. Cao, C. H. Chang, T. Srikanthan, “Adder based residue to binary converters for a new balanced 4-moduli set,” in Proc. IEEE International Symposium on Image and Signal Processing and Analysis: 820-825, 2003.

[34] A. Tyagi, “A reduced-area scheme for carry-select adders,” IEEE Trans. on Comput., 42: 63–70, 1993.

LETTERS TO EDITOR

Journal of Electrical and Computer Engineering Innovations (JECEI) welcomes letters to the editor for the post-publication discussions and corrections which allows debate post publication on its site, through the Letters to Editor. Letters pertaining to manuscript published in JECEI should be sent to the editorial office of JECEI within three months of either online publication or before printed publication, except for critiques of original research. Following points are to be considering before sending the letters (comments) to the editor.

[1] Letters that include statements of statistics, facts, research, or theories should include appropriate references, although more than three are discouraged.

[2] Letters that are personal attacks on an author rather than thoughtful criticism of the author’s ideas will not be considered for publication.

[3] Letters can be no more than 300 words in length.

[4] Letter writers should include a statement at the beginning of the letter stating that it is being submitted either for publication or not.

[5] Anonymous letters will not be considered.

[6] Letter writers must include their city and state of residence or work.

[7] Letters will be edited for clarity and length.

Name *

Email Address *

Affiliation *

Comments *

Security Code *

Journal of Electrical and Computer Engineering Innovations (JECEI)

Fast and Power Efficient Signed/Unsigned RNS Comparator & Sign Detector

References

References

Send comment about this article

Volume 11, Issue 1
January 2023
Pages 41-50

Fast and Power Efficient Signed/Unsigned RNS Comparator & Sign Detector

References

References

Send comment about this article

Volume 11, Issue 1January 2023Pages 41-50

Volume 11, Issue 1
January 2023
Pages 41-50