Residue to Binary Converter for a Four Moduli Set

Abstract

Due to issues with conventional number systems (binary), such as the carry propagation issue, which reduces the performance of hardware computing systems, residue number systems (RNS) have gained popularity. Residue to binary conversion speed and complexity, as well as the speed of the internal RNS arithmetic unit, all affect how well a residue number system (RNS) performs. We have included a number of studies on the recognition of RNS Number Systems and Residue to Binary Converter Systems for various moduli sets in this paper. Additionally, we implemented a model and calculated the value of LUT’S, Slices and other components within it.

Introduction

I. INTRODUCTION

A unique and unweighted arithmetic number representation is the residue number system (RNS). A collection of co-prime integers is used to represent numbers that fall inside a specific dynamic range. It uses a carry-free mechanism for its mathematical representation, RNS. This suggests that there won't be any carry that spreads among the bits of the same digit. This resulted in an arithmetic form that is computationally quick since carry need not be propagated across multiple digits.[1]

This crucial RNS characteristic is only applicable to addition, subtraction, and multiplication. Other crucial function, such as the conversion of residue to base two system, sign analogy, scaling, etc. require more time than equivalent operations in base two arithmetic.[2] Although RNS is not majorly used in general-purpose processors, application-specific processors that primarily rely on  basic operations like add, subtract and multiply can benefit from RNS's carry-free characteristic. [3][4]

As a result, RNS has been effectively employed in a number of high-speed computation-required applications, including communication systems, digital signal and image processing, digital sweep oscillators, digital filters, embedded systems, parallel DNA calculations, and cryptographic systems. RNS has gained appeal in new applications including deep neural networks, memory processing, efficient video coding, and current cryptosystems in order to enhance the value of DSPs.[5][6]

The crucial requirements that make RNS a feasible choice to integrate demanding applications in embedded systems and Internet of Things Devices are to improve performance, reduce power consumption, and increase dependability.[7]

To have more successful RNS-based execution of such applications, they must have sufficient parallelism and dynamic range. Class-1 and Class-2 are the two basic subcategories of parallelism. One modulus in Class-1 must be a power of 2, while the multiplication of the other two moduli should be a Mersenne number.  With an extra modulus of m4, the class-2 is a kind of a parallel extension of a kind of Class-1.[8][9] It is not necessary that multiplying all the moduli of class-2 RNS will give a Mersenne number.  Despite its many benefits, the reverse converter's complicated design results from the inter-modular calculations it uses. The primary constituents of RNS based processors are the base two to RNS converter, modulo arithmetic units, and reverse converters. The reverse converter has a complicated, non-modular construction compared to other components.[10] Its design needs to be given more consideration in order to avoid sluggish performance and jeopardizing the advantages of the RNS number system.

The performance of the planned reverse converter is affected by both the properties of the selected moduli set and conversion algorithm. As a result, many moduli sets have been created, and the performance of the RNS depends heavily on the hardware choice.

II. SELECTION OF MODULI SET

The choice of the moduli set in the Residue Number System (RNS) is an important factor that affects the efficiency and accuracy of arithmetic operations. Here are some properties of the moduli set in RNS:

1. Coprimality: The moduli in the RNS moduli set should be pairwise coprime (i.e., they should have no common factors other than 1). This property ensures that every residue combination corresponds to a unique integer, which is essential for accurate arithmetic operations.
2. Large Moduli: larger moduli in the moduli set allow for larger representable integers, which is desirable in many applications. However, larger moduli also require more complex arithmetic operations and larger storage requirements.
3. Prime Moduli: Prime moduli are often preferred in RNS because they offer better properties for arithmetic operations. For example, addition and subtraction operations in RNS with prime moduli can be performed using simple bitwise operations.
4. Balanced Moduli: A balanced moduli set consists of moduli that are close in value to each other. This property can help in significant reduction of the residues dynamic range. This will also help to streamline the arithmetic operations.
5. Reduced Moduli Set: A reduced moduli set consists of a subset of the original moduli set that can represent the same range of integers. A reduced moduli set can improve the efficiency of arithmetic operations by reducing the number of moduli required and the complexity of modular arithmetic.

