Redundant Residue Number Systems

You can uniquely represent a large number by its remainders when divided by smaller numbers, provided the smaller numbers have no factors in common, and carry out arithmetic in this representation. Such a representation is called a Residue Number System (RNS).

In the 1960's people realized RNSs could be useful in computer arithmetic. The original papers are now hard to find, but you can find a summary of some of their ideas here. We will give examples working in a particular RNS below.

When you work with remainders by more numbers than necessary, you have a Redundant Residue Number System (RRNS) that provides error detection and correction. We will also demonstrate this with an example.

To be concrete, we'll use the remainders by 199, 233, 194, and 239 to represent numbers, following the work of C. W. Hastings and R. W. Watson referenced in the link cited above.

Let M = 199*233*194*239. Any non-negative integer less than M can be specified by its remainders mod 199, 233, 194, and 239.

The following Python code generates a random number less than M, represents it by its remainders, and then recovers the original number from the remainders using the Chinese Remainder Theorem.

 from random import randrange from sympy import prod from sympy.ntheory.modular import crt moduli = [199, 233, 194, 239] M = prod(moduli) x = randrange(M) remainders = [x % m for m in moduli] # See footnote [1] y = crt(moduli, remainders, symmetric=False)[0] print(x) print(remainders) print(y)

This printed

 1119075671 [166, 204, 57, 235] 1119075671

You can add, subtract, and multiply numbers by carrying out the corresponding operations on their remainders. There are three advantages to this.

First, you can work with smaller numbers. In our example, all the moduli are 8-bit numbers; we can carry out arithmetic on 32-bit numbers [2] by only working directly with 8-bit numbers. We could use the same idea to represent extremely large numbers by their remainders via 64-bit integers.

Second, we can do our calculations in parallel, working with each of our remainders at the same time.

Third, there are no carries. There's no need to keep track of whether component calculations overflow.

The following code shows how we can add two numbers via their remainders.

 a = randrange(M//2) b = randrange(M//2) arem = [a % m for m in moduli] brem = [b % m for m in moduli] crem = [z[0] + z[1] for z in zip(arem, brem)] c = crt(moduli, crem, symmetric=False)[0] print(a + b) print(c)

When I ran this code, it printed 832537447 twice.

Now we get to the redundant part. Suppose we add more numbers to our list of moduli, larger than the previous numbers and relatively prime to all of them and to each other. Now working modulo this larger list of numbers, we have more information than we need. If the results we get from using various subsets of the list of moduli are inconsistent, we've detected an error. And with enough extra information, we can correct the error.

Watson and Hastings added 251 and 509 in their example, and so we'll do the same.

As before, we will generate a couple random numbers and represent them via their remainders, though now by a longer list of remainders. We will deliberately corrupt one of the component sums and then compute their sum using different choices of four moduli from the set of six.

 xmoduli = [199, 233, 194, 239, 251, 509] a = randrange(M//2) b = randrange(M//2) aremx = [a % m for m in xmoduli] bremx = [b % m for m in xmoduli] cremx = [z[0] + z[1] for z in zip(aremx, bremx)] cremx[1] += 13 c0 = crt(xmoduli[:4], cremx[:4], symmetric=False)[0] c1 = crt(xmoduli[2:], cremx[2:], symmetric=False)[0] c2 = crt(xmoduli[:2] + xmoduli[4:], cremx[:2] + cremx[4:], symmetric=False)[0] print(c0, c1, c2)

This will return three different answers, so we know that there has been an error. When I ran it I got 70315884, 819846513, and 890162397. If you run the code yourself you'll get different answers since you'll generate different random numbers.

Now how do we correct the error? Suppose we know there has only been one error (or more realistically, we are willing to assume that the probability of two errors is tolerably small). Then one of the results above must be correct: the first sum excludes the last two moduli, the second excludes the first two, and the last excludes the middle two. One of them must exclude the error.

The first calculation based on a different subset of moduli that gives one of the results above is correct. The code

 c3 = crt(xmoduli[:1]+xmoduli[2:5], cremx[:1] + cremx[2:5], symmetric=False)[0] print(c3)

produced 890162397, matching the third sum above, so we know that eliminating the second modulus gives the correct answer. We've found the correct answer, and we've discovered which component was corrupted.

***

[1] A couple things about the call to crt require explanation. We set symmetric to False in order to get a positive return value. Otherwise we might get a value that is correct mod M but negative. Also, crt returns not just the solution we're after but a pair consisting of the solution and the product of the moduli. We take the first element of the pair with [0] to get the part we're interested in.

[2] Not all 32-bit numbers. with any numbers less than M, and M is between 2³¹ and 2³².

The post Redundant Residue Number Systems first appeared on John D. Cook.