Hybrid Design of Forward and Reverse Converters: A New Approach to Reduce Hardware Complexity of Residue Number System

Document Type : Original Article

Authors

1 Department of Computer Engineering, Shahid Bahonar University of Kerman, Kerman, Iran

2 Department of Computer Engineering, Islamic Azad University Kerman Branch, Kerman, Iran,

Abstract

The Residue Number System (RNS) hardware structure consists of several components, including forward converter, separate arithmetic units for performing modular addition and multiplication, and reverse converter. Forward and reverse converters, essential in any RNS to interface with other digital circuits, represent overhead, resulting in larger chip-area and power-consumption. This work, for the first time, proposes a hybrid converter for RNS, which unifies forward and reverse converters by re-using hardware. To achieve this aim, the mixed-radix conversion (MRC) algorithm has been used for putting up the reverse conversion formulas in a similar format to forward conversion formulas. The VLSI implementation results of the proposed hybrid converter based on TSMC-65nm technology for the moduli set {2n−1, 22n, 2n+1−1} show a reduction up to 19% of the required area in comparison to the total area of the forward and reverse converters. However, the delay of the proposed hybrid converter is just 10% higher than individual reverse converter delay.

Keywords

References

[1]      Systems Design with Special Arithmetic and Number Systems, Springer International Publishing, 2017.
[2]      امیر سزاوار، حسن فرسی، سجاد محمدزاده، «بازیابی تصویر مبتنی بر محتوا با استفاده از شبکه‌های عصبی کانولوشن عمیق»، مجله مهندسی برق دانشگاه تبریز، دوره 48، شماره 4، صفحه 1595-1603، زمستان 1397.
[3]      پرهام درّی، علی قیاسیان، حسین سعیدی، «طراحی و پیاده‌سازی رمزنگار AES در بستر FPGA برای خطوط پرسرعت»، مجله مهندسی برق دانشگاه تبریز، دوره 46، شماره 1، صفحه 153-167، بهار 1395.
[4]      H.L. Garner, “The residue number system,” IRE Transactions on Electronic Computers, vol. 8, no. 2, pp. 140-147, Jun. 1959.
[5]      C.H. Chang, A.S. Molahosseini, A.A. Emrani 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 and Systems Magazine, vol. 15, no. 4, pp. 26-44, Nov. 2015.
[6]      L. Sousa, S. Antão and P. Martins, “Combining residue arithmetic to design efficient cryptographic circuits and systems,” IEEE Circuits and Systems Magazine, vol. 16, no. 4, pp. 6-32, Nov. 2016.
[7]      V. Arrigoni, B. Rossi, P. Fragneto and G. Desoli, “Approximate operations in convolutional neural networks with RNS data representation,” In Proc. of 25th European Symposium on Artificial Neural Networks, Bruges, Belgium, Apr. 26-28 2017.
[8]      K. Navi, A.S. Molahosseini and M. Esmaeildoust, “How to teach residue number system to computer scientists and engineers,” IEEE Transactions on Education, vol. 54, no. 1, pp. 156-163, Feb. 2011.
[9]      S. J. Piestrak, “Design of residue generators and multioperand modular adders using carry-save adders,” IEEE Transactions on Computers, vol. 43, no. 1, pp. 68-77, Jan. 1994.
[10]      A. A. Hiasat, “Arithmetic binary to residue encoders for moduli (2n±2k+1),” IEEE Proceedings - Computers and Digital Techniques, vol. 150, no. 6, pp. 369-374, Nov. 2003.
[11]      C. Efstathiou, N. Moschopoulos, K. Tsoumanis and K. Pekmestzi, “On the design of configurable modulo 2n±1 residue generators,” In. Proc. of 15th Euromicro Conference on Digital System Design, Izmir, Turkey, pp. 50-56, 2012.
[12]      P. M. Matutino, R. Chaves and L. Sousa, “Arithmetic-based binary-to-RNS converter modulo {2n±k} jn-bit dynamic range,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 3, pp. 603-607, Mar. 2015.
[13]      S.J. Piestrak, “A high speed realization of a residue to binary converter,” IEEE Transactions on Circuits and Systems-II, vol. 42, no. 10, pp. 661-663, Oct. 1995.
[14]      Y. Wang, X. Song, M. Aboulhamid and H. Shen, “Adder based residue to binary numbers converters for (2n-1, 2n, 2n+1),” IEEE Transactions Signal Processing, vol. 50, no. 7, pp. 1772-1779, Jul. 2002.
[15]      B. Cao, C. H. Chang and T. Srikanthan, “An efficient reverse converter for the 4-moduli set {2n-1, 2n, 2n+1, 22n+1} based on the new Chinese remainder theorem,” IEEE Transaction on Circuits and Systems- I, vol. 50, no. 10, pp. 1296-1303, Oct. 2003.
[16]      A. Hariri, K. Navi, and R. Rastegar, “A new high dynamic range moduli set with efficient reverse converter,” Journal of Computers and Mathematics with Applications, vol. 55, no. 4, pp. 660-668, Feb. 2008.
[17]      A.S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi, “Efficient reverse converter designs for the new 4-moduli sets {2n–1, 2n, 2n+1, 22n+1–1} and {2n–1, 2n+1, 22n, 22n+1} based on new CRTs,” IEEE Transactions on Circuits and Systems-I, vol. 57, no. 4, pp. 823-835, Apr. 2010.
[18]      L. Sousa and S. Antao, “MRC-based RNS reverse converters for the four-moduli sets {2n+1, 2n-1, 2n, 22n+1-1} and {2n+1, 2n-1, 22n, 22n+1-1},” IEEE Transactions on Circuits and Systems II, vol. 59, no. 4, pp. 244-248, Apr. 2012.
[19]      A.S. Molahosseini, K. Navi, C. Dadkhah, M. Eshghi. “Efficient MRC-based residue to binary converters for the new moduli sets {22n, 2n−1, 2n+1−1} and {22n, 2n−1, 2n−1−1},” IEICE Transactions on Information and Systems, vol. 92, no. 9, pp. 1628-1638, Sep. 2009.
[20]      A.A.E. Zarandi, A.S. Molahosseini, M. Hosseinzadeh, S. Sorouri, S.F. Antão and L. Sousa, “Reverse converter design via parallel-prefix adders: novel components, methodology and implementations,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 2, no. 374-378, p. 23, Feb. 2015.
[21]      A.A.E. Zarandi, A.S. Molahosseini, L. Sousa and M. Hosseinzadeh, “An efficient component for designing signed reverse converters for a class of RNS moduli sets with composite form {2K, 2P-1},” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 1, pp. 48-59, Jan. 2017.
[22]      A. S. Molahosseini, A. A. E. Zarandi, P. Martins and L. Sousa, “A Multifunctional Unit for Designing Efficient RNS-Based Datapaths,” IEEE Access, vol. 5, pp. 25972-25986, Dec. 2017.
[23]      P.V.A. Mohan, Residue Number Systems: Theory and Applications, Springer International Publishing, 2016.
TABRIZ JOURNAL OF ELECTRICAL ENGINEERING
Volume 50, Issue 3 - Serial Number 93
November 2020
Pages 1315-1328

Files

Share

How to cite

Statistics