Overall, a trade-off between accuracy, efficiency, and complexity must be taken into account when selecting the moduli set values in RNS which depends over the application's individual needs.

III. METHODS for RNS to BASE-2 CONVERSIONS

If we have to metamorphose a number from Residue Number System (RNS) to base two (Binary) system, the following steps need to be performed: -

Determine the RNS moduli set: In RNS, the number is represented in terms of residues modulo a set of coprime integers. For example, if we have moduli set {2, 3, 5}, then the RNS depiction of a number X would be (X mod 2, X mod 3, X mod 5).

Compute the product of all moduli in the moduli set. This product is denoted by M.

Compute the inverse of each modulus with respect to M using the Extended Euclidean Algorithm. The inverse of modulus mi with respect to M is denoted by Mi.

Multiply each residue in the RNS representation by its corresponding Mi value.

Add all the products obtained in step 4.

The sum obtained in step 5 is the binary equivalent of the original number.

Let's take an example to illustrate the conversion process from RNS to Binary system:

Suppose we have a number in RNS with moduli set {2, 3, 5}. The RNS depiction of the number is (1, 2, 3).

Compute the product of all moduli: M = 2 x 3 x 5 = 30

Compute the inverse of each modulus with respect to M using the Extended Euclidean Algorithm:

Inverse of 2 with respect to 30: 2 x 15 = 1 (mod 30), so Mi = 15

Inverse of 3 with respect to 30: 3 x 10 = 1 (mod 30), so Mi = 10

Inverse of 5 with respect to 30: 5 x 6 = 1 (mod 30), so Mi = 6

Multiply each residue by its corresponding Mi value:

1 x 15 = 15

2 x 10 = 20

3 x 6 = 18

Add all the products obtained in step 3: 15 + 20 + 18 = 53

The sum obtained in step 4 is the binary equivalent of the original number. Converting 53 to binary, we get 110101.

Therefore, the RNS representation (1, 2, 3) is equivalent to the binary number 110101.

IV. LITERATURE SURVEY

[10] An innovative approach for the implementation of modulo based operations which are required for CRT was provided in this work. We may identify the multiple of the modulus that must be deducted by including a product with 2k of the items in the summation and afterwards only examine the k number of bits which are least significant for us. The technique is also used with adder tree-based CRT systems, within which the aggregate results are reckoned with the help of a variety of dispersed structures. Regarding speed and space occupancy, the resulting architecture seems to be highly appealing. A 32-bit CRT architecture is currently being developed for extremely fast DSP applications. ES2 CMOS 0.7 p technology is being used to create the converter.

Conclusion

The Residue Number System (RNS)\'s intrinsic parallelism and modular arithmetic capabilities are extremely advantageous for the development of application-specific digital signal processors (DSP). Along with providing value to DSPs, RNS is becoming more and more popular in the construction of cutting-edge applications like deep neural networks, high efficiency video coding, contemporary cryptosystems, and memory processing [6]. RNS has several applications in various fields, and its advantages in terms of speed and efficiency make it a useful tool in many applications. RNS is a strong contender for integrating a variety of applications which requires higher amount of computation into embedded systems and IOTdevices by enhancing performance, reducing power consumption, and also improving dependability. This paper outlines a variety of methods for successfully converting the residue number system to base two number systems.

References

