SIGN detection and signed integer comparison for three-moduli SET {2n ±1, 2n+k}

• Autorzy: Torabi Zeinab , Timarchi Somayeh

Identyfikatory

DOI

10.7494/csci.2021.22.3.3955

• Języki publikacji: EN

Abstrakty

EN

Comparison, division, and sign detection are considered to be complicated op erations in a residue number system (RNS). A straightforward solution is to convert RNS numbers into binary formats and then perform complicated op erations using conventional binary operators. If efficient circuits are provided for comparison, division, and sign detection, the application of RNS can be extended to those cases that include these operations. For RNS comparison in three-moduli set τ = {2 n−1, 2 n+k , 2 n+1},(0 ≤ k ≤ n), we have found only one hardware realization. In this paper, an efficient RNS comparator is proposed for moduli set τ , which employs a sign-detection method and operates more efficiently than its counterparts. The proposed sign detector and comparator utilize dynamic range partitioning (DRP), which has been recently presented for unsigned RNS comparison. The delay and cost of the proposed comparator are lower than the previous works, which makes it appropriate for RNS applications with limited delay and cost.

Słowa kluczowe

EN

computer arithmetic; residue number system; signed integer comparison; dynamic range partitioning

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2021
• Tom: T. 22 (3)
• Strony: 387–401
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Torabi Zeinab

• Shahid Rajaee Teacher Training University, Department of Computer Engineering, Tehran, Iran

autor

Timarchi Somayeh

• Somayeh Timarchi Shahid Beheshti University, Faculty of Electrical Engineering, Tehran, Iran

Bibliografia

