Volume 20, Issue 1 (6-2023)                   JSDP 2023, 20(1): 123-132 | Back to browse issues page

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Ahmadifar H, Hakimi Z. Set the Domain for Using 3-moduli set {2^n-1, 2^n, 2^n +1}. JSDP 2023; 20 (1) : 7
URL: http://jsdp.rcisp.ac.ir/article-1-1214-en.html
Set the Domain for Using 3-moduli set {2^n-1, 2^n, 2^n +1}
HamidReza Ahmadifar * , Zahra Hakimi
University of Guilan
Abstract:   (794 Views)
In special purpose circuits, the amount of energy consumed and the speed of operation are the main challenges. There are wide researches and methods to improve the performance of these types of circuits. One of these methods is to use a Residue Number System (RNS). In the RNS, there are a number of modules (channels) as a set to represent the number and perform parallel arithmetic operations. The most famous set is the 3-modlui set {2n-1, 2n, 2n +1}. The form of modules to the power of 2 makes it easier to perform binary computational operations. To use this system, you need to perform conversion operations from binary to residue (forward conversion) and residue to binary (reverse conversion). The greater the number of modules (channels) in the set, the higher the degree of parallelism of computational operations. In contrast, more complex forward and reverse conversion circuits are required. The overhead of conversion computing can reduce the efficiency of using this system, unless the number of consecutive operations is large enough to cover the conversion overhead time. In this paper, based on 3-moduli set {2n-1, 2n, 2n +1} evaluation, it was determined that for how many consecutive addition or multiplication operations, the use of RNS operations leads to greater speed. In this paper, we evaluate the carry propagation adder as the most popular adder and parallel prefix adder as the high speed adder. Also, the parallel block multiplier circuit was used to evaluate the multiplication operations. First, modular adder/multiplier, binary, and forward and reverse conversion circuits were implemented and synthesized. We used Synopsys Design Compiler, K-2015.06 version and 45nm technology. The results show that if the carry propagation adder is used, in modules with a width of more than 8 bits (n≥8), if the number of consecutive operations is at least 4, it will speed up the calculations. Likewise, in the multiplication operation and parallel prefix addition, the number of sequences is reduced to two.
Article number: 7
Keywords: Residue Number System, Residue Operations, Carry Ripple Adder, Parallel Prefix Adder, Parallel Multiplier
Full-Text [PDF 1904 kb]   (298 Downloads)    
Type of Study: Applicable | Subject: Paper
Received: 2021/03/2 | Accepted: 2023/02/22 | Published: 2023/08/13 | ePublished: 2023/08/13
References
1. [1] Hakimi, Z., Ahmadifar, H.," Delimitation for Using Residue Number Systems", 4th Conference on Electrical and Computer Engineering Technology, E-TECH2019, ITRC, Tehran, 1398.
2. [2] Omondi, A., Premkumar, B., "Residue Number Systems - Theory and Implementation", Imperial College Press (ICP), 2007. [DOI:10.1142/9781860948671]
3. [3] Belghadr, A., Jaberipur, G., "FIR Filter Realization via Deferred End-Around Carry Modular Addition", IEEE TCAS I, Vol. 65, pp. 2878 - 2888, 2018. [DOI:10.1109/TCSI.2018.2798595]
4. [4] Xiao, L., Xiang-Gen, X., "Robust Polynomial Reconstruction via Chinese Remainder Theorem in the Presence of Small Degree Residue Errors", IEEE TCAS II: Vol. 65 , Issue: 11, pp. 1778 - 1782, 2018. [DOI:10.1109/TCSII.2017.2756343]
5. [5] Sousa, L., Antao, S., Martins, P., "Combining Residue Arithmetic to Design Efficient Cryptographic Circuits and Systems", IEEE Circuits and Systems Magazine, Vol.16, Issue:4, pp. 6-32, 2016. [DOI:10.1109/MCAS.2016.2614714]
6. [6] Tay, T., Chang, C.-H., "A non-iterative multiple residue digit error detection and correction algorithm in RRNS", IEEE Transactions on Computers, Vol. 65 , Issue: 2, pp. 396 - 408, 2016. [DOI:10.1109/TC.2015.2435773]
7. [7] Koren I, "Computer Arithmetic Algorithms", 2d Edition, A.K. Peters Ltd, 2002.
8. [8] Hiasat, A, "An Efficient Reverse Converter for the Three-Moduli Set { 2^(n+1)-1,2^n,2^n-1 }", IEEE Transactions on Circuits and Systems II, Vol. 64, Issue: 8 pp. 962 - 966, 2017. [DOI:10.1109/TCSII.2016.2608335]
9. [9] Ahmadifar, A., and G. Jaberipur, "Improved modulo-2^q±3 multipliers," in Proc. Of the 17th CSI International Symposium on Computer Architecture and Digital Systems (CADS2013), Tehran, Iran, pp. 31-35.
10. [10] Patronik, P., Piestrak, S.J., "Hardware/Software Approach to Designing Low-Power RNS-Enhanced Arithmetic Units," IEEE TCAS I, Vol. 64, 2017. [DOI:10.1109/TCSI.2017.2669108]
11. [11] Ahmadifar, H., Jaberipur, G., "A New Residue Number System with 5-Moduli Set: {22q,2q±3,2q±1}", The Computer Journal, Vol. 58 , Issue: 7, pp.1548 - 1565, 2015. [DOI:10.1093/comjnl/bxu084]
12. [12] Wang Y, Song X, Aboulhamid M, Shen H, " Adder Based Residue to Binary Number Converters for {2^n- 1,2^n,2^n + 1}", IEEE Transactions on Signal Processing, Vol. 50, No. 7, July 2002. [DOI:10.1109/TSP.2002.1011216]
13. [13] Jaberipur, G., B. Parhami, and S. Nejati, "On Building General Modular Adders from Standard Binary Arithmetic Components," Proc. 45th Asilomar Conf. Signals, Systems, and Computers, 6-9 Nov., Pacific Grove, CA, USA, pp. 154-159, 2011. [DOI:10.1109/ACSSC.2011.6189975]
14. [14] Kalamatianos L, Nikolos D, Efstathiou C, T. Vergos H, Kalamatianos J, "High-Speed Parallel-Prefix Modulo 2^n-1 Adders," IEEE Trans. Computers, Vol. 49, No. 7, special issue on computer arithmetic, pp. 673-680, July 2000. [DOI:10.1109/12.863036]
15. [15] Efstathiou C., H. T. Vergos, and D. Nikolos, "Fast Parallel-Prefix 2^n+1 Adder", IEEE Trans. on Computers, Vol. 53, No. 9, pp. 1211-1216, September 2004. [DOI:10.1109/TC.2004.60]
16. [16] Jaberipur G, Alavi H, "Comment on "Fast Parallel Prefix Modulo 2^n+1 Adder", IEEE Trans. on Computers, Vol. 64, No. 1, pp. 293-294, January 2015. [DOI:10.1109/TC.2013.160]
17. [17] Cardirilli, G.C., Nunzio, L.D., Fazzolari, R., Nannarelli, A., et al," Design Space Exploration Based Methodology for Residue Number System Digital Filters Implementation", IEEE Trans. On Emerging Topics in Computing, Early Access,25 May, 2020.
Add your comments about this article : Your username or Email:
CAPTCHA
Send email to the article author

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2015 All Rights Reserved | Signal and Data Processing