3 Introduction to Reed Solomon Codes:
5 Henry Minsky, Universal Access Inc.
8 [For details see Cain, Clark, "Error-Correction Coding For Digital
9 Communications", pp. 205.] The Reed-Solomon Code is an algebraic code
10 belonging to the class of BCH (Bose-Chaudry-Hocquehen) multiple burst
11 correcting cyclic codes. The Reed Solomon code operates on bytes of
14 Given m parity bytes, a Reed-Solomon code can correct up to m byte
15 errors in known positions (erasures), or detect and correct up to m/2
16 byte errors in unknown positions.
18 This is an implementation of a Reed-Solomon code with 8 bit bytes, and
19 a configurable number of parity bytes. The maximum sequence length
20 (codeword) that can be generated is 255 bytes, including parity bytes.
21 In practice, shorter sequences are used.
23 ENCODING: The basic principle of encoding is to find the remainder of
24 the message divided by a generator polynomial G(x). The encoder works
25 by simulating a Linear Feedback Shift Register with degree equal to
26 G(x), and feedback taps with the coefficents of the generating
27 polynomial of the code.
29 The rs.c file contains an algorithm to generate the encoder polynomial
30 for any number of bytes of parity, configurable as the NPAR constant
33 For this RS code, G(x) = (x-a^1)(x-a^2)(x-a^3)(x-a^4)...(x-a^NPAR)
34 where 'a' is a primitive element of the Galois Field GF(256) (== 2).
38 The decoder generates four syndrome bytes, which will be all zero if
39 the message has no errors. If there are errors, the location and value
40 of the errors can be determined in a number of ways.
42 Computing the syndromes is easily done as a sum of products, see pp.
45 Fundamentally, the syndome bytes form four simultaneous equations
46 which can be solved to find the error locations. Once error locations
47 are known, the syndrome bytes can be used to find the value of the
48 errors, and they can thus be corrected.
50 A simplified solution for locating and correcting single errors is
51 given in Cain and Clark, Ch. 5.
53 The more general error-location algorithm is the Berlekamp-Massey
54 algorithm, which will locate up to four errors, by iteratively solving
55 for the error-locator polynomial. The Modified Berlekamp Massey
56 algorithm takes as initial conditions any known suspicious bytes
57 (erasure flags) which you may have (such as might be flagged by
58 a laser demodulator, or deduced from a failure in a cross-interleaved
59 block code row or column).
61 Once the location of errors is known, error correction is done using
62 the error-evaluator polynomial.
66 As an example application, this library could be used to implement the
67 Compact Disc standard of 24 data bytes and 4 parity bytes. A RS code
68 with 24 data bytes and 4 parity bytes is referred to as a (28,24) RS
69 code. A (n, k) RS code is said to have efficiency k/n. This first
70 (28,24) coding is called the C2 or level 2 encoding, because in a
71 doubly encoded scheme, the codewords are decoded at the second
74 In following the approach used by Compact Disc digital audio, the 28
75 byte C2 codewords are four way interleaved and then the interleaved
76 data is encoded again with a (32,28) RS code. The is the C1 encoding
77 stage. This produces what is known as a "product code", and has
78 excellent error correction capability due to the imposition of
79 two-dimensional structure on the parity checks. The interleave helps
80 to insure against the case that a multibyte burst error wipes out more
81 than two bytes in each codeword. The cross-correction capability of
82 the product code can provide backup if in fact there are more than 2
83 uncorrectable errors in a block.