[1] Ali Akbari, Mehdi Hosseinzadeh, Shiva TaghipourEivazi, Somayyeh Jafarali Jassbi a New High Speed, Low Area Residue to Binary Converter for the Moduli Set {24n, 22n + 1, 2n + 1, 2n ? 1} Based on CRT 1 Circuits, Systems, and Signal Processing 40:5773–5786, (2021). [2] R.K. Jaiswal, R. Kumar, R.A. Mishra, Area efficient memoryless reverse converter for new four moduli set {2n-1, 2n ? 1, 2n + 1, 22n+1?1}. J. Circuits Syst. Comput. 27, 1–13 (2018) [3] Amani Goniemat, Andraws Swidan, A High-Speed Residue-to-Binary Converter for Three-Moduli Set, IJCSI International Journal of Computer Science Issues, Vol. 10, Issue 4, No 1, July. (2013). [4] M.R. Noorimehr, M. Hosseinzadeh, R. Farshidi, High speed residue to binary converter for the new four-moduli set {22n, 2n + 1, 2n/2 + 1, 2n/2?1}. Arab. J. Sci. Eng. 39, 2887–2893 (2014) [5] Mohammad Reza Taheri, Nasim Shafiee, Mohammad Esmaeildoust, Zhale Amirjamshidi, Reza Sabbaghi-nadooshan, Keivan Navi, A High-Speed Residue-to-Binary Converter for Balanced 4-Moduli Set. Journal of Computing and Security Volume 2, Number 1 (pp. 43–54), January (2015). [6] A. Hiasat, A residue-to-binary converter with an adjustable structure for an extended RNS three moduli set. J. Circuits Syst. Comput. 28, 1950126 (2018). [7] Sheba Diamond Tabaha, Mridupawan Sonowalb , Prabir Sahaa,b, On the design of efficient Redidue to Binary Converters, International Conference on Computational Intelligence and Data Science (ICCIDS).( 2018). [8] Azadeh Alsadat Emrani Zarandi, Amir Sabbagh Molahosseini, Mehdi Hosseinzadeh, Saeid Sorouri, Samuel Antão, and Leonel Sousa Reverse Converter Design via Parallel-Prefix Adders: Novel Components, Methodology, and Implementations, IEEE TRANSACTIONS ON VERY LARGE-SCALE INTEGRATION (VLSI) SYSTEMS. (2015) [9] K.A. Gbolagade, R. Chaves, L. Sousa, S.D. Cotofana,An Improved RNS Reverse Converter for the Moduli Set , 978-1-4244-5309-2/10/$26.00 ©2010 IEEE.(2010) [10] **G.C. Cardarilli, M. Re, R. Lojacono, EFFICIENT MODULO EXTRACTION FOR CRT BASED RESIDUE TO BINARY CONVERTER, 1997 IEEE International Symposium on Circuits and Systems, - June 9-12,1997, Wong Kong. [11] S. Andraros and H. Ahmad, “A new efficient memoryless residue to binary converter,” IEEE Trans. Circuits Syst., vol. CAS-35, pp. 1441–1444, Nov. 1988. [12] Stanislaw J. Piestrak, A High-speed Realization of a Residue to Binary Number System Converter, IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-11: ANALOG AND DIGITAL SIGNAL PROCESSING, VOL. 42, NO. 10, OCTOBER 1995. [13] M. Bhardwaj, A. B. Premkumar, and T. Srikanthan, Breaking the -Bit Carry PropagationBarrier in Residue to Binary Conversion for the Modula Set, IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: FUNDAMENTAL THEORY AND APPLICATIONS, VOL. 45, NO. 9, SEPTEMBER 1998. [14] . A. Bayoumi, G. A. Jullien, and W. C. Miller, “A VLSI implementation of residue adders,” IEEE Trans. Circuits Syst., vol. 34, pp. 284–288, 1987. [15] K. M. Elleithy and M. A. Bayoumi, “A (1) algorithm for modulo addition,” IEEE Trans. Circuits Syst., vol. 37, pp. 628–631, May 1990. [16] A. Hiasat, A residue-To-binary converter for the extended four-moduli set {2n – 1, 2n + 1, 22n+1, 22n+p}. IEEE Trans. Very Large-Scale Integration. Syst. 25, 2188–2192 (2017)

Copyright

Copyright © 2023 Priyank Tomar, Aditi Kashyap, Rishabh Anand, Ritesh Kumar Jaiswal. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.