EE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

This page introduces the Reed Solomon (RS) Codes and the extended Galois fields upon which these powerful and popular codes are based.

Error control codewords with predictable properties can be generated using a primitive prime polynomial P(x) to build a suitable generator polynomial G(x). Galois fields form the basis for BCH codes capable of multi-bit error correction. Reed-Solomon (RS) codes are a subset of BCH codes, based on extended Galois fields GF(2^m). The symbol-based RS codes boast inherent burst-error correction capability.

The terms {a^N} serve to describe this GF(8). Equivalent 3-bit values are shown in decimal.

From this table, the polynomial P(a) = a³ + a + 1 = 3 + 2 + 1 = 0, since a is specifically defined to be a root of P(x)

A Polynomial in GF(8)

A polynomial P(x) can be defined using the above values in a^N as coefficients.

For example, this polynomial M(x) has 3-bit coefficients defined in terms of a^N:

Arithmetic in this number set proceeds with reference to the table of values defining the a^N.

Generator Polynomial G(x) Formulation

The general form of the RS code generator polynomial G(x) is:

G(x) = (x - a¹) (x - a²) (x - a³) (x - a⁴) ... (x - a^2t)

Where t is the number of multi-bit symbols that can be corrected with the resulting code and 2t is the number of parity symbols. The abilty to correct symbol errors rather than individual bit errors is key to the power of the RS codes. This is somewhat like fixing bad digits in a credit card number rather than individual bit errors. For GF(8), the resulting code is (n,k) = (7, 7-2t), where the n and k and t all refer to a number of 3-bit symbols. The overall codeword size is 3 × 7 = 21 bits. In the present examples using GF(8) in which addition and subtraction are equivalent operations, the minus signs may be replaced with plus signs.

Generator Polynomial G(x) for RS Code based on GF(8)

The maximum codeword length with 3-bit symbols is 2³-1 = 7 symbols as shown here.

Let t=1, then this G(x) defines a (n,k) = (7,5) RS code able to correct one bad 3-bit symbol.

G(x) = (x + a¹) (x + a²)

G(x) = (x + 2) (x + 4)

G(x) = 1 x² + 6 x + 3

Division by this degree 3 polynomial leaves a two symbol remainder.

Let t=2, then this G(x) defines a (n,k) = (7,3) RS code able to correct two bad 3-bit symbols.

G(x) = (x + a¹) (x + a²) (x + a³) (x + a⁴)

G(x) = (x + 2) (x + 4) (x + 3) (x + 6)

G(x) = (1 x² + 6 x + 3 ) (1 x² + 5 x + 1 )

G(x) = 1 x⁴ + 3 x³ + 1 x² + 2 x + 3

Division by this degree 5 polynomial leaves a four symbol remainder.

Example systematic (7,5) codeword with t=1 using G(x) = 1 x² + 6 x + 3

Consider an input message F(x) having five symbols. It is necessary to append two parity symbols to make the complete RS codeword having seven symbols.

F(x) = 1 x⁴ + 5 x³ + 3 x² + 5 x + 3

Multiply F(x) by x² to append two zeros, then divide by G(x) .

F(x) x² = 1 x⁶ + 5 x⁵ + 3 x⁴ + 5 x³ + 3 x² + 0 x + 0

(F(x) x²) / G(x) = (1 3 1 6 2), remainder (6 6) (Check the math)

The remainder (6 6) is substituted for the two zeros to give the Reed Solomon codeword:

C(x) = 1 x⁶ + 5 x⁵ + 3 x⁴ + 5 x³ + 3 x² + 6 x + 6

This systematic codeword is an exact multiple of G(x); (Check the math)

The seven 3-bit symbols in the entire codeword comprise 21 bits. Any error in any one symbol can be corrected, as shown below.

Error Correction on (7,5) RS codeword with t=1 using G(x) = 1 x² + 6 x + 3

Consider the single-symbol error E(x):

E(x) = 6 x³

And the valid codeword C(x) from above:

C(x) = 1 x⁶ + 5 x⁵ + 3 x⁴ + 5 x³ + 3 x² + 6 x + 6

Adding the error to the codeword gives M(x) = C(x) + E(x):

M(x) = 1 x⁶ + 5 x⁵ + 3 x⁴ + 3 x³ + 3 x² + 6 x + 6

The errored symbol is shown highlighted.

Correcting the Error...

Dividing the errored codeword M(x) by G(x) gives a non-zero remainder, signalling the presence of an error.

M(x) / G(x) = (1 5 3 3 3 6 6) / G(x), giving remainder (6 6) (Check the math)

Observe that dividing the error pattern E(x) by G(x) gives the same non-zero remainder.

E(x) / G(x) = (0 0 0 6 0 0 0) / G(x), giving remainder (6 6) (Check the math)

The remainder (6 6) corresponds to the specific error pattern E(x) = 6 x³ and matches it to the errored word M(x). This single-symbol error in M(x) is easily corrected since the original C(x) = M(x) + E(x). Any single bad symbol could be corrected in this way; because each symbol is 3-bits, the RS codes inherently provide substantial burst-error correction.

Error Lookup Table, given a remainder (x y)

The remainder corresponding to E(x) = 6 x³ is shown highlighted. No other remainder matches this value.

Select a primitive polynomial P(x)

Model C-206H REED SOLOMON CODE TUTOR P(x) = 1011 : P[x] = x3+x+1 1101 : P[x] = x3+x2+1 10011 : P[x] = x4+x+1 11001 : P[x] = x4+x3+1 100101 : P[x] = x5+x2+1 101001 : P[x] = x5+x3+1 101111 : P[x] = x5+x3+x2+x+1 110111 : P[x] = x5+x4+x2+x+1 111011 : P[x] = x5+x4+x3+x+1 111101 : P[x] = x5+x4+x3+x2+1 1000011 : P[x] = x6+x+1 1011011 : P[x] = x6+x4+x3+x+1 1100001 : P[x] = x6+x5+1 1100111 : P[x] = x6+x5+x2+x+1 1101101 : P[x] = x6+x5+x3+x2+1 1110011 : P[x] = x6+x5+x4+x+1    Include MATLAB example calculations.

Mon May 20 02:39:50 ADT 2013 Last Updated: 03 JAN 2013	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...