Residue Arithmetic Operations

In Residue Number System, Addition, Subtraction and Multiplication are inherently carry-free, which means that each digit of the result is a function of only one digit from each operand and independent of the others [2]. This is the most attractive feature of RNS that enables us to design highly parallel structure for computation in order to gain high speed for DSP applications.

Addition and Subtraction: For a Residue Number System consisting of moduli {m1, m2, ..., mN}, if the two integer number x and y have the residue representations {x1, x2, ..., xN} and {y1, y2, ..., yN} respectively then the residue representation of will be as follows:

From the above expression of modular addition and subtraction the fundamental benefit of using RNS is apparent- each digit of the resultant is the function of only one digit from each operand and thus it has no intermodular carries. But it has some constraint. From the expression we see that the result is in the form of modulo M, which means the result should not exceed the dynamic range (i.e [0, M-1]) otherwise ambiguity would result because and has the same result. So to avoid this ambiguity M should be chosen large enough to guarantee results within the dynamic range and to avoid overflow.

 

Example 2.1:

            Let a Residue Number System has 3 moduli- 3, 5 and 7.

            So in this system M = 3.5.7 = 105. Also, in this system an integer number x = 12 has the residue representation {0, 2, 5} and y = 4 has the residue representation {1, 4, 4}. Now, since 124 within the dynamic range of the system (i.e. [0, 105-1] or [0, 104]), this computation can be done in this system without any ambiguity, as follows:

so,       

{1, 1, 2}

and,     

{2, 3, 1}

            Click here, for a Java Applet for easy demonstration.

 

Multiplication: For a Residue Number System consisting of moduli {m1, m2, ..., mN}, if the two integer number x and y have the residue representations {x1, x2, ..., xN} and {y1, y2, ..., yN} respectively then the residue representation of will be as follows:

The form is just like Addition or Subtraction. Like Residue Addition or Subtraction, Residue Multiplication is also carry-free because of the elimination of the need of partial products. The results must also be an element of the ring modulo M (i.e [0, M-1]). For any result greater than the dynamic range will cause an ambiguity as in the case of Addition.

 

Example 2.2:

            For the Residue Number System of Example 2.1, if we want to multiply the two integers x = 12 and y = 4, the result would be 48. Now, since 124 within the dynamic range of the system (i.e. [0, 104]), this computation can be done in this system without any ambiguity, as follows:

so,       

{0, 3, 6}

            Click here, for a Java Applet for easy demonstration.

 

Division: Unlike Addition, Subtraction and Multiplication, Division operation in Residue Arithmetic is rather slow and demands some conditions to be met. These conditions are:

• The division must results an integer number without any residues.
• If y divides x then, y has to be relatively prime to the moduli {m1, m2, ..., mN} used in the system.

These are known as “Division remainder zero” conditions. If these two conditions are met then the residue representation of will be:

Here, {x1, x2, ..., xN} is the residue representation of x and {,, ...,} is the multiplicative inverse of y over modulus {m1, m2, ..., mN}. Division is not very popular in modular arithmetic because of its restriction. Most of the discussions related to modular arithmetic are concentrated within the three operations- Addition, Subtraction and Multiplication.

 

Example 2.3:

            For the same Residue Number System of the previous two examples, if we want to divide integer x = 12 by y = 4, the result would be 3 without any residue and also the divisor- 4 is relatively prime to the three moduli- 3, 5 and 7 used in the system. So the division operation- can be carried out as follows:

            The multiplicative inverse of divisor 4 over the ring modulo 3, 5 and 7 can be found as follows:

4 mod 3 = 1 and 1.1 mod 3 = 1 so, = 1

4 mod 5 = 4 and 4.4 mod 5 = 1 so, = 4

4 mod 7 = 4 and 4.2 mod 7 = 1 so, = 2

so,       

{0, 3, 3}

            Now we can verify that {0,3,3} is the residue representation of the result of division operation 12/4 = 3, by CRT as follows:

            For the RNS system under consideration has the moduli- 3, 5 and 7. So, M = 3.5.7 = 105. And the values of A1, A2 and A3, as calculated in Example 1.5 for this system are 35, 21 and 15 respectively. The value of the multiplicative inverses of A1, A2, A3 are also calculated in Example 1.5 to be T1 = 2, T2 = 1 and T3 = 1.

            So, Using CRT we get

                                                                  x/y = (35.2.0 + 21.1.3 + 15.1.3) mod 105

                                                                        = 108 mod 105

                                                                        = 3