KR-20260063355-A - Residue Number System with Complex-Number Moduli

Abstract

The present invention relates to a residual number system, and more specifically, to a residual number system using a complex number modulus that can maintain a speed balance between modulo operation channels while preventing an increase in the complexity of the inverse transform by using a complex number modulus when adding a modulus to expand the dynamic range (DR).

Inventors

• 이정아
• 자베리푸가셈

Assignees

• 조선대학교산학협력단

Dates

Publication Date

20260507

Application Date

20241030

Claims (4)

1. A residual number system characterized by using a modulo (2 q ± j) adder that performs q-bit operations by separating into complex modulo (2 q - √- 1) and (2 q + √- 1) instead of using a modulo adder for 2 q -bit operations when adding modulo (2 2 q + 1) to extend the dynamic range (DR) in modulo operations of a residual number system where the modulo set τ is {2 q - 1, 2, 2 q + 1}.
2. In Article 1, The module to be added A residual number system characterized by using a modulo adder that performs q-bit operations by separating into 2 p complex modulos, rather than using a modulo adder for 2 p q-bit operations.
3. In Article 1, A remainder number system characterized by the above modulo (2 q ± j) adder calculating a sum S by adding operands X and Y as in Equation 1 below, wherein X is expressed as in Equation 2 below and Y is expressed as in Equation 3 below, and finally S is expressed as in Equation 4 below by configuring the logic gates. [Equation 1] [Equation 2] [Equation 3] [Equation 4] Here, X I is the upper bits of X, x 2q - 1 , ..., x q bits; X R is the remaining lower bits, x q - 1 , ..., x 0 bits; x 2q is the most significant bit of X; Y I is the upper bits of Y, y 2q - 1 , ..., y q bits; Y R is the remaining lower bits, y q - 1 , ..., y 0 bits; b y is the borrow value in modulo operation; c y is the carry value in modulo operation; b s is the value calculated by Equation 5 below; and c s is the value calculated by Equation 6 below. [Equation 5] [Equation 6]
4. In Paragraph 3, The above modulo (2 q ± j) adder: is, A q-bit adder for calculating SR that takes X R , Y R , b y , x 2q as input and calculates SR from the sum S; A q-bit adder for calculating SI that takes X I , Y I , c y , x 2q as input and calculates SI among the sum S; A first AND gate that performs an AND operation between b y and x 2q ; A first OR gate that outputs a b s value by performing an OR operation between the output of the first AND gate and the most significant bit value of s I ; A second AND gate that performs an AND operation between c y and x 2q ; and A residual number system characterized by including a second OR gate that outputs a c s value by performing an OR operation between the output of the second AND gate and the most significant bit value of the S r .

Description

Residue Number System with Complex-Number Moduli The present invention relates to a residual number system, and more specifically, to a residual number system using a complex number modulus that can maintain a speed balance between modulo operation channels while preventing an increase in the complexity of the inverse transform by using a complex number modulus when adding a modulus to expand the dynamic range (DR). The modular set τ={2 q - 1, 2 q , 2 q + 1} is known as the most frequently used modular set in applications of residual number systems (RNS). The characteristic of this classic popular set of moduli is that the rate balance between the residual channels operating the three modulus operations is maintained, and only the adder, multiplier, and forward converter are used for the inverse transformation. In machine learning hardware accelerators, the residual number system requires the detection and comparison of codes, and its performance largely depends on the efficiency of the inverse converter. The aforementioned inverse transformer of the modular set τ can be simply implemented through a 2q-bit carry-save adder (CSA) and a modulo ( 2q -1) adder. In addition, the modulo ( 2q -1) adder is realized as the single-zero ripple-carry modulo ( 2q -1) adder shown in FIG. 1 and is identical to a one's complement adder that includes an additional AND gate in each full adder (FA). Meanwhile, it is actually required to realize a wider dynamic range (DR) without increasing the bit width q, and this is achieved by including an additional modulus in the set of moduli τ, but in this process, the two main advantages of τ, speed balance and efficient inverse converter, may be compromised. To address this, there is a method to extend the modularity to maintain the form of the expression for the dynamic range of τ, 2q (2 2q - 1), which is the modular set τ p This is possible through = τ∪{2 2iq + 1(1≤i≤p)}, and in this case, the dynamic range is It becomes. For example, the modular set τ 1 The dynamic range of = τ∪{2 2q + 1} is 2 q (2 4q - 1), and the modular set τ 2 In the case of = τ∪{2 2q + 1,2 4q + 1}, it becomes 2 q (2 8q - 1). Therefore, τ p is preserved in an extended form of 2 p while maintaining the simplicity and speed of the inverse converter. However, this method has the problem of hindering speed balance between residual water channels. In summary, when increasing q to increase the dynamic range of the modular set τ={2 q - 1, 2 q , 2 q + 1}, there is a problem of slowdown due to a longer carry chain, and when δ>1, extending τ with a q-bit additional modular of the general form 2 q ± δ results in slowdown due to added complexity compared to when δ=1 and increases the complexity of the inverse transform. That is, the aforementioned form Adding a modularity of (1≤i≤p) does not cause additional complexity as δ remains at 1, but there is a problem where the carry chain becomes longer and speed is reduced as q increases. FIG. 1 shows a conventional modulo ( 2q -1) adder, a carry-save adder (CSA), and a modulo ( 2q -1) adder, FIG. 2 is a drawing showing a modular adder of a residual number system according to an embodiment of the present invention, FIG. 3 is a graph comparing the delay speeds of a modulo 2 2q + 1 adder and a modulo 2 q ± j adder of the present invention, Figure 4 is a graph comparing the power consumption of a modulo 2 2q + 1 adder and a modulo 2 q ± j adder of the present invention. The terms used in this invention have been selected to be as widely used as possible; however, in specific cases, terms have been arbitrarily selected by the applicant. In such cases, the meaning should be understood by considering the meaning described or used in the detailed description of the invention, rather than merely the name of the term. Hereinafter, the technical configuration of the present invention will be described in detail with reference to preferred embodiments illustrated in the attached drawings. However, the present invention is not limited to the embodiments described herein and may be embodied in other forms. Throughout the specification, the same reference numerals indicate the same components. A residual number system according to one embodiment of the present invention is a system in which, when adding modulo (2 2q +1) to expand the dynamic range (DR) in modulo operation where the modulo set τ is {2 q -1, 2, 2 q +1}, there is no increase in complexity during inverse transformation and the speed balance between modulo operation channels can be maintained. In addition, when the above residual number system wants to add modulo (2 2q + 1), it does not use a modulo adder for 2q-bit operations, but instead uses a modulo (2 q ± j) adder that performs q-bit operations by separating into complex modulo (2 q - √-1) and (2 q + √-1). In other words, since q is maintained at '1' just like other modulos, an adder with the same carry chain can be used for each modulo operation, preventing an imbalance in