Magnitude Comparison and Sign Detection based on the 4-Moduli Set {2n+1, 2n−1, 2n+3, 2n−3}

Majlesi Journal of Electrical Engineering

مقاله 9، دوره 15، شماره 3، آذر 2021، صفحه 93-103   

نوع مقاله: Review Article

شناسه دیجیتال (DOI): 10.52547/mjee.15.3.93

نویسندگان

Mohsen Mojahed¹؛ Amir Sabbagh Molahosseini^{* 1}؛ Azadeh Alsadat Emrani Zarandi²

¹Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran.

²Department of Computer Engineering, Shahid Bahonar University of Kerman, Kerman, Iran. Email: [e-mail]

چکیده

The 4-moduli set residue number system (RNS),{2n+1, 2n−1, 2n+3, 2n−3}, with a wide dynamic range, has recently been proposed as a balanced 4-moduli set for utilizing the cases that demand fast calculations such as deep learning and implementation of asymmetric cryptographic algorithms. Up to now, only an unsigned reverse converter has been designed for this moduli set. Thus, there is a need for two separate units, a sign detection circuit, and a comparator to use this set in cases requiring sign and comparison. Nevertheless, the existence of these components demands high hardware that makes the implementation of the RNS impractical. Therefore, this paper presents the design of a sign detection circuit and a signed reverse converter that can overcome this problem by reusing the hardware. To achieve an integrated hardware design, first, we optimized the previous unsigned reverse converter for this 4-moduli set and next, we derived an approach from the structure of the reverse convertor for detecting signs and recognizing comparators. Finally, using the sign signals extracted from the reverse converter, we change reverse convertor into a unit that perform sign detection and comparison. The simulation has been conducted using ISE Design Suite 14.7 tool and the Spartan6 family technology. Empirical results show that, the proposed multifunctional unit has an approximately identical performance with respect to delay and area compared to the previous reverse converter. Besides, the proposed signed reverse converter relies on a 46% and 28% reduction in area and delay compared to the previous unsigned reverse converter which uses a comparator and also a multiplexer to detect a sign in the output.

کلیدواژه‌ها

Residue Number System؛ Reverse Converter؛ Computer Arithmetic؛ Sign Detection

مراجع

H. L. Garner, "The Residue Number System," in IRE Transactions on Electronic Computers, Vol. EC-8, No. 2, pp. 140-147, June 1959.

P. V. A. Mohan, “Residue Number Systems: Theory and Applications”, Switzerland:Springer, 2016.

C. 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," in IEEE Circuits and Systems Magazine, Vol. 15, No. 4, pp. 26-44, Fourthquarter 2015.

L. Sousa, S. Antao and P. Martins, "Combining Residue Arithmetic to Design Efficient Cryptographic Circuits and Systems," in IEEE Circuits and Systems Magazine, Vol. 16, No. 4, pp. 6-32, Fourthquarter 2016.

B. Moons, D. Bankman, and M. Verhelst, “Embedded deep learning: algorithms, architectures and circuits for always-on neural network processing”. Cham, Switzerland: Springer, 2019.

d’Acremont, Antoine; Fablet, Ronan; Baussard, Alexandre; Quin, Guillaume. 2019. "CNN-Based Target Recognition and Identification for Infrared Imaging in Defense Systems" Sensors 19, No. 9: 2040.

N. Samimi, M. Kamal, A. Afzali-Kusha and M. Pedram, "Res-DNN: A Residue Number System-Based DNN Accelerator Unit," in IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 67, No. 2, pp. 658-671, Feb. 2020.

S. Salamat, M. Imani, S. Gupta and T. Rosing, "RNSnet: In-Memory Neural Network Acceleration Using Residue Number System," 2018 IEEE International Conference on Rebooting Computing (ICRC), McLean, VA, USA, 2018, pp. 1-12.

X. Zheng, B. Wang, C. Zhou, X. Wei and Q. Zhang, "Parallel DNA Arithmetic Operation With One Error Detection Based on 3-Moduli Set," in IEEE Transactions on NanoBioscience, Vol. 15, No. 5, pp. 499-507, July 2016

P. Martins and L. Sousa, "The Role of Non-Positional Arithmetic on Efficient Emerging Cryptographic Algorithms," in IEEE Access, Vol. 8, pp. 59533-59549, 2020.

K. Navi, A. S. Molahosseini and M. Esmaeildoust, "How to Teach Residue Number System to Computer Scientists and Engineers," in IEEE Transactions on Education, Vol. 54, No. 1, pp. 156-163, Feb. 2011.

P. V. A. Mohan, "RNS-To-Binary Converter for a New Three-Moduli Set {2^((n+1) ),2^n,2^n-1}," in IEEE Transactions on Circuits and Systems II: Express Briefs, Vol. 54, No. 9, pp. 775-779, Sept. 2007.

