Introduction to Reed Solomon Codes: Henry Minsky, Universal Access Inc.hqm@ua.com[For details see Cain, Clark, "Error-Correction Coding For DigitalCommunications", pp. 205.] The Reed-Solomon Code is an algebraic codebelonging to the class of BCH (Bose-Chaudry-Hocquehen) multiple burstcorrecting cyclic codes. The Reed Solomon code operates on bytes offixed length.Given m parity bytes, a Reed-Solomon code can correct up to m byteerrors in known positions (erasures), or detect and correct up to m/2byte errors in unknown positions.This is an implementation of a Reed-Solomon code with 8 bit bytes, anda configurable number of parity bytes.  The maximum sequence length(codeword) that can be generated is 255 bytes, including parity bytes.In practice, shorter sequences are used. ENCODING: The basic principle of encoding is to find the remainder ofthe message divided by a generator polynomial G(x). The encoder worksby simulating a Linear Feedback Shift Register with degree equal toG(x), and feedback taps with the coefficents of the generatingpolynomial of the code.The rs.c file contains an algorithm to generate the encoder polynomialfor any number of bytes of parity, configurable as the NPAR constantin the file ecc.h.For this RS code, G(x) = (x-a^1)(x-a^2)(x-a^3)(x-a^4)...(x-a^NPAR)where 'a' is a primitive element of the Galois Field GF(256) (== 2).DECODINGThe decoder generates four syndrome bytes, which will be all zero ifthe message has no errors. If there are errors, the location and valueof the errors can be determined in a number of ways.Computing the syndromes is easily done as a sum of products, see pp.179 [Rhee 89].Fundamentally, the syndome bytes form four simultaneous equationswhich can be solved to find the error locations. Once error locationsare known, the syndrome bytes can be used to find the value of theerrors, and they can thus be corrected.A simplified solution for locating and correcting single errors isgiven in Cain and Clark, Ch. 5.The more general error-location algorithm is the Berlekamp-Masseyalgorithm, which will locate up to four errors, by iteratively solvingfor the error-locator polynomial. The Modified Berlekamp Masseyalgorithm takes as initial conditions any known suspicious bytes(erasure flags) which you may have (such as might be flagged bya laser demodulator, or deduced from a failure in a cross-interleavedblock code row or column).Once the location of errors is known, error correction is done usingthe error-evaluator polynomial.APPLICATION IDEASAs an example application, this library could be used to implement theCompact Disc standard of 24 data bytes and 4 parity bytes. A RS codewith 24 data bytes and 4 parity bytes is referred to as a (28,24) RScode.  A (n, k) RS code is said to have efficiency k/n. This first(28,24) coding is called the C2 or level 2 encoding, because in adoubly encoded scheme, the codewords are decoded at the seconddecoding step.In following the approach used by Compact Disc digital audio, the 28byte C2 codewords are four way interleaved and then the interleaveddata is encoded again with a (32,28) RS code. The is the C1 encodingstage. This produces what is known as a "product code", and hasexcellent error correction capability due to the imposition oftwo-dimensional structure on the parity checks. The interleave helpsto insure against the case that a multibyte burst error wipes out morethan two bytes in each codeword. The cross-correction capability ofthe product code can provide backup if in fact there are more than 2uncorrectable errors in a block.