ECE4253 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 polynomial P(x) to build a suitable generator polynomial G(x). Galois fields form the basis for BCH codes capable of multibit error correction. ReedSolomon (RS) codes are a subset of BCH codes, based on extended Galois fields GF(2^{m}). The symbolbased RS codes boast inherent bursterror correction capability.
The 8 terms {0, a^{0}, a^{1}, a^{2} ... a^{6}} describe the 3bit elements of this GF(8) as shown here in decimal for a = x = (2)
0  a^{0 }  a^{1 }  a^{2 }  a^{3 }  a^{4 }  a^{5 }  a^{6 } 
0  1  2  4  3  6  7  5 
Each term a^{n} is given by x^{n} mod P(x).
While P(x) is primitive in GF(2), this a is one of 3 polynomial roots of P(x) in GF(2^{3}); observe from the table that P(a) = a^{3} + a + 1 = 3 + 2 + 1 = 0
A Polynomial in GF(8)
A GF(2^{3}) polynomial can be defined using the above 3bit values in {a^{n}} as coefficients.
For example, this polynomial M(x) has 3bit coefficients in the range 0 to 7:
M(x)  = a^{3} x^{3} + a^{1} x^{2} + a^{4} x + a^{5} 
= 3 x^{3} + 2 x^{2} + 6 x + 7 , also written as (3 2 6 7)  
= (011) x^{3} + (010) x^{2} + (110) x + (111)  
= the 12bit binary value 011010110111 
Further arithmetic proceeds with reference to the above table defining this GF(8). Multiplication is most easily performed using the terms in a^{n}.
Addition Example:  a^{5} + a^{3} = (111) + (011) = (100) = a^{2} 
Multiplication Example:  a^{5} × a^{3} = a^{(5+3)} = a^{8} = a^{1} 
Addition Example:  4 + 1 = (100) + (001) = (101) = 5 
Multiplication Example:  4 × 1 = a^{2} × a^{0} = a^{(2+0)} = a^{2} = 4 
Generator Polynomial G(x) Formulation
The general form of the RS code generator polynomial G(x) is:
G(x) = (x  a^{1}) (x  a^{2}) (x  a^{3}) (x  a^{4}) ... (x  a^{2t})
Where t is the number of multibit 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, 72t), where the n and k and t all refer to a number of 3bit 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 3bit symbols is 2^{3}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 3bit symbol.
G(x) = (x + a^{1}) (x + a^{2})
G(x) = (x + 2) (x + 4)
G(x) = 1 x^{2} + 6 x + 3
Division by this degree 2 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 3bit symbols.
G(x) = (x + a^{1}) (x + a^{2}) (x + a^{3}) (x + a^{4})
G(x) = (x + 2) (x + 4) (x + 3) (x + 6)
G(x) = (1 x^{2} + 6 x + 3 ) (1 x^{2} + 5 x + 1 )
G(x) = 1 x^{4} + 3 x^{3} + 1 x^{2} + 2 x + 3
Division by this degree 4 polynomial leaves a four symbol remainder.
Example systematic (7,5) codeword with t=1 using G(x) = 1 x^{2} + 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) = 3 x^{4} + 2 x^{3} + 5 x^{2} + 5 x + 1
Multiply F(x) by x^{2} to append two zeros, then divide by G(x) .
F(x) x^{2} = 3 x^{6} + 2 x^{5} + 5 x^{4} + 5 x^{3} + 1 x^{2} + 0 x + 0
(F(x) x^{2}) / G(x) = (3 3 1 6 0), remainder (1 0) (Check the math)
The remainder (1 0) is substituted for the two zeros to give the Reed Solomon codeword:
C(x) = 3 x^{6} + 2 x^{5} + 5 x^{4} + 5 x^{3} + 1 x^{2} + 1 x + 0
This systematic codeword is an exact multiple of G(x); (Check the math)
The seven 3bit 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^{2} + 6 x + 3
Consider the singlesymbol error E(x):
E(x) = 7 x^{6}
And the valid codeword C(x) from above:
C(x) = 3 x^{6} + 2 x^{5} + 5 x^{4} + 5 x^{3} + 1 x^{2} + 1 x + 0
Adding the error to the codeword gives M(x) = C(x) + E(x):
M(x) = 4 x^{6} + 2 x^{5} + 5 x^{4} + 5 x^{3} + 1 x^{2} + 1 x + 0
The errored symbol is shown highlighted.
Correcting the Error...
Dividing the errored codeword M(x) by G(x) gives a nonzero remainder, signalling the presence of an error.
M(x) / G(x) = (4 2 5 5 1 1 0) / G(x), giving remainder (4 5) (Check the math)
Observe that dividing the error pattern E(x) by G(x) gives the same nonzero remainder.
E(x) / G(x) = (7 0 0 0 0 0 0) / G(x), giving remainder (4 5) (Check the math)
The remainder (4 5) corresponds to the specific error pattern E(x) = 7 x^{6} and matches it to the errored word M(x). This singlesymbol 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 3bits, the RS codes inherently provide substantial bursterror correction.
Error Lookup Table, given a remainder (x y)
The remainder corresponding to E(x) = 7 x^{6} is shown highlighted. No other remainder matches this value.
x^{6}  x^{5}  x^{4}  x^{3}  x^{2}  x^{1}  x^{0}  
1  (6 2)  (7 2)  (7 3)  (1 1)  (6 3)  (1 0)  (0 1) 
2  (7 4)  (5 4)  (5 6)  (2 2)  (7 6)  (2 0)  (0 2) 
3  (1 6)  (2 6)  (2 5)  (3 3)  (1 5)  (3 0)  (0 3) 
4  (5 3)  (1 3)  (1 7)  (4 4)  (5 7)  (4 0)  (0 4) 
5  (3 1)  (6 1)  (6 4)  (5 5)  (3 4)  (5 0)  (0 5) 
6  (2 7)  (4 7)  (4 1)  (6 6)  (2 1)  (6 0)  (0 6) 
7  (4 5)  (3 5)  (3 2)  (7 7)  (4 2)  (7 0)  (0 7) 
Select a primitive polynomial P(x)

20241111 09:26:04 AST
Last Updated: 20130103 
Richard Tervo [ tervo@unb.ca ]  Back to the course homepage... 