P. V. A. 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}," in IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 54, No. 6, pp. 1245-1254, June 2007.

Y. Wang, X. Song, M. Aboulhamid and H. Shen, "Adder based residue to binary number converters for {2^n-1,2^n,2^n+1}," in IEEE Transactions on Signal Processing, Vol. 50, No. 7, pp. 1772-1779, July 2002.

A. Hiasat and A. Sweidan, "Residue number system to binary converter for the moduli set {2^(n-1),2^n-1,2^n+1}", Elsevier J. Syst. Architect., Vol. 49, pp. 53-58, 2003.

P. A. Mohan, “New reverse converters for the moduli set {2^n-1,2^n+1,2^n-3,2^n+3},” AEU - International Journal of Electronics and Communications, Vol. 62, No. 9, pp. 643 – 658, 2008.

A.. Hiasat, "A New Scaler for the Expanded 4-Moduli Set {2^K-1,2^K+1,2^2K+1,2^2k}," 2020 11th International Conference on Information and Communication Systems (ICICS), Irbid, Jordan, 2020, pp. 429-433.

Hiasat, A. Sweidan, “Residue number system to binary converter for the moduli set {2^(n-1),2^n-1,2^n+1},” International Elsevier Journal of Systems Architecture 49, pp. 53–58, 2003.

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

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^(n+1)-1} and {2^n-1,2^2n,2^n+1,2^2n+1} Based on New CRTs," in IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 57, No. 4, pp. 823-835, April 2010.

P. M. Matutino, R. Chaves and L. Sousa, "Binary-to-RNS Conversion Units for moduli {2^n±3}," 2011 14th Euromicro Conference on Digital System Design, Oulu, 2011, pp. 460-467.,

G. Jaberipur, H. Ahmadifar, “A ROM-less Reverse RNS Converter for Moduli Set

{2^n±1,2^n±3},” IET Computers & Digital Techniques, Vol. 8, No. 1, pp. 11-22, Jan 2014.

H. Ahmadifar, G. Jaberipur, “A New Residue Number System with 5-Moduli Set:{2^2q,2^q±1,2^q±3},” The Computer Journal, Vol. 58, Issue 7, July 2015, Pages 1548–1565.

N. Stamenković, B. Jovanović and V. Stojanović, "Reverse conversion for residue number system realizations of digital signal processing hardware," Proc. 18th Telecommun. Forum (TELFOR), pp. 1-4, 2010.

Hiasat and L. Sousa, ‘‘Sign identifier for the enhanced three moduli set {2^(n+k),2^n-1,2^(n+1)-1},’’ J. Signal Process. Syst., Vol. 91, No. 8, pp. 953–961, Aug. 2019.

Hiasat and L. Sousa, ‘‘On the design of RNS inter-modulo processing units for the arithmetic-friendly moduli sets {2^(n+k),2^n-1,2^(n+1)-1},’’ Comput. J., Vol. 62, no. 2, pp. 292–300, 2018.

L. Sousa and P. Martins, " Sign detection and number comparison on RNS 3-moduli sets {2^n-1,2^(n+x),2^n+1}", Circuits Syst. Signal Process., Vol. 36, No. 3, pp. 1224-1246, 2017.

S. Kumar and C. Chang, "A VLSI-efficient signed magnitude comparator for {2^n-1,2^n,2^(2n+1)-1} RNS," 2016 IEEE International Symposium on Circuits and Systems (ISCAS), Montreal, QC, 2016, pp. 1966-1969.

R. Kumar and R. A. Mishra, "Design of Efficient Sign Detector for Moduli Set {2^n-1,2^n,2^n+1} in Residue Number System," 2019 International Conference on Electrical, Electronics and Computer Engineering (UPCON), ALIGARH, India, 2019, pp. 1-5.

S. Kumar and C. Chang, "A Scaling-Assisted Signed Integer Comparator for the Balanced Five-Moduli Set RNS {2^n-1,2^n,2^n+1,2^(n+1)-1,2^(n-1)-1}," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 25, No. 12, pp. 3521-3533, Dec. 2017.

Emrani Zarandi, A. Molahosseini, L. Sousa and M. Hosseinzadeh, "An Efficient Component for Designing Signed Reverse Converters for a Class of RNS Moduli Sets of Composite Form {2^K,2^P-1}," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 25, No. 01, pp. 48-59, 2017.

S. Molahosseini, A. A. E. Zarandi, P. Martins and L. Sousa, "A Multifunctional Unit for Designing Efficient RNS-Based Datapaths," in IEEE Access, Vol. 5, pp. 25972-25986, 2017.

M. Mojahed, A. S. Molahosseini, A. A. E. Zarandi, "A Multifunctional Unit For Reverse Conversion and Sign Detection Based on The 5-Moduli Set," Computer Science 22, No. 1, 2021.