Reed-Solomon Data Link Error Detection / Correction Method

Reed-Solomon block codes are popular in communications and data-storage applications. Like fire codes, Reed-Solomon-code implementations append symbols to the end of a transmission to locate and correct errors during decoding. Reed-Solomon-code systems' effectiveness at high data rates results from operations taking place at the code-symbol rate or at a fixed number of times per code word. Either way, the number of operations is much smaller than the number of bits. Chips that implement these types of high-speed real-time correctors are commercially available, as are DSP-software options.

Each RS symbol is actually a group of M bits. Just one bit error anywhere in a given symbol spoils the whole symbol. That's why RS codes are often called "burst-error-correcting" codes; if you're going to have bit errors, you'd like to concentrate them into as few RS symbols as possible. Many RS codes in use are "shortened", i.e., the block size, or number of symbols used: N, is smaller than the symbol size, or maximum number of symbols: 2^M-1 would indicate.

Since RS can be done on any message length and can add any number of extra check symbols, a particular RS code will be expressed as RS (N,N-R) code where N is the total number of symbols per codeword; R is the number of check symbols per codeword and; therefore, N-R is the number of actual information symbols per codeword. The typical RS decoder can correct up to (N-R)/2 symbol errors per block Note that "errors" and "erasures" are not the same things.

For example, digital video broadcast (DVB) specification uses a RS (204,188) code, utilizing sixteen check symbols per 188, 8-bit, information symbols for a total codeword length of 204 symbols and can correct eight symbols. This means that a burst error of 57 to 64 consecutive bits can be corrected.

RS encoding then consists of the generation of these check symbols from the original data. The process is based upon finite field (also known as Galois field or GF) arithmetic. Finite fields are so named because all arithmetic is closed over the field (the result of any operation is still an element of the field). In other words, GF addition bears no resibalence to normal addition; adding two large GF values will probably get you a smaller value. Its sort of like always taking the modulo of the result (or throwing away the carry) so that the values never exceed the space available to store them. The field elements are all values from 0 to 2^M-1. Therefore, for a bit width of 3, the field will contain the values (0,1,2,3,4,5,6,7), though not necessarily in that order.

The field polynomial, which is used to determine the order of the elements in the finite field, is generally determined by specification (the example DVB specification mentioned uses eight bit symbols {m=8} and a field polynomial of 285 per specification). Valid field polynomials are a function of the bit width to be operated on. For example, the valid field polynomials for m=3 are 11 and 13.

The generator polynomial starting root is generally determined by specification (DVB uses a generator polynomial starting at root zero), although any value in the finite field can be used.

Generally, a Reed-Solomon corrector provides a number of symbol corrections, say T, in an N-symbol code word. T is independent of the location of the errors inside the code word. When you use this method with complex interleaving, this approach can easily correct large error bursts. Further algorithm refinements allow even more correction capability if you know the error location by some other means. These "soft-error" indicators can come, for example, from up-stream decoding violations. It is unable to both locate and correct errors in a block that has more than T symbol errors.

See also

• Phil Karn wrote a good general purpose Reed-Solomon  implementation of finite (Galois) field arithmetic and the Berlekamp-Masssey (BM) algorithm, as explained in Lin and Costello's book Error Control Coding. (Simon Rockliff, 1991)
• Paul Flaherty (paulf at stanford.edu) developed GPL'd librarys for RS, GF and an ECC sample program for (255, 248) code over GF(256) and corrects 3 errors and detects 4. A 2.74% increase in size.
• http://people.qualcomm.com/karn/code/fec/ (cached 20000506 HTML) Phil Karn developed a Pentium optimized version of the Reed-Solomon errors-and-erasures decoder by Morelos-Zaragoza and Thirumoorthy, 1995 for (255,223) code over GF(256) to correct 3 errors. A 12.5% increase in size.
• IBM came up with a way to do RS in parallel
• Kodak Berkeley Research (KBR) are working on RS FEC
• Aztec Barcode Symbology is public-domain and uses RS FEC
• http://www.csdmag.com/main/1999/06/9906building.htm Building Blocks: The long climb up the error correction ladder leads to one of today’s best data tricks — Reed-Solomon coding.
• http://www.csdmag.com/main/1999/05/9905building.htm Building Blocks: Reed-Solomon from the Ground Up.
• http://www.csdmag.com/main/9812/9812feat3.htm Reed-Solomon Codec Design in Programmable Logic
• http://www.csdmag.com/main/col9703.htm State-of-the-art performance in today's digital communication systems can be achieved if error correction is employed.

Books

• Lin & Costello, Error Control Coding
• Lee & Messerschmitt, Digital Communication

See also:

• http://the-art-of-ecc.com http://the-art-of-ecc.com+
• http://www.ee.umn.edu/users/jchen/ecc.html

  .