Chapter 2: Power of Reed-Solomon Codes
Idea of Reed-Solomon Codes
Simply speaking, the basic idea of Reed-Solomon codes is multiplying the information word represented in the form of a polynomial D by the prime polynomial G [i] , known to both parties. As a result, the codeword C will be obtained, also represented in the polynomial form.
Decoding is carried out in the inverse manner: If, after dividing the codeword C by the polynomial G , the decoder obtains a remainder, it can report an error. Accordingly , if the codeword can be divided without a remainder, this means that its transmission was completed successfully.
If the power of the polynomial G (also called the generator polynomial) exceeds the power of the codeword by at least two, then the decoder is capable not only of reporting, but also of correcting single errors. If the power of the generator polynomial exceeds that of the codeword by 4, double errors can also be corrected. Briefly speaking, the power of polynomial k is related to the maximum number of recoverable errors t as follows : k = 2*t . Consequently, the codeword must contain two auxiliary symbols per one recoverable error. Meanwhile, maximum number of recognizable errors is equal to t , i.e., one redundant symbol per each recognizable error.
In contrast to Hamming codes, Reed-Solomon codes can correct any reasonable number of errors with quite an acceptable level of redundancy. What helps to achieve this result? In Hamming codes, check bits controlled only data bits to the right of them and ignore all data bits located to the left. Let us return to Table 2.1. The addition of the 8th check bit D has in no way improved the noise immunity of encoding, since the check bit D has nothing to control. In Reed-Solomon codes, check bits expand their influence to all data bits. Therefore, increasing the number of check bits improves the quality of error detection/correction. Thanks to this, Reed-Solomon correcting codes have become so stunningly popular.
Now for the bad news. Normal arithmetic is not suitable for working with Reed-Solomon codes. Encoding assumes computations over polynomials , the coefficients of which must be added, subtracted, multiplied, and divided. These operations must not be accompanied by the rounding up of intermediate results (even division), in order to avoid the introduction of indeterminacy. Both intermediate and final results must not exceed the predefined limits of the bit width. But wait! This is impossible ! Who believes that multiplication doesn t increase the bit width of the result?!
Still, if we call up a little brain power, we can grasp that it is not necessary to multiply the information word by the generator polynomial. It is possible to find a much more elegant solution.
-
Add r trailing zeroes to the source data word D . As a result, we will get a word that has the length of n = m + r and the polynomial X r *D , where m is the length of the data word.
-
Divide the resulting polynomial X r *D by the generator polynomial G and calculate the remainder from the division R , so that X r *D = G*Q + R , where Q is the quotient which we ignore, since, at this stage, only the remainder is of interest.
-
Add the remainder R to the data word D , as a result we will get a code word C , the data bits of which are stored separately from control bits. In fact, the remainder that was obtained as a result of division represents correcting Reed-Solomon codes. The method of encoding, in which data and check symbols are stored separately, is known as systematic coding. Such coding is convenient from the point of view of hardware implementation.
-
Now, mentally scroll steps 1, 2, and 3, trying to detect, at which stage of calculation the bit width has been exceeded. You ll notice that there is no such stage! Every-thing is OK. It only remains to point out that the information word plus correcting codes can be written as T == X r *D + R = GQ .
Decoding of the resulting keyword T is carried out in just the same manner as was described earlier. If, when dividing T (which, in fact, represents the product of G and Q ) by the generator polynomial G , we get a remainder, this means that the word T is corrupted, and, accordingly, if there is no remainder, there was no error.
Now, the question arises as to how are we going to carry out division of polynomials within the framework of standard algebra? In integer arithmetic, division is not defined for all pairs of numbers (for instance, 2 cannot be divided by 3, and 9 cannot be divided by 4, ”without the loss of value, of course). With regard to floating-point division, its precision is catastrophically insufficient for effective use with Reed-Solomon codes. Further, it is somewhat complicated for hardware implementation. If you are working with IBM PC based on a Pentium processor, it is equipped with high-performance math coprocessor. However, consider the situation from the point of view of manufacturers releasing hardware like tape drives, hard disks, CD drives . Are they going to equip these devices with Pentium 4 processors?! Of course not! It is much better to use special arithmetic ”the arithmetic of finite groups called Galois fields. The advantage of this arithmetic is that operations of addition, multiplication, subtraction, and division are defined for all members of the field (except, naturally, for the case of division by zero). The number obtained as a result of any of these operations is guaranteed to be present in the group ! This means that when dividing any integer number A , belonging to the set 0 255, by any integer number B belonging to the same set (naturally, B must not be equal to zero), we will get the number C , belonging to the same set. Consequently, there are no losses of value, and no uncertainty appears.
Thus, correcting Reed-Solomon codes are based on polynomial operations in the Galois fields and require the programmer to master several aspects of higher mathematics in the field of the theory of numbers. Like any other concepts of higher mathematics, Galois fields represent an abstraction that can t be presented in the form of illustration or felt in any other way. When dealing with such an abstraction, it is just necessary to accept it as a set of axioms, without trying to grasp its sense. It is sufficient to know that it works. That s all. Still, there are polynomials of vast powers, which will turn the normal system programmer a little green ( unfortunately , programmers with higher math education are more of an exception than a rule).
Therefore, before rushing into the depths of a pathless mathematical forest of abstractions, let us construct the model of the Reed-Solomon coder/decoder operating according to the rules of normal integer algebra. Naturally, because the bit width must inevitably be extended in this case, it will be rather hard to find a reasonable area of application for such a coder /decoder. However, it works, it is illustrative , and it allows not only the understanding of the working principle of Reed-Solomon codes, but also allows you to feel them intuinively.
Let us base our considerations on the assumption that if g = 2 n + 1 , then for any a belonging to the range of 2 n , the product a*g = c (where c is the codeword) will represent a jumble of bits from both source numbers.
Let us assume that n = 2 , then g = 3 . As can be easily seen, no matter by which number we multiply g ”by 0, by 1, 2, or 3. Either way, the result will be exactly divisible by g only in case if no one of its bits is inverted (or, simply speaking, that there are no single errors).
The remainder from the division is a clear indication of the position in which the error has occurred (provided that it is a single error, because this algorithm is incapable of correcting group errors). To be more precise, if the error occurred in position x , then remainder of division will be equal to k = 2 x . To determine x by a given k value quickly, it is possible to use a trivial table algorithm. Nevertheless, for restoring the corrupted bit, it is not necessary to know its position. It is enough to simply carry out the following operation: R = e ^ k , where e is the mangled codeword, ^ stands for the XOR operation, and R is the recovered codeword.
In general, the working implementation of the coder/decoder might appear as below. This implementation operates on the basis of normal arithmetic (e.g., with unjustified extension of the bit width), and corrects any single errors in a single 8-bit data word (naturally, it is not difficult to modify this program to operate with 16-bit information words). Note that the coder is implemented in a significantly simpler manner than decoder. In a real-world Reed-Solomon coder/decoder capable of correcting group errors, this gap is even more considerable.
| |
/*------------------------------------------------------------------------ * * SIMPLEST REED-SOLOMON CODER/DECODER * ======================================== * * Build 0x001 @ 02.07.2003 ------------------------------------------------------------------------*/ // ATTENTION! This coder/decoder is built on the basis // of normal arithmetic, not on the Galois arithmetic. // As a result, its functional capabilities are very limited. // However, it is very easy and illustrative #include <stdio.h> #define SYM_WIDE 8 // width of the source data word (bits) #define DATAIN 0x69 // input data (on byte) #define ERR_POS 3 // number of corrupted bit // prime polynomial #define MAG (1<< (SYM_WIDE*1) + 1<< (SYM_WIDE*0)) // --------------------------------------------------------------------------------- // determining the error position x given the remainder k // from the division of the codeword by the polynomial // k = 2^x, where "^" - means raising to power // The function accepts k and returns x // --------------------------------------------------------------------------------- int pow_table [9] = {1, 2, 4, 8, 16, 32, 64, 128, 256}; lockup(int x) {int a; for(a=0; a<9; a++) if(pow_table[a]==x)return a; return -1;} main() { int i; int g; int c; int e; int k; fprintf(stderr, "simplest Reed-Solomon encoder/decoder by Kris Kaspersky\n\n"); i = DATAIN; // input data (data word) g = MAG; // prime polynomial printf("i = %08x (DATAIN)\ng = %08x (POLYNOM)\n, i, g); // REED-SOLOMON CODER (very simple, but working) // calculating the codeword intended for transmission c = i * g; printf("c = %08x (CODEWORD) \n", c); // End of CODER // transmission with errors e = c ^ (1<<ERR_POS); printf("e = %08x (RAW RECEIVED DATA+ERR)\n\n", e); /* ^^^^ inverting one bit to imitate the transmission error */ // REED-SOLOMON DECODER // Check for transmission errors // (the simplest Reed-Solomom decoder) if (e % g) { // errors detected, trying to correct printf("RS decoder says: (%x) error detected\n{\n", e % g); k = (e % g); // k = 2^x, where x is the position of erroneous bit printf("\t0 to 1 err position: %x\n", lockup(k)); printf ("\trestored codeword is: %x\n}\n", (e ^= k)); } printf("RECEIVED DATA IS: %x\n", e / g); // END OF DECODER } | |
Now, consider the results. Pay special attention to the fact that the corrupted bit was successfully restored. However, in order to achieve this, it was necessary to add three bits (instead of 2) to the source data word. Note that you take the maximum allowed 8-bit value 0xFF as the input word, then the code word will be equal to 0x1FE00 . Since 2 10 = 10000 , there will be no free positions , and the width must be increased up to 2 11 , while the least significant bits of the code word remain unused. The correct coder must connect them in the manner of a ring.
| |
i = 00000069 (DATAIN) g = 00000200 (POLYNOM) c = 0000d200 (CODEWORD) e = 0000d208 (RAW RECEIVED DATA+ERR) RS decoder says: (8) errors detected { 0 to 1 err position: 3 restored codeword is: d200 } RECEIVED DATA IS: 69 | |
[i] I.e., the polynomial with integer coefficients that cannot be expressed as the product of two lower-degree polynomials with integer coefficients.
EAN: 2147483647
Pages: 60