• [1] Alhassan I.Z., Ansong E.D., Abdul-Salaam G., Alhassan S.: Enhancing Image Security during Transmission using Residue Number System and k-shuffle, Earth line Journal of Mathematical Sciences, vol. 4(2), pp. 399–424, 2020.
• [2] Bi S., Gross W.J.: The Mixed-Radix Chinese Remainder Theorem and Its Appli cations to Residue Comparison, IEEE Transactions on Computers, vol. 57(12), pp. 1624–1632, 2008.
• [3] Boyvalenkov P., Chervyakov N.I., Lyakhov P., Semyonova N., Nazarov A., Val ueva M., Boyvalenkov G., Bogaevskiy D., Kaplun D.: Classification of Moduli Sets for Residue Number System With Special Diagonal Functions, IEEE Access, vol. 8, pp. 156104–156116, 2020.
• [4] Cardarilli G.c., Di Nunzio L., Fazzolari R., Nannarelli A., Petricca M., Re M.: Design Space Exploration based Methodology for Residue Number System Digital Filters Implementation, IEEE Transactions on Emerging Topics in Computing, 2020.
• [5] Dimauro G., Impedovo S., Pirlo G., Salzo A.: RNS architectures for the imple mentation of the ‘diagonal function’, Information Processing Letters, vol. 73(5–6), pp. 189–198, 2000.
• [6] Gbolagade K.A., Chaves R., Sousa L., Cotofana S.D.: Residue-to-Binary Con verters for the Moduli Set {2 2n+1 − 1, 2 2n, 2 n − 1}. In: 2009 2nd International Conference on Adaptive Science & Technology (ICAST), pp. 26–33, IEEE, 2009.
• [7] Gbolagade K.A., Chaves R., Sousa L., Cotofana S.D.: An improved RNS reverse converter for the {2 2n+1−1, 2 2n, 2 n−1} moduli set. In: Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pp. 2103–2106, IEEE, 2010.
• [8] Hiasat A.: A Residue-to-Binary Converter With an Adjustable Structure for an Extended RNS Three-Moduli Set, Journal of Circuits, Systems and Computers, vol. 28(08), p. 1950126, 2019.
• [9] Hiasat A., Sousa L.: Sign Identifier for the Enhanced Three Moduli Set {2 n+k , 2 n − 1, 2 n+1 − 1}, Journal of Signal Processing Systems, vol. 91(8), pp. 953–961, 2019.
• [10] Isupov K.: Using Floating-Point Intervals for Non-Modular Computations in Residue Number System, IEEE Access, vol. 8, pp. 58603–58619, 2020.
• [11] Kalampoukas L., Efstathiou C., Nikolos D., Vergos H.T., Kalamatianos J.: High-speed parallel-prefix modulo 2n−1 adders, 2006. Google Patents, Patent: US7155473B2.
• [12] Krasnobayev V., Yanko A., Koshman S.: A Method for Arithmetic Comparison of Data Represented in a Residue Number System, Cybernetics and Systems Analysis, vol. 52(1), pp. 145–150, 2016.
• [13] Kumar S., Chang C.H., Tay T.F.: Algorithm for Signed Integer Compari son in 2n+k , 2 n − 1, 2 n + 1, 2 n±1 − 1 and Its Efficient Hardware Implementa tion, IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 64(6), pp. 1481–1493, 2016.
• [14] Latha M.V.N.M., Rachh R.R., Mohan P.V.A.: RNS-to-Binary Converters for a Three-Moduli Set {2 n−1 − 1, 2 n − 1, 2 n+k}, IETE Journal of Education, vol. 58(1), pp. 20–28, 2017. doi: 10.1080/09747338.2017.1317040.
• [15] Mohan P.V.A.: RNS-To-Binary Converter for a New Three-Moduli Set 2 n+1 − 1, 2 n, 2 n − 1, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 54(9), pp. 775–779, 2007.
• [16] Salamat S., Imani M., Gupta S., Rosing T.: Rnsnet: In-Memory Neural Net work Acceleration Using Residue Number System. In: 2018 IEEE International Conference on Rebooting Computing (ICRC), pp. 1–12, IEEE, 2018.
• [17] Samimi N., Kamal M., Afzali-Kusha A., Pedram M.: Res-DNN: A Residue Num ber System-Based DNN Accelerator Unit, IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 67(2), pp. 658–671, 2019.
• [18] Schoinianakis D.: Residue arithmetic systems in cryptography: a survey on modern security applications, Journal of Cryptographic Engineering, vol. 10(3), pp. 249–267, 2020.
• [19] Sousa L.: Efficient Method for Magnitude Comparison in RNS Based on Two Pairs of Conjugate Moduli. In: 18th IEEE Symposium on Computer Arithmetic (ARITH’07), pp. 240–250, IEEE, 2007.
• [20] Sousa L., Martins P.: Sign Detection and Number Comparison on RNS 3-Moduli Sets {2 n − 1, 2 n+k , 2 n + 1}, Circuits, Systems, and Signal Processing, vol. 36(3), pp. 1224–1246, 2017.
• [21] Szab´o N.S., Tanaka R.I.: Residue arithmetic and its applications to computer technology, McGraw-Hill, 1967.
• [22] Torabi Z., Jaberipur G.: Low-Power/cost RNS Comparison via Partitioning the Dynamic Range, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 24(5), pp. 1849–1857, 2015.
• [23] Torabi Z., Jaberipur G.: Fast low energy RNS comparators for 4-moduli sets {2 n±1 , 2 n, m} with m ∈ {2 n+1±1, 2 n−1−1}, Integration, vol. 55, pp. 155–161, 2016. doi: 10.1016/j.vlsi.2016.05.009.
• [24] Torabi Z., Jaberipur G., Belghadr A.: Fast division in the residue number system {2 n + 1, 2 n, 2 n − 1} based on shortcut mixed radix conversion, Computers & Electrical Engineering, vol. 83, p. 106571, 2020.
• [25] Wang Y.: New Chinese remainder theorems. In: Conference Record of Thirty Second Asilomar Conference on Signals, Systems and Computers (Cat. No. 98CH36284), vol. 1, pp. 165–171, IEEE, 1998.
• [26] Wang Y., Song X., Aboulhamid M.: A new algorithm for RNS magnitude com parison based on new Chinese remainder theorem II. In: Proceedings Ninth Great Lakes Symposium on VLSI, pp. 362–365, IEEE, 1999.
• [27] Youssef M.I., Emam A.E., Abd Elghany M.: Image multiplexing using residue number system coding over MIMO-OFDM communication system, International Journal of Electrical & Computer Engineering, vol. 9(6), pp. 4815–4825, 2019. doi: 10.11591/ijece.v9i6.pp4815-4825.

Uwagi

PL

„Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).”