Home > cryptocurrencies > Residual Number System

Residual Number System


Fig.2. Mixed Radix conversion for a four moduli set (a) algorithm and (b) a numerical example.

Note that d0 is given residue r1. We next compute d1 by subtracting r1 from all other residues ri mod mi and divide the result by m1. Since we have subtracted the residue corresponding to m1 from X, evidently the remainder (X-r1) is divisible exactly by m1. This is the basic principle of MRC. The division is performed by multiplying the residues of all other channels with the multiplicative inverse The residues at this stage correspond to . We next subtract the residue corresponding to modulus m2 in the new set of residues and continue in the same way to obtain the other Mixed Radix digits. This process continues till the last residue channel is reached. An example of four moduli RNS is shown in Fig. 2 (a) together with a numerical example in Fig. 2 (b) . After Mixed Radix digits are found, we can compute the binary number following (2). This involves big number multiplications but the advantage is that no cumbersome modulo M reduction is needed. we can represent all positive numbers between 0 to 104. Alternatively, we can represent numbers between -52 to +52. The positive numbers are between 0 and 52. Negative numbers are between 53 and 104. For example, we represent -3 as 105-3 = 102.

Its residues are complements of residues of 3 with respect to the moduli:

There are several other techniques for RNS to nary conversion introduced more recently such as New Chinese Remainder Theorem., Mixed-Radix CRT, core function etc [12][13][14] each having its own advantages and disadvantages regarding area and time needed in hardware implementation.

By looking at the residues, we cannot find the sign of the corresponding number. Hence, after decoding, we need to compare with 52 to know whether the number is positive or negative. For some special moduli sets, however, some simpler methods have been recently presented.

5. Scaling and base extension

It is interesting to note that scaling by one modulus or product of two or more moduli is possible using MRC easily. In the example of Fig.2 (b), the residues corresponding to scaling by 3 are available in first step as in the reduced RNS {5, 7, 11}. In the second step, we have the result of scaling by 15 as in the reduced RNS {7, 11} and in the last step we have corresponding to scaling by 105 as d4 in the reduced RNS {11}. Note, however, that these results do not give residues corresponding to the “scaling” moduli (moduli to the left of the scaled result). We need to have these residues also for the complete answer to be available in RNS. This needs a step known as base extension. This needs application of Mixed Radix Conversion in the reverse order of moduli.
Scaling by a power of 2 also is possible as is needed in some DSP applications. Scaling by arbitrary number also is possible with some difficulty.

6. Sign detection and comparison

Sign detection is possible after performing reverse conversion using CRT or MRC. For a given RNS e.g. {3, 5, 7}, we can represent all positive numbers between 0 to 104. Alternatively, we can represent numbers between -52 to +52. The positive numbers are between 0 and 52. Negative numbers are between 53 and 104. For example, we represent -3 as 105-3 = 102. Its residues are complements of residues of 3 with respect to the moduli:3 = (0, 3, 3) and -3 = (3-0, 5-3, 7-3) = (0, 2, 4).

By looking at the residues, we cannot find the sign of the corresponding number. Hence, after decoding, we need to compare with 52 to know whether the number is positive or negative. For some special moduli sets, however, some simpler methods have been recently presented.

Comparison also can be done after reverse conversion using CRT or MRC. However in MRC case, the comparison can be done using Mixed radix digits di of given numbers A and B without needing full conversion using (2). We can start comparison with highest Mixed Radix digit dn-1 and if they are equal , then we compare the next Mixed radix digit dn-2. Thus n sequential steps will be needed in the worst case in case of a n-moduli RNS.

7. Abundance of moduli sets

In the past fifteen years numerous moduli sets have been introduced which enable fast reverse conversion and forward conversion and fast multiplication operations without using Read Only Memory (ROM) based Lookup tables (LUTs). Some moduli sets are for example {2n-1, 2n, 2n+1}, {2n-1,2n, 2n-1-1}, {2n-1, 2n, 2n+1-1},{22n-1, 2n, 22n+1}, {2n-1, 2n, 2n+1, 2n+1 -1}, {2n-1, 2n, 2n+1, 2n+1 +1}, {2n-1, 2n, 2n+1, 2n-1-1}, {2n-1, 2n, 2n+1, 2n-1 -1}, {2n-1, 2n, 2n+1, 22n -1} etc.

1 2 3 4 5

Leave a Comment:

Your email address will not be published. Required fields are marked *