BCH codes

6.1 INTRODUCTION
BCH codes are a class of cyclic codes discovered in 1959 by Hocquenghem [1] and
independently in 1960 by Bose and Ray-Chaudhuri [2]. They include both binary and
multilevel codes and the codes discovered in 1960 by Reed and Solomon [3] were soon
recognized to be a special case of multilevel BCH codes [4]. In this chapter we shall
confine our attention to binary BCH codes, leaving Reed Solomon codes to Chapter 7.
From the discussions of Chapter 4, we could, given a generator polynomial, con-
struct an encoder for binary BCH codes. Moreover, using the discussions of finite field
arithmetic in Chapter 5, it requires only a straightforward extension of the principles of
Chapter 4 to construct an encoder for a Reed Solomon code, given the generator
polynomial. The purpose of this chapter is to show the structure of BCH codes and the
decoding methods. We will therefore be able to work out the generator polynomials
for any code of interest and to implement low complexity decoders.

6.2 SPECIFYING CYCLIC CODES BY ROOTS

It is possible to specify a cyclic binary code by saying that the codewords are binary
polynomials with specific roots in GF(2W). These roots, being common to every
codeword, are inherited from the generator polynomial. Note that the concepts of
conjugacy will apply and that the existence of a particular root will imply the
existence of the conjugates. Thus the generator polynomial will be constructed
from the minimum polynomials of the roots. For example if the specified root is a
from GF(8), we know that the minimum polynomial is X3 + X + 1, and all code-
words must be multiples of this minimum polynomial. In this case the minimum
polynomial acts as the generator for the code.
In general the generator polynomial will be the least common multiple of the
minimum polynomials for the specified roots. The degree of the polynomial, which
is equal to the number of parity check symbols for the code, is the same as the
number of separate roots, so that the total number of code roots gives the number of
parity check symbols.
From the discussions of Chapter 5, we recall that the values of roots of a time
domain polynomial are equivalent to the positions of zeros in the frequency domain.
138 ERROR CONTROL CODING

We shall therefore be able to say equivalently that all codewords of a cyclic code have
zeros at specific locations in the frequency domain.

6.3 DEFINITION OF A BCH CODE

A f-error correcting q-ary BCH code of length qm - 1 is a cyclic code whose roots
include 2t consecutive powers of a, the primitive element of GF(qm). There will be
two main cases of interest:

• Binary BCH codes will consist of binary sequences of length 2m — 1 with roots
including It consecutive powers of the primitive element of GF(2m). Alternatively,
the Fourier transform over GF(2m) will contain 2t consecutive zeros. Note that the
generator polynomial will have conjugate roots (or conjugate frequency domain
zeros) in addition to the specified 2t values.

• Reed Solomon codes are the special case where m = 1. They therefore consist of
sequences of length q — 1 whose roots include 2t consecutive powers of the primi-
tive element of GF(q). Alternatively, the Fourier transform over GF(q) will contain
2t consecutive zeros. Note that because both the roots and the symbols are
specified in GF(q), the generator polynomial will have only the specified roots;
there will be no conjugates. Similarly the Fourier transform of the generator
sequence will be zero in only the specified 2t consecutive positions.

The individual codewords, being multiples of the generator, may have roots in
addition to the ones specified, depending on the multiplying polynomial. However
the generator itself will have only the roots (or frequency domain zeros) implied by
the above, and only those roots (or frequency domain zeros) will be common to every
codeword.

6.4 CONSTRUCTION OF BINARY BCH CODES

To create some realistic multiple-error correcting examples, we shall need to work
with codes of length 15 or more, implying a need to construct corresponding finite
fields. We therefore construct GF(16) so that we can define codes of length 15. The
primitive polynomial to be used is p(X) = X4 + X + 1. The polynomial basis repre-
sentation of the elements is shown in Table 6.1.

Single-error correcting code

Suppose we choose a1 and a2 as the consecutive roots for this code. We know that
there will be conjugate roots, the full set of conjugates being

a1 a2 a4 a8
 BCH CODES 139

Table 6.1 GF(16)

Element Value
0 0000
a° 0001
a1 0010
a2 0100
a3 1000
a4 0011
a5 0110
a6 1100
a7 1011
a8 0101
a9 1010
a 10 0111
a11 1110
a12 1111
a 13 1101
a 14 1001

This set of conjugates contains the two roots we want, therefore no others are
required. The generator polynomial is

g(X) = (X + a.{)(X + a2)(X + a 4 ) ( X + a8)

g(X) = X4 + X3(al + a2 + a4 + a8) + X 2 (a 3 + a5 + a9 + a6 + a10 + a 12 )

Alternatively we find that the generator polynomial is the LCM of the minimum
polynomials of a1 and a2. Both these elements have X4 + X + 1 as their minimum
polynomial, therefore this is the generator of the code. The code has 4 parity checks
(from the degree of the generator) and so is a (15, 11) code.
Note that the generator polynomial is primitive and that therefore the code created
is a Hamming code. We can therefore see that cyclic Hamming codes are just single-
error correcting binary BCH codes.

Double-error correcting code

Following on from the above example, we choose a1 a2 a3 and a4 as our desired

roots. Starting from a and including the conjugates we find as for the Hamming code
that we have roots

a1 a2 a4 a8
140 ERROR CONTROL CODING

However we still need another root, namely a3. Including the conjugates we create
roots

a3 a6 a12 a9

The generator polynomial is

g(X) = (X4 + X + 1) (X4 + X3 + X2 + X + 1)

g(X) = X8 + X7 + X6 + X4 + 1

Alternatively we can see that X4 + X + 1 is the minimum polynomial of a1 a2 and

a , the minimum polynomial of a3 is found to be X4 + X3 + X2 + X + 1 leading to
4

the result above. The degree of the generator is 8, so the code is (15, 7).

Triple-error correcting code

To make a triple-error correcting code we want to have roots a1 a2 a3 a4 a5 and a6.

Note that the double-error correcting example had all these except a5, so we take
another set of conjugate roots, namely

a5 a10

The minimum polynomial of a5 is found to be X2 + X + 1 , leading to

g(X) = (X8 + X7 + X6 + X4 + 1 ) ( X 2 + X + 1)
g(X) = X10 + X8 + X5 + X4 + X2 + X + 1

With a degree 10 generator, and therefore 10 parity checks, this is a (15, 5) code.

6.5 ROOTS AND PARITY CHECK MATRICES

Cyclic codes can of course also be represented in terms of their parity check or
generator matrices. The parity check matrix H can be derived in a straightforward
way from the roots of the generator. If a code polynomial v(X) has a root ft then

If vn is the coefficient of Xn then

Vn-1ß
n-1
+ • • • + v2 ß2 + v1ß + v0 = o
or in vector form
 BCH CODES 141

(6.1)

Similarly if there are j roots ß1 to ft then

ßn-1Pi . r1"
ft ' ft-! =0 (6.2)

i ft
ft
ftl
1 i i
but

=0

which means that the large matrix in Equation (6.2), when transposed, will give the
parity check matrix of the code.
The roots are polynomials in a and so may be regarded as vectors which themselves
need to be transposed. Therefore

1t
H= (6.3)
2r2 :
ßj-1 2r ßj-1r 1
ßj ßj 1:
Only one of the roots ß, ß2, ß4, ß8, etc. needs to be included in the parity check
matrix as the inclusion of any one implies all the others.

Hamming codes

Hamming codes have generator polynomials which are primitive. Hence any primi-
tive element can be a root of the code. If we take the element a as the root then

H= (6.4)

The powers of a are just all the nonzero elements of the field which leads to the
conclusion that the columns of the parity check matrix contain all the possible
combinations of 1 and 0. For example taking the code based on GF(8), for which
a3 + a + 1 = 0, gives
142 ERROR CONTROL CODING

1 1 1 0 1 0 0
H 0 1 1 1 0 1 0
1 1 0 1 0 0 1

This is in fact the parity check matrix for the cyclic Hamming code in Chapter 4.

Binary BCH codes

A double-error correcting binary BCH code might have roots of a, a2, a3 and a4. Of
these, only a and a3 are independent, the others being implied by a, and so the parity
check matrix is

H = (n-1)
or a (6.5)
a3 r a 3x2 a

For the length 15 code, we obtain

— II a'12
H— 4 r
3x2
a

or

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
H=
1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
1 0 1 0 0 1 0 1 0 0 1 0 1 0 0
1 1 0 0 0 1 1 0 0 0 1 1 0 0 0
1 0 0 0 1 1 0 0 0 1 1 0 0 0 1

Note that this does not correspond to the usual definition of the parity check
matrix for a systematic code. It will, however, be seen to be useful for decoding.
A triple-error correcting code would introduce an additional root a5. The parity
check matrix becomes

1T
H= 1T (6.6)
1T

Corresponding to this, the parity check matrix for the length 15 code is

1T
H
,10r 1T

which in binary terms is

 BCH CODES 143

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
1 0 1 0 0 1 0 1 0 0 1 0 1 1 0
H=
1 1 0 0 0 1 1 0 0 0 1 1 0 0 0
1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0 1 1 0 1 1 0 1

Note, however, that there is one all-zero row and one that duplicates the previous
one. Both can therefore be removed from the parity check matrix to give

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
H=
1 0 1 0 0 1 0 1 0 0 1 0 1 0 0
1 1 0 0 0 1 1 0 0 0 1 1 0 0 0
1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0 1 1 0 1 1 0 1

Again this is not the usual systematic form.

6.6 ALGEBRAIC DECODING

BCH codes allow an algebraic method of decoding. Consider the case of a double-
error correcting code where there are errors at positions / and/ The syndrome is

The syndrome has two components s1 and s3:

(6.7)
s3 = a3j-a3j + a3j

Substituting the first into the second gives

=0 (6.8)

Any value of ai which is a root of this equation will locate an error and, as the
assignment of the parameters i and j is arbitrary, both error locations can be found
144 ERROR CONTROL CODING

from the same equation. Roots can be found by trying all possible values, which is
better than having to try all possible combinations of positions, or by other tech-
niques. This method is known as a Chien search.

Example
For the double-error correcting BCH code of length 15, if the received sequence is
101010110010101, the syndrome is 10010110. Thus

s1=a14

s3 = a5

Substituting in Equation (6.8) gives

a 13+i +a 14+2i +a 12 +a 5 =

The value i = 2 gives

The value i= 1 3 gives

The errors are therefore at positions 2 and 13 giving a transmitted sequence

111010110010001. The syndrome of this sequence is zero, showing that it is a codeword.

Of course it is possible that a single error may occur in a double-error correcting

code. In that case Equation (6.7) becomes

s1 = ai
s3 = a3i

This condition can be recognized from the fact that s3 = (s1 )3 and the position of
the error found directly from s1 .

6.7 BCH DECODING AND THE BCH BOUND

We have previously seen that binary BCH codes can be decoded by a polynomial
with roots that indicate the positions of the errors. The method as described is
suitable for single or double errors and can be extended to more errors, but with
increasing complexity. To find a more general method, we note that the syndromes
computed above are in fact the Fourier transform components in the positions of the
frequency domain zeros, and we look for a frequency domain description of algebraic
decoding.
 BCH CODES 145

We shall see in the next section that frequency domain decoding uses a polynomial
whose zero coefficients indicate the locations of errors in the time domain and whose
roots in the frequency domain can therefore be used to locate the errors. For the
moment we will use such a polynomial to prove a property of BCH codes, namely
that 2t consecutive zero-valued spectral components are sufficient to guarantee t-
error correction.
Suppose we have a code vector c(X) with fewer than d nonzero components, and
its spectrum C(z) has d - 1 consecutive zeros. We define a polynomial A(X) such that
it is zero where c(X} is nonzero and let the positions of the zeros be denoted ij. The
polynomial k(X) is usually called the error locator polynomial because, as we shall see,
there is no codeword apart from the all-zero sequence which satisfies the defined
conditions.
The zero components in 1(X) mean that each or'' will be a root of the transform
A(z) of MX), or

Note from the above definition of A(z) that AO is equal to 1 . The polynomial A(z) is
known as the connection polynomial.
Now in the time domain, A/c/ = 0 for all /, therefore in the frequency domain,
replacing multiplication with a convolution:

The degree v of A(z) is at most d — 1 and AO = 1 , which leaves us with

Ay (6.9)

This is the equation for the output of a linear feedback shift register with feedback
polynomial A(z), as shown in Figure 6.1.
If we know any d — 1 consecutive values of Cy we can use the shift registers with
feedback to generate all the rest. We know, however that there are d — I consecutive

Figure 6.1 Shift register representation of connection polynomial

146 ERROR CONTROL CODING

zeros and using them to initialize the feedback shift register will generate a string of
zeros. Thus Cj must be zero for ally and all terms in c(X) are zero. This proves that if
there are 2t consecutive zeros in the spectrum, the nonzero codewords must have
weight at least 2t + 1 and the code can therefore correct at least t errors.
Although we are left with the possibility that the code may be able to correct more
than t errors, the BCH decoding method will use the 2t consecutive zeros in a way
that will correct up to t errors, and any extra capabilities of the code will go into error
detection.

6.8 DECODING IN THE FREQUENCY DOMAIN

Assume that we transmit a code sequence c(X) and that it is received with the addition
of an error sequence e(X). We take the transform of the received sequence, giving

R(z) = C(z) + E(z)

where R(z), C(z) and E(z) are the transforms of the received sequence, the codeword
and the error sequence respectively. We know that C(z) is zero in 2t consecutive spectral
locations, so we can use these locations to give us a window on E(z), i.e. 2t components
of E(z) can easily be obtained and can be considered to form a syndrome S(z).
We assume that there are v < t errors and define an error locator polynomial A(X)
such that it is zero in the positions where e(X) is nonzero. The product of the received
sequence and the error locator sequence in the time domain will therefore be zero,
which means that in the frequency domain the convolution will be zero

AyEk-i = 0 (6.10)

Here we have used the fact that A.(X) has at most t zeros; hence, A(z) has at most /
roots and is therefore a polynomial of degree no greater than t. If we know the error
spectrum from positions m to m + 2t - 1, we can form t equations by letting k take
values from m + Mo m + 2t — 1. Assuming the spectral zeros of the code are from
positions 1 to 2t, the equations are as follows:

(6.11)
A0E2t-1 + A1E2t,_2 +- A,Et-1 = 0
Ai£ 2 ,_i H h A,£, = 0

This set of t equations in / + 1 unknowns is called the key equation, which we can
solve for the different values of A, provided we impose an arbitrary value on one of
the roots, corresponding to the fact that the value of the error locator polynomial is
arbitrary in the nonzero positions in the time domain. In practice the condition we
impose is A0= 1. The procedure for solving the key equation may be straightforward
 BCH CODES 147

if t is small, but in the general case special methods have to be devised which are
computationally efficient and which take into account the fact that the number of
errors may be less than t. One such method, Euclid's algorithm, will be explained in a
later section. For the moment it is sufficient to believe that the task can be accom-
plished.

6.9 DECODING EXAMPLES FOR BINARY BCH CODES

Take the example of the (15, 7) binary BCH code from Section 6.6 where we received a
sequence 1010101 100 10101 which was found to have two errors, in positions 2 and 13.
To find the syndrome, we calculate the Fourier transform of the received sequence in
the positions of the zeros, i.e. positions 1, 2, 3 and 4. In fact the value in position 2 is,
through conjugacy, the square of the value in position 1 and the value in position 4 the
square of that in position 2. We therefore need calculate only the values in positions
1 and 3 (found previously to be (a14 and a5) before filling in the values for positions 2
and 4. The syndrome polynomial is therefore

The key equation becomes

a5 + a 13 A 1 + a 14 A 2 = 0

a 11 +a 5 A 1 + a 13 A 2 =0

To solve, we can multiply each term in the second equation by a and add to the
first equation to eliminate A2n. This gives

A1=a14

Hence

A2 = 1

Decoding can now be carried out by finding the roots of z2 + al4z + 1, which are a2
and a13. Hence the errors are at positions -2 and -13, or 13 and 2, respectively.
Suppose now that only one error occurred, say the error in position 13. The
syndromes are found to be S1 = a 13 , S3 = a9, giving a full syndrome polynomial of

The key equation becomes

a 1 1 A 1 +a ! 3 A 2
an1 1 = 0
148 ERROR CONTROL CODING

It can be seen that these two equations are not linearly independent, the first being
merely a2 times the second. Only one unknown can therefore be found and the
connection polynomial must be of degree 1, i.e. A2 = 0. Inserting this condition
gives A1 = or2 = a13. The connection polynomial is therefore a 13 z+ 1, which has
root or-13, indicating an error at position 13. Any solution method therefore needs to
take account of the possibility that there may be fewer errors than the maximum
corrected by the code. Of course, in this case the occurrence of a single error can be
recognized through the condition 53 = (s 1 ) 3 from Section 6.6 and its location deter-
mined from the value of s1 .
Another possibility is that too many errors may occur and in that case the decoder
may give the wrong result or may detect the errors but be unable to correct them. We
need to know, however, how the decoding failure will arise.
Suppose we insert a third error at position 10 into our received sequence. The
syndromes are found to be s 1 =a 1 1 ,53 = a10. The full syndrome polynomial is

The key equation is

a 10 + a 7 A 1 + a l l A 2 = 0

a14 + a10A1 +- a 7 A 2 = 0

Eliminating A2 gives

a 1 2 +a 1 A 1 = 0

The connection polynomial is therefore a1z2 + a11z + 1. We now try to find the
roots as shown in Table 6.2. It is seen that no roots are found. The general condition
for detected uncorrectable errors is that the number of roots found is less than the
degree of the connection polynomial.

Table 6.2 Chien search for triple-error example

Root Evaluation Root Evaluation

a0 a1a0 + a"a^ + oP = a13 a8 a'a' + a"a -+• a^ = a
2
a' a'a + a" a' -+• ot® = a^ a9 a'a 3 -I- a"a9 + of = a2
a2 a1a4 + a"a2 + a° = a9 a10 a'a5 + a"a10 -I- a° = a°
a3 a 1 a 6 + a"a3 + a° = a4 a11 a'a 7 + a11*11 + a° = a12
a aa +a a +a =a a aa
a5 a l a l ° + a l l a 5 + a° = a13 a13 a'a 11
a6 a l a l 2 + a l l a 6 + a° = a3 a14 a'a 13
 BCH CODES 149

6.10 POLYNOMIAL FORM OF THE KEY EQUATION

In the previous section we have been involved in solving simultaneous equations in
order to carry out error correction. This we can do manually by substitution or other
means. For automatic implementation we need to find an approach which can be
efficiently and routinely implemented. To do this we first of all convert the key
equation from its expression as a summation into a polynomial format.
We wish to find a solution to the key equation, which can be expressed as

]T A/ E k-j = 0 t<k<2t-1
7 =0

This expression represents a convolution that can, alternatively, be given a poly-

nomial form. We have seen on a number of occasions previously that the convolution
of two sequences corresponds to the product of the sequence polynomials. In this
case it is equivalent to all the terms of degree between t and 2t — 1 in A(z)E(z). Hence
we can say

A(z)E(z) = f(z)z2t + n(z) (6.12)

The terms in the left-hand side of degree t to 2t — 1 are zero. The terms of degree 2t
or more are represented by f(z)z2t. Here, fi(z) represents the terms of degree less than
t. It is known as the error evaluator polynomial because it is used for such a purpose
in the decoding of multilevel BCH codes such as Reed Solomon codes.
There are two commonly used methods for solving the key equation in this form.
They are Euclid's algorithm and the Berlekamp-Massey algorithm. The latter is
more efficient, but is more difficult to understand than Euclid's method and is related
to it. We shall study the Euclid algorithm in detail and merely outline the steps
involved in the other.

6.11 EUCLID'S METHOD

The Euclid algorithm is most commonly encountered in finding the lowest common
multiples of numbers. In the process of so doing it identifies common factors so that
these can be taken into account in computing the lowest common multiple. Many
authors preface a discussion of Euclid's method with an illustration of its use for such
a purpose. Unfortunately, the connection between using it in this way and solving the
key equation is not easy to spot and the numeric application may not be of much help
in understanding the application to polynomials. For that reason, I prefer to confine
the discussion to the solution of equations involving polynomials. Euclid's method
enables us to find minimum degree solutions for polynomials f(z) and g(z) such that
150 ERROR CONTROL CODING

where r(z) is known to have degree less than some fixed value. In our case, r(z) will
have degree < t, a(z) = z2t and b(z) is the syndrome polynomial S(z). The polynomial
g(z) will give us A(z), which is what we need to know. The method involves repeated
division of polynomials until a remainder of degree < Ms found.
The first step is to divide a(z) by b(z) to find the quotient q 1 (z) and remainder r\(z):

a(z) = q 1 (z)b(z) + rl(z) (6.13)

If the degree of r 1 (z) is less than t then we have reached our solution with f(z) = 1,
g(z) = q1(z) and r(z) = r 1 (z). Otherwise set g1(z) = q1(z) and proceed to the next stage.
The second step is to divide b(z) by r 1 (z) giving

b(z) = q2(z)r1(z) + r2(z) (6.14)

Note that the degree of r2(z) must be less than that of r 1 (z) so that this process is
reducing the degree of the remainder. If we eliminate r\(z) from Equations (6.13) and
(6.14) we obtain

q2(z)a(z) = [q2(z)g1(z) + l]b(z) + r2(z) (6.15)

Set g2(z) = q 2 (z)g 1 (z) + 1. If the degree of r2(z) is less than t then g(z) = g2(z);
otherwise, continue to the next step.
The third step continues in similar vein, dividing r1 (z) by r2(z):

r1(z) = q2(z)r2(r) + r3(r) (6-16)

Again the degree of the remainder is decreasing. Using Equations (6.14) and (6.15)
to eliminate r 1 (z) and r2(z) gives

[1 + q2(z)q3(z)]a(z) = [g1=(z} + q 3 (z)g 2 (z)]b(z) + r3(z) (6.17)

If the degree of r3(z) is less than t then g3(z) = g3(z) = q 3 (z)g 2 (z) + g 1 (z).
The method continues in this way until a remainder of degree less than t is found,
at each stage setting

gn(z) = q n (2)g n - 1 (z) + gn-2(z) [g 0 (z) = 1, g-1,(z) = 0] (6.18)

Summary of Euclid's algorithm

Set n = 1. Divide z2t by S(z) to find quotient q 1 (z) and remainder r 1 (z). Calculate
g1(z) from Equation (6.18).
While degree of remainder is greater than or equal to t, continue by incrementing
n, divide previous divisor by previous remainder and calculate gn(z) by Equation
(6.18).
When desired degree of remainder is obtained, set A(z) = gw(z).
 BCH CODES 151

Example
We shall now solve the key equation for the double-error example from Section 6.9, using
the Euclid algorithm. We treat the syndrome with 4 terms as a degree-3 polynomial

Divide z4 by S(z) to give

z4 - (a 4 Z + a13)(a11z3 + a5z2 + a13z + a14) + a6z2 + a5z

Divide S(z) by a6z2 + asz + a12 to give

a11z3 + a13 + a13z + a14 = (a5z + a9)(a6z2 + a5z + a12) + a8

Set g2(z) = (a5z + a9)(a4z + a13) + 1 = a9Z2 + a8Z + a9.

As the remainder is of degree < 2, this is the end of Euclid's algorithm. The result for g2(z)
is the connection polynomial A(z). It can be seen to be a factor of a9 times the result
obtained in Section 6.9 and hence will have the same roots.

Applying Euclid's algorithm to a single-error example would terminate with a

polynomial of degree 1 . This is left as an exercise for the reader.

6.12 BERLEKAMP-MASSEY ALGORITHM

Another way to find the connection polynomial is to use the Berlekamp-Massey

algorithm. This algorithm is difficult to understand, although it synthesizes directly
the shift registers with feedback shown in Figure 6.1. It is also simple to implement;
consequently it will be described here but an explanation of why it works will not be
attempted. In the following description, the parameter / represents the degree of the
error locator polynomial and n represents the degree of the syndrome polynomial
being examined.
Table 6.3 shows a Pascal description of the algorithm in the left column and, in the
other columns, the steps in the calculations for our double-error BCH example. As
before, the syndrome will be treated as a polynomial of degree 3.
The algorithm terminates with A(z) holding the correct coefficients of the feedback
polynomial. Applied to a single-error example it will also terminate correctly with a
polynomial of degree 1. Note that on every second iteration of the main loop the
value of 6 is zero. This is because every second syndrome component in a binary code
is predictable from previous values. The algorithm could therefore be simplified for
the binary case to multiply D(z) by z2 at each iteration and to increment « by 2.
This version of the Berlekamp-Massey algorithm involves a division and, as men-
tioned in Chapter 5, finding the multiplicative inverse of an element is not straight-
forward. Given that only the roots of the connection polynomial are important,
152 ERROR CONTROL CODING

Table 6.3 Berkekamp-Massey algorithm for binary BCH example

begin
l:=0: 0
n :— 0; 0
k:=!; -1
A(z) := 1; 1
D(z):=zA(z); z
while (n < 2t) do 0<4 1 <4 2<4 3<4
begin
<5 := Z! A,Sn_i; a14 0 a14 0
i=0 14 14
if (5 =0) then a =0 0=0 a =0 0=0
begin
A* (z) = A(z) + 5 x D(z); a14z+l z2 + a 1 4 z+l
if (l<n - k) 0< 1 1 <2
begin
l :=n-k- 1 2
k:=n~l; 0 1
D(z) := A(z)/5; a1 z+a
/:=/* 1 2
end;
A(z):=A*(z) al4z+l z2 + a14z + 1
end;
Z)(z):=zZ)(z); a1z a'z2 z2 + az z 3 +az 2
«:=/7+l 1 2 3 4
end;
end.

we could multiply it by any constant. Thus we could eliminate the division in the line
D(z) := A(z)/<5 provided that on the line A* (z) = A(z) + 6 x D(z) we first multiply
the value of A(z) by the previously applied version of 6. We therefore introduce a
variable <5* and amend the algorithm to that shown in Table 6.4.
The working shown in Table 6.4 is again the stages in calculating the connection
polynomial for the double-error example of Section 6.9. The connection polynomial
is «14z2 + a13z + a14 which is just a14 times the previous result and therefore has the
same roots.

6.13 CONCLUSION
As indicated at the beginning of this chapter, BCH codes have a long history and are
therefore well represented in standard text books [5-9]. The inversionless Berlekamp-
Massey algorithm given here is similar to that published in [10] and another imple-
mentation is embodied in [11]. The performance and applicability of binary BCH
codes are discussed in Chapter 8.
 BCH CODES 153

Table 6.4 Inversionless version of Berlekamp-Massey algorithm

begin
/ := 0; 0
n :=0; 0
k : = -1; —1
A(z) : = 1; 1
D(z) := zA(z); z
(5* :=1; 1
while (n < It) do 0<4 1 <4 2<4 3<4
begin
f> :=[Link] n - i a14 0 a14 0
/=0 4
14
if (=^0) then a ^ 0 0=0 a' ^0 0=0
begin
A*(z) = 5* xA(z) + <5 x D(z); a14z+l a14:z2 + a13 + a14
if ( l < n - k ) 0< 1 1 <2
begin
l* : = n - k ; 1 2
k:=n-l; 0 1
(X...14 14

D(z) := A(z); a° a'4z+l

/:=/* 1 2
end;
A(z):=A*(r) a14z+l a14;j2 + a'3z + a14
end;
D(z):=zD(z); a0z a0z2 «14z2 + z «14z3 + z2
n :— n + 1 1 2 3 4
end;
end.

6.14 EXERCISES
1 Given that

X+ l)(X4 + X3 + l)(X4 + X3 + X2 + X

find the generator polynomial of a triple-error correcting BCH code of length 15,
assuming that GF(16) is created using the primitive polynomial X4 + X 3 + 1.

2 For the double-error correcting BCH code defined in Section 6.5, decode the
sequence 100010110010001.

3 Describe the frequency domain representation (i.e. positions of the zeros) of a

triple-error correcting BCH code of length 31. Why would you not put a zero in
position zero of the frequency domain?
154 ERROR CONTROL CODING

4 Find the generator polynomial of a triple-error correcting BCH code of length 15,
assuming that GF(16) is created using the primitive polynomial X4 + X3 + 1.

5 For the BCH code of length 15 with roots , a, a2, a3, and a4 in GF(16) (created
using the primitive polynomial X4 + X3 + 1), find the generator polynomial and
decode the following sequences
100010110010001
101110100101001
100110000011111

6.15 REFERENCES
1 A. Hocquenghem, Codes correcteurs d'erreurs, ChifFres, Vol. 2, pp. 147-156, 1959.
2 R.C. Bose and D.K. Ray-Chaudhuri, On a class of error-correcting binary group codes,
Information and Control, Vol. 3, pp. 68-79, 1960.
3 I.S. Reed and G. Solomon, Polynomial codes over certain finite fields, J. Soc. Indust.
Applied Math. Vol. 8, pp. 300–304, 1960.
4 D.C. Gorenstein and N. Zierler, A class of error-correcting codes in pm symbols, J. Soc.
Indust. Applied Math. Vol. 9, pp. 207-214, 1961.
5 R.E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, 1983.
6 G.C. Clark and J.B. Cain, Error-Correction Coding for Digital Communications, Plenum
Press, 1981.
7 A.M. Michelson and A.H. Levesque, Error-Control Techniques for Digital Communica-
tion, John Wiley & Sons, 1985.
8 S.B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall,
1994.
9 M. Bossert, Channel Coding for Telecommunications, John Wiley and Sons, 1999.
10 Y. Xu, Implementation of Berlekamp-Massey Algorithm without inversion, IEE Proceed-
ings-I, Vol. 138, No. 3, pp. 138-140, June 1991.
11 H-C. Chang and C-S.B. Shung, Method and apparatus for solving key equation polynomials
in decoding error correction codes, US Patent US6119262, September 2000.
7
Reed Solomon codes

7.1 INTRODUCTION
It was pointed out in Chapter 6 that Reed Solomon codes are a special example
of multilevel BCH codes. Because the symbols are nonbinary, an understanding of
finite field arithmetic is essential even for encoding. Moreover the decoding methods
will be similar to those encountered for binary BCH codes, so some familiarity with
Chapter 6 will also be advisable for the understanding of this chapter.
There are two distinctly different approaches to the encoding of Reed Solomon
codes. One works in the time domain through calculation of parity check symbols.
The other works in the frequency domain through an inverse Fourier transform. We
shall meet the time domain technique first as it is more likely to be encountered in
practice. It was pointed out in Chapter 6 that the standard decoding method is
essentially a frequency domain technique, but we will see that a modification is needed
for RS codes which can be achieved in two different ways. There is also a purely time
domain decoding method for RS codes - the Welch-Berlekamp algorithm - which will
be presented towards the end of the chapter.

7.2 GENERATOR POLYNOMIAL FOR A

REED SOLOMON CODE
A Reed Solomon code is a special case of a BCH code in which the length of the code
is one less than the size of the field over which the symbols are defined. It consists of
sequences of length q — 1 whose roots include 2t consecutive powers of the primitive
element of GF(q). Alternatively, the Fourier transform over GF(q) will contain 2t
consecutive zeros. Note that because both the roots and the symbols are specified in
GF(q), the generator polynomial will have only the specified roots; there will be no
conjugates. Similarly the Fourier transform of the generator sequence will be zero in
only the specified 2t consecutive positions.
A consequence of there being only 2t roots of the generator polynomial is
that there are only 2t parity checks. This is the lowest possible value for any
t-error correcting code and is known as the Singleton bound (see Chapter 8, Section
8.5).
156 ERROR CONTROL CODING

To construct the generator for a Reed Solomon code, we need only to construct the
appropriate finite field and choose the roots. Suppose we decide that the roots will be
from ai to a i + 2/-1 , the generator polynomial will be

In contrast to the case with binary BCH codes, the choice of value of i will not
affect the dimension or the minimum distance of the code because there are no
conjugates to consider.

Example
Suppose we wish to construct a double-error correcting, length 7 RS code; we first construct
GF(8) using the primitive polynomial X3 + X + 1 as shown in Table 7.1. We decide to choose
i = 0, placing the roots from a° to a3. The generator polynomial is

g(X) = (X + a°)(X + a1 )(X + c 2 )(X + a3)

g(X) = X4+ (a0 + a1 + a2 +«3)X3 + (a1 + a* + a3 +a4 + a5)X2

g(X) = X4 + a2X3 + a5X2 + a5X + a6

Table 7.1 GF(8)

Element Polynomial
0 000
a° 001
a1 010
a2 100
a3 011
a4 110
a5 111
a6 101

7.3 TIME DOMAIN ENCODING FOR REED SOLOMON

CODES
The encoding of a Reed Solomon code can be done by a long division method similar
to that of Chapter 4 (Section 4.9) or, equivalently, by shift registers with feedback.
The long division method is slightly more complicated than in Chapter 4 because
we need to subtract multiples of the divisor from the dividend so that the degree of
the remainder is reduced. In the binary case the multiple is always 0 or 1, but here we
need to choose an appropriate value from the finite field. Also the binary data will
first need to be mapped onto finite field symbols and the result mapped back to
binary values. An example will illustrate this.
 REED SOLOMON CODES 157

Example
For the Reed Solomon code above, encode the data sequence 111001111. Assuming the
polynomial mapping in Table 7.1, the data maps to symbols a5 a° a5. Four zeros are
appended, corresponding to the four parity checks to be generated, and the divisor is the
generator sequence.

a5 0 a2
a5 a5 «6)«5 «° a* 0 0 0 0
«5 a° a3 a3 a4

a2 a3 «4 00
a2
a a° a° a1
4

As shown, the multipliers used were a5 0 and a2. The remainder is a6 a5 a° a1 so that
the codeword is a5 a° a5 a6 a5 a° a1. Expressed as a binary sequence this is
111001111101111001010.

The encoder circuit for a Reed Solomon code is shown in Figure 7.1. This is almost
identical to Figure 4.3 except that the value of go is not necessarily 1 and there are
multipliers in every feedback connection rather than just connection or no connec-
tion as there was for the binary case. In fact all the feedback terms will be nonzero for
a Reed Solomon code.
The encoder for the above example is shown in Figure 7.2 and the stages in the
encoding in Table 7.2. The example terminates with the registers containing the
values a6 a5 a° a1, the parity checks for this codeword.

Figure 7.1 Schematic of Reed Solomon encoder

Figure 7.2 (7, 3) Reed Solomon encoder

158 ERROR CONTROL CODING

Table 7.2 Parity generation for (7, 3) Reed Solmon example

3
Input Feedback Register jr2
X2 X1 X°
multiplier a a 5
a5 a6

0 0 0 0
a5 a5 a° a3 a3 a4
a° 0 a3 a3 a4 0
a5 a2 a6 a5 a° a1

7.4 DECODING REED SOLOMON CODES

The frequency domain algebraic decoding method explained in Chapter 6 (Section
6.8) is used to decode Reed Solomon codes. There are, however, two differences. The
first is that all the syndromes must be calculated from the received sequence; we
cannot use conjugacy to find some of the values. Secondly, once we have located the
errors we need to find their value to carry out the correction; this will require an extra
stage in the decoding.
Error value calculation can be done using the Forney algorithm. Recall that in
Chapter 6 (Equation (6.12)) we found that

where A(z) is the connection polynomial, E(z) can be taken as the frequency domain
syndrome terms expressed as a polynomial and O(z) is a polynomial of degree / — 1
known as the error evaluator polynomial. We calculate the error evaluator polyno-
mial and also A'(z), the formal derivative of the connection polynomial. This is found
to be

(even t) A,_, z''2 + A t_3 z*'4 + • • • + AI

/
(oddr) A , z -

In other words, get rid of the zero coefficient of A and then set all the odd terms in
the resulting series to zero.
The error value in position m is now

A'(z) (7.2)

evaluated at z = a~m. The parameter i is the starting location of the roots of the
generator polynomial.
 REED SOLOMON CODES 159

7.5 REED SOLOMON DECODING EXAMPLE

Consider the codeword a5 a° a5 a6 a5 a° a! previously generated for the double-error
correcting (7, 3) RS code. We create errors in positions 5 and 3, assuming that we
receive a5 a4 a5 a3 a5 a° a1. The frequency domain syndrome of this sequence is

S0 = a5 + a4 + a5 + a3 + a5 + a° + a1 = a0
S1 = a 5 - a 6 + a 4 - a 5 + a 5 - a 4 + a 3 -a 3 + a? • a2 + a0 • a.1 +a! = a1
S2 = a5- a5 + a4- a3 + a5- a1 + a3- a6 + a5- a4 + a°- a2 + a1 = a°
S3 = a 5 -a 4 + a 4 - a 1 +a 5 - a5 + a3- a2 + a5- a6 + a°- a3 +a1 = 0

Now we form the key equation for which the solution is

a 6 A 1, = a1
A1 = a2 A

The roots of the connection polynomial are a4 (as a1 a8 + a2 a4 + 1 = 0) and a2 (as

a a + a2 a2 + 1 = 0). Having found two roots for a connection polynomial of degree
1 4

2 indicates successful error correction with errors located at positions -4 and -2, i.e.
positions 3 and 5. We now calculate the error evaluator polynomial, taking the
powers from 0 to t — 1 of S(z)A(z).

H(z) = (S0 A1 + S1 A 0 )z + S0A0

H(z) - (a1 + a3 + a 0 )z 2 + (a2 + a 1 )z + a°
H(z) = a4z + a0

For the assumed g(X) in which i = 0, we want zA'(z) as the denominator which is
just A(z) with all the even coefficients set to zero. Therefore

em —
zA'(z) ,=g_-m a2;

Evaluating at m = 3 and m = 5 gives

a 4 a - 3 + a° a3 ..4

2
°
160 ERROR CONTROL CODING

The received symbol a3 at position 3 is therefore corrected to a6. The received

symbol a4 at position 5 is corrected to a°. This successfully completes the decoding.

7.6 FREQUENCY DOMAIN ENCODED REED

SOLOMON CODES
As the Fourier transform of a Reed Solomon code word contains n — k consecutive
zeros, it is possible to encode by considering the information to be a frequency domain
vector, appending the appropriate zeros and inverse transforming. The encoding and
decoding processes are illustrated in Figure 7.3. In this case the final step of decoding
will differ from that in the previous section because we need to obtain the errors in the
frequency domain.
We will choose again a (7, 3) double-error correcting RS code over GF(23). Let the
information be a2, a5, a° (representing binary information sequence 100111001) and
let the zeros in the frequency domain occupy the positions 0 to 3. We therefore put
the information into positions 4, 5 and 6 in the frequency domain with zeros in the
other positions, producing the transform of the codeword as a2 a5 a° 0 0 0 0.
An inverse Fourier transform generates the codeword as follows:

c0 = a2 + a5 + a° = a1
c1 = a2 + a5 a2 + a0 = a°
c2 = a2 + a5 a4 + a0a6 = a5
c3 = a2 + aV + aV = a6

k information symbols 2t zeros

Inverse Fourier transform

codeword

codeword

syndrome
Error correction

k information symbols 2t zeros

Figure 7.3 Frequency domain encoding and decoding of Reed Solomon codes
 REED SOLOMON CODES 161

c4 = oc2a4 + aV + a°a5 = a5
c5 = « 2 a 5 + a 5 a 3 + aV = a°
c6 - a 2 a 6 + aV + a°a4 = a5

Hence the code sequence is a5 a° a5 a6 a5 a° a1. This is in fact the same codeword
that we created from different information in Section 7.3. The previous encoding
method was systematic whereas this method is not. There is no straightforward way
to recover the information from the codeword.
We now create a two-symbol error, say a5 in position 5 and a4 in position 3, as in
our previous example. The received sequence is a5 a4 a5 a3 a5 a° a1.
The decoding proceeds by finding the Fourier transform of the received sequence:

RO = a5 + a4 + a5 + a3 + a5 + a° + a1 = a°
R1 = aV + aV + a5a4 + aV + aV + aV + a'a° = a1
R2 = aV + aV + aV + oc3a6 + aV + aV + a'a° = a°
R3 - a5 a4 + aV + aV + aV + aV + a°a3 + a'a 0 = 0
R4 = a5a3 + aV + «5a2 + a3a5 + aV + a°a4 + a'a 0 = a3
R5 = a5a2 + a4 a4 + a5a6 + aV + asa3 + a°a5 + a'a° = a2
R6 = a 5 «' + a4 a2 + a5a3 + a3a4 + aV + a°a6 + a'a 0 = a5

Hence the transformed received sequence is a5 a2 a3 0 a° a1 a° with the syndrome

being 0 a° a1 a°.
We now form the key equation with t = 2 and A0 = 1 :

a 1 A 2 + a 0 A 1 +0 = 0

As before the solution is

a6A = a1
A] = a2 A2 = a

Instead of carrying out a Chien search, however, we use the connection polynomial
to synthesize shift registers with feedback, as in Figure 6.1, to generate the entire
frequency domain error sequence. If we initialize the registers with E2 and E3 (which
are just the syndrome components in those positions), subsequent shifts will generate
E4, E5 and E6. This process is known as recursive extension of the frequency domain
error sequence. The general arrangement is shown in Figure 7.4 where it is considered
that we may have used a method such as the inversionless Berlekamp-Massey algo-
rithm or the Euclidean algorithm to obtain a connection polynomial where A0= 1 .
In our case we have obtained a solution with A0 = 1 ; therefore, the circuit becomes
as shown in Figure 7.5.
We load the value a° into the leftmost stage of the shift register, and zero into the
other stage. Cycling the shift register will generate values a1, a3, a3, which are the
162 ERROR CONTROL CODING

Figure 7.4 General shift register for double-error recursive extension

Figure 7.5 Example shift register for recursive extension

frequency domain errors in positions 4, 5 and 6, respectively. The next two values
generated are a°, a1, corresponding to syndrome components Sb and S\. Thus the
cycle will repeat; it can be shown that a failure to repeat is the condition for detection
of uncorrectable errors.
The complete error sequence in the frequency domain is a3 a3 a1 0 a° a1 a°.
Adding this to a5 a2 a3 0 a0 a1 a°, the Fourier transform of the received signal,
gives a decoded sequence of a2 a5 a° 0 0 0 0. Thus we have shown that double-
error-correction has been achieved.

7.7 FURTHER EXAMPLES OF REED SOLOMON

DECODING
The previous section worked through an example in which the number of errors was
exactly equal to the error correcting ability of the code. There are two other types
of cases where the outcome is not obvious and which we need to study. They are the
cases where the number of errors is less than the error correcting capability and
where there are more errors than the code can correct.
Let us first suppose that three errors are introduced into the transmitted codeword
and that the received sequence is a6 a4 a5 a3 a5 a0 a1, an extra error of magnitude a
having been created in position 6. The Fourier transform is

R(z) = a3 + aV + a6z4 + aV + aV + a3z + a3

from which the key equations are found to be

 REED SOLOMON CODES 163

a2 + + a3A2 = 0
a3 + + a3A2 = 0

Eliminating A2 gives

a5 + a 5 A 1 = 0
A1 - a°
A? = or

The registers for recursive extension are shown in Figure 7.6. After initializing with
values a3 a2, the error sequence generated is a2 a6 a5 followed by a5. The sequence is
therefore incorrect because the syndrome S0 has not been generated at this point. The
general condition for detection of uncorrectable errors is that the sequence generated
by recursive extension is not cyclic with the correct length. This can be shown to be
identical to the condition that the Chien search does not return the correct number of
roots.
Looking next at the case where we have fewer than the maximum number of
correctable errors, it is obvious that if there are no errors then the transform of the
codeword will exhibit zeros in the expected places and no decoding is required. If
there are some errors, but less than t, the transform of the error locator polynomial
will have fewer than t unknown roots and the t simultaneous equations will not be
linearly independent. This will be illustrated by returning to the example of the
previous section but this time introducing only one error.
Let us assume that we receive a sequence a5 a4 a5 a6 a5 a° a1. This is the same as
the previous example except that position 3 does not contain an error, the sole error
being in position 5. The transform is

R(z) = a6z6 + aV + aV + aV + a)z2 + a3z + a5

from which the key equations are found to be

a 1 +a 3 A 1 +a 5 A 2 =0
a6 + a'A 1 +a 3 A 2 = 0

This is similar to what happened in the single-error example of Section 6.9. The
second equation is the same as the first, multiplied by a2, which tells us that there is

Figure 7.6 Attempted recursive extension after triple error

164 ERROR CONTROL CODING

Figure 7.7 Recursive extension with single error

only one error and we must set A2 equal to zero. The solution to the key equation is
thus

A 1 =a 5

and loading the value a6 into the shift register of Figure 7.7 gives the sequence
a4 a2 a° as the corrections to the frequency domain data positions 4, 5 and 6, then
the next value is a5 which reproduces the value of s0, showing that the error correc-
tion is successful. We therefore correct the received Fourier transform values in
positions 6, 5 and 4, a6 a3 a5 to a2 a5 a°, the information encoded in Section 7.7.
The fact that in the above example each term in the syndrome is a constant factor
times the previous term is characteristic of single symbol errors, and the position of
the error in the time domain can be readily determined from the factor. In this case
because Sj = a5Sj-i, the error is in position 5 and the value of so is the error value in
that location. It is often worth including a check for single errors in a decoder and a
special decoding routine, because in many practical examples single errors will make
up a significant proportion of the sequence errors. Moreover all decoders will have to
cope with the case where there are fewer than / errors.

7.8 ERASURE DECODING

One feature that is sometimes incorporated into decoders for Reed Solomon codes is
the ability to recover events known as erasures. These are instances when there is
knowledge that a symbol is likely to be in error, perhaps through the detection of
interference. Erasure decoding could be regarded as a first step in soft-decision
decoding because, in comparison with what was transmitted, an extra level has
been introduced into the received sequence.
When an erasure occurs, the maximum likelihood decoding method is to compare
the received sequence with all codewords, but ignoring the symbol values in the
erased positions. The erasures are then filled using the values from the selected
codeword. With e erasures there will still be a minimum distance of dmin - e between
codewords, counting only the unerased places. Thus we will obtain decoding pro-
vided 2t is less than this reduced minimum distance:

2t + e < dn (7.3)
 REED SOLOMON CODES 165

At this point, one might well ask whether there is any point in declaring erasures
on a binary symmetric channel. A f-error correcting code will be able to fill up to 21
erasures, but if a guess was made for the values of all the erased symbols then on
average half would be correct and the error correction would cope with the rest. It
will be seen shortly that erasures do give some advantage, in that erasure filling is
equivalent to carrying out error correction on two possible sets of reconstituted bit
values, and then choosing the better of the two. On the other hand, the demodulator
need only have a slight inclination towards one or other value to make choosing the
more likely bit value a better strategy than erasure.
For any binary code there is a straightforward, nonalgebraic erasure filling
method. Replace all the erased bits by zero and decode. If no more than half of the
erasures should have been ones and Equation (7.3) was satisfied, then the number of
errors will still be less than half of dmin and the decoding will be correct. If on the
other hand more than half the erasures should have been ones then we may get a
decoding that will introduce extra errors into the sequence.
In this case, replacing all the erased bits by 1 will be successful. The procedure is
therefore to decode twice, replacing all the erased bits firstly with zeros and then with
ones. If the decoded sequences differ, choose the one that is closer to the received
sequence.
In contrast, if several bits of a Reed Solomon symbol are erased, it is unlikely that they
can be guessed correctly and erasure filling is a good strategy. They may be decoded
in the presence of erasures by an algebraic technique to be explained below. The
minimum distance of these codes is n — k + 1, which means that in the absence of errors,
Equation (7.3) shows that n-k erasures can be filled. We thus have the interesting
result that a Reed Solomon codeword can be recovered from any k correct symbols.
To decode algebraically, we replace the erased symbols by some arbitrary value,
usually zero. We adopt the polynomial approach in the frequency domain and
multiply the product of the syndrome polynomial S(z) and the connection polyno-
mial A(z) by an erasure polynomial F(z) which is known because the positions of the
erasures are known. For every two erasures, the degree of the error locator polyno-
mial is reduced by one so that the degree of the product of erasure and error locator
polynomials is increased by one. The number of simultaneous equations that can be
formed will thus be reduced by one, thus matching the reduction in the number of
unknowns. This all sounds rather horrific, but is fairly straightforward if considered
in the context of an example.

7.9 EXAMPLE OF ERASURE DECODING OF

REED SOLOMON CODES
We choose as our example the first case from Section 7.7 in which there was one error
at position 5 in the received sequence, but we introduce also two erasures in positions
6 and 1. The received sequence will be taken as 0 a4 a5 a6 a5 0 a1. The Fourier
transform is

R(z) = a6z6 + aV + aV + a'z 3 + a6z2 + a5 + a°

166 ERROR CONTROL CODING

The low order terms of R(z) form a syndrome of the received sequence.
The erasure polynomial is

F(z) = ( a 6 z + l ) ( a ' z + l ) = z 2 + a 5 z + l

The error locator polynomial is

A(z) = A 1 z + l

and the product is

F(z)A(z) = A,z 3 + [a° + a^Jz 2 + [a5 + A,]z + 1

As this polynomial is of degree 3, we can only carry out a single place convolution
with a known section of the error spectrum to produce a key equation. We are
therefore only interested in the terms of degree 3 when we multiply by the syndrome

giving as our key equation

a°A1 + a5 + a3A1 + a4 + a 6 A, + a1 = 0
a5A1 = a3; A1 = a5

We can now substitute this value back into the expression for F(z)A(z), which will
be the polynomial used to generate the errors in the frequency domain by recursive
extension:

This gives rise to the circuit shown in Figure 7.8 to be used for recursive extension.
Loading with values a5 a6 a1 and shifting gives the sequence a1 a1 a° and then,
regenerating the syndrome, oc° a5, a6. The error correction is therefore successful
and the values a° a1 a1 are added to the components a6 a6 a3 from the Fourier
transform of the received sequence to give recovered information a2 a5 a°.

Figure 7.8 Recursive extension with one error and two erasures
 REED SOLOMON CODES 167

If instead we choose to use the Forney algorithm to correct errors in the time
domain, the error evaluator polynomial is found to be

O(z) = [S(z)F(z)A(z)]mod z4 = ocV + a5z + oe°

Note that the degree of this polynomial is now 2 because there are effectively three
errors to correct. To calculate error values, we also need the formal derivative of
F(z)A(z), i.e. of oc5z3 4- oc'z2 + a°. The value of this derivative is z5z2. Therefore at
position i, the error value is

The polynomial F(z)A(z) has known roots a- 6 and a ] (because erasures were
detected there) and a further root a-5 that can be located by Chien search. Calculat-
ing the error values at positions 1, 5 and 6 gives e\ = oe°, e5 = a5, e6 — a5. The
received sequence is therefore corrected to a5 a° a5 a6 a5 a° a1, corresponding to
the original codeword.
Euclid's algorithm may be used to solve for the feedback polynomial in the
presence of erasures by initializing g1(z) as F(z) and terminating when the degree of
the remainder is less than t + e/2 (e is the degree of the erasure locator polynomial,
assumed to be even). To operate the Berlekamp-Massey algorithm, set l and n to e
and initialize A(z) to F(z).

7.10 GENERALIZED MINIMUM DISTANCE

DECODING
Having the ability to fill in erasures allows us to deal effectively with certain types of
interference and also to implement some approaches to soft-decision decoding. One
well-known approach is Forney's Generalized Minimum Distance (GMD) decoding
[1].
The principle of GMD decoding is very simple. We use a f-error correcting code
and, from the soft-decision information on the received sequence, we rank the
received symbols according to reliability. The decoding procedure is then:

1 Decode for f-error correction.

2 Erase the two least reliable symbols and decode for t — 1 errors and 2 erasures.

3 If the number of erasures is 2t, stop decoding and go to step 5.

4 From the symbols input to the previous decoding, erase the two least reliable (i.e.
increase the number of erasures by 2), decode and return to step 3.

5 From the decoded sequences produced, choose the closest to the received sequence.
168 ERROR CONTROL CODING

There will be at most / + 1 decoded sequences to compare; in practice when the

number of errors exceeds t there may be fewer because the errors are likely to be
uncorrectable. It is not clear, however, whether the performance gains will be worth
the effort of carrying out t + 1 decoding attempts.
The GMD algorithm is designed to work in conjunction with a particular metric of
goodness of decoded solutions. For each received symbol i with reliability r/, we count
+ri if the codeword matches and -r, if it does not. There can be at most one codeword
for which the sum over all symbols will exceed n - dmin and, if there is such a codeword,
GMD decoding will find it. For a binary code this is a good metric, although GMD is
still a bounded distance decoding rather than true maximum likelihood. For multilevel
codes transmitted over a binary channel, however, the metric may not be good. Over a
memoryless channel, we would consider that two symbol values differing in a single bit
are closer than two symbol values differing in several bits. The GMD metric, however,
treats those two cases as the same because symbols are treated as being either the same
or different. Only in burst-error conditions, or where an orthogonal modulation such
as MFSK is used, will the GMD metric be reasonable for a Reed Solomon code.
If we do, however, have conditions in which GMD seems to offer performance
benefits, the complexity needs to be considered. Using the Berlekamp-Massey or the
Euclidean algorithm, every decoding is a separate exercise with no way of reusing
results from previous decodings. However GMD can be implemented in conjunction
with another algorithm, the Welch-Berlekamp algorithm, in a way that builds on
previous results.

7.11 WELCH-BERLEKAMP ALGORITHM

The Welch-Berlekamp algorithm is another algebraic method for decoding Reed
Solomon codes. It is a time domain algorithm using values that are easily computed
from the received sequence, rather than the frequency domain syndromes used by
other algebraic methods. As a result, although the Welch-Berlekamp algorithm itself
is slightly more complex than the Berlekamp-Massey algorithm, the overall com-
plexity may well be lower if the actual number of errors to be corrected is not too
large. Moreover, it fits conveniently with GMD decoding.
The Welch-Berlekamp algorithm can be thought of as a kind of curve fitting
process. The points each have a value and a position, and a curve can be constructed
to fit any k points. When two more points are added, the curve must fit at least k + 1,
but the curve is allowed to miss one of the points. After adding another two points,
the curve must fit at least k + 2 of them. When eventually all n points have been
considered, the curve must fit at least (n + K)/2 of them.
Suppose, as in our previous double-error correction examples we transmit a code-
word from a (7, 3) RS code with roots a3, a2, a1, a° in GF(8). The first step is to
precompute some values needed for input to the algorithm and for error value
calculations. For the input to the algorithm we evaluate
 REED SOLOMON CODES 169

Therefore g3 = «°, g2 — a5, g1 = a6, go = a3-

For error value calculations we compute C = aV • • • a n-k--2 (a° + a1)(0 + a2) • •
(a° + an-k-1). For our example code the answer is a6. We now need for each of the
data locations the value of hi = C/g(ai) where g(a') indicates the evaluation of g(X) at
each of the data locations. The values are found to be

h5 = a 6 /a 1 = «5
h4 = a 6 / ° = a6

Assume we receive a sequence a5 a4 a5 a3 a5 a0 a1 . The first step is to compute the

syndrome obtained by division by the generator. This is found to be S3 = a°, s2 = a2,
s\ = a°, S0 = a6.
The input to the Welch-Berlekamp algorithm is the set of points (Sj, aj) where
Sj = Sj/gj. The input points are therefore (a°,a3), (a4, a2), (a1, a1), (a3,a°).
We need to find two polynomials Q(x) and N(x) for which

Q ( a j ) Sj = N(ajj) for 0 < j < n - k - 1

and the length L[Q(x), N(x)], defined as the maximum of deg[Q(x)] and
deg[N(x)] + 1, has the minimum possible value.
The steps in the algorithm are now:

1 Set g°(x) = 1, N°(x) = 0, W 0 (x) = x, V°(x) = 1 and d = 0.

2 Evaluate D 1 = Q d ( S d ) + Nd(y.d).
3 If DI = 0, set Wd+l = Wd(x + ad), Vd+l = Vd(x + a.d) and go to step 6; other-
wise, set D2 = Wd(y.d)Sd + Vd(a.d).
4 Set (Qd+1 = Qd(x + ad) Nd+l = Nd(x + ad), Wd+l = Wd
= Vd +NdD2/Di.
5 Check whether L[Wd, Vd] was less than or equal to L[(Qd, N d ]; if it was then swap
Qd+1,Nd+l with Wd+l, Vd+].
6 Increment d.
< n-k, return to step 1; otherwise, Q(x) = Qd(x), N(x) = Nd(x).

The steps in evaluation for this example are shown in Table 7.3.
The error locator polynomial is x2 + %2x + a1 which has roots a3 and a5. Finding
two roots for a degree 2 polynomial indicates that errors are correctable.
The error values in the data positions are

N(a k )
ek = hk (7.4)
170 ERROR CONTROL CODING

Table 7.3

Input Z), D2 L1 < L2 Q(x) N(x) W(x) V(x)

1 0 x i
0 X3 X3 X1 N x + a° 0 x + x5 i
1 X1 x4 0 Y x +x5
1 .x2+ x3.x + x1 0
2 X4 0 x3 + x5.x2 + x6.x + x3 0
3 x4 x4 a2 N x+x2x+x1 x + x3 x3+x5.x2+ x1x V x5

where Q''(x:) is the formal derivative of Q(x) (see Section 7.4). In this case Q'(x) = a2.
Therefore the error value at location 5 is e5 — a5(a5 + a3)/a2 = a5. The received
information is therefore corrected to a5 a° a5.
The application of the Welch-Berlekamp algorithm to GMD is that, for a Reed
Solomon code, any n - k symbols can be treated as parity checks. The least reliable
n — k symbols are therefore treated as parity checks with the syndromes derived by
recomputing the codeword from the most reliable symbols. As we enter the syn-
dromes into the algorithm, each time a new pair of values of Q and N is produced we
carry out the correction and produce a new codeword for consideration.

7.12 SINGLY EXTENDED REED SOLOMON CODES

It is possible to create a q-ary Reed Solomon code of length q, and such a code is known
as an extended code. The code will still correct t = (n - k)/2 symbols and can be
thought of either as adding a parity symbol to a code which corrects / - 1 errors and
detects t (expansion), or as adding an extra information symbol to a t-error correcting
code. The extended code is not cyclic, but can be encoded and decoded using frequency
domain techniques. The properties of such a code are relatively easy to understand and
the logic of the decoding approach is effectively the proof of the properties.
To create a /-error correcting RS code of length q, we first create the code of length
q — 1 with 2t — 1 parity checks. The frequency domain syndrome components S0 to
S2t-2 will, by definition, be zero. We now choose an adjacent position in the frequency
domain, known as the edge frequency, work out the value of Fourier transform in
that position and append it to the sequence. This is shown in Figure 7.9 on the
assumption that the edge frequency corresponds to S2t-1 • The extra symbol is known
as the edge symbol.
In the frequency domain, a codeword can be created as shown in Figure 7.10. Here
one of the information symbols acts as the edge symbol.
To decode, we calculate 2t components of the frequency domain syndrome of the
length q - 1 sequence. We use 2t — 2 syndrome components to create a connection
polynomial of degree up to t - 1. If there are no more than t - 1 errors in the length
q — 1 sequence then the final syndrome component s2t-2 will show that there are no

information symbols 2t-\ parity symbols

Figure 7.9 Singly extended Reed Solomon code

 REED SOLOMON CODES 171

i to /, | i0 | 2t-1zeros
Inverse Fourier transform

length q-\ code

Figure 7.10 Frequency domain view of singly extended Reed Solomon code

more errors detected and correction can proceed. If there are t errors in the length
q — 1 sequence then they will be detected by s2t-2; however, in this case we can
assume that the received value of S2t-t is correct (otherwise there would be more
than t errors in the whole codeword). We therefore add the received value of S2t-1 to
the calculated value to produce a usable value for t-error correction.
The choice of edge frequency from the two available is unimportant for the
properties of the code. However, assuming that the Berlekamp-Massey algorithm
is used for decoding, the choice of st-2 will be convenient as the connection polyno-
mial can, if necessary, be calculated as an extension of the results up to S2l-2. The
location of the edge symbol in the final codeword is entirely arbitrary.

Examples of singly extended code

To create a single-error correcting double-error detecting RS code of length 7 over

GF(8), we can use

g(X) = (X + a0)(JT + a1)(X + a2) = X3 + a5X2 + a6X + a3

The information a5 a° a5 a2 encodes systematically to a5 a° a5 a2 0 a2 a°. The

Fourier transform in position 3 is

.53 = a5 a4 + aV + ocV + ora2 4- ocV + a° = a6

The codeword is therefore a6 a5 a° a5 a2 0 a2 a°.

Now create errors in positions 7 and 5, the received sequence being a2 a5 a4
a a 0 a2 a°. The syndrome polynomial of the sequence a5 a4 a5 a2 0 a2 a° is
5 2

and the syndrome in position 4 is zero. Attempting single-error correction yields a

connection polynomial of oc5z + 1 and the syndrome component in position 2 is
correctly predicted. The symbol in position 7 is therefore not needed and can be
discarded. The error value is the value of S0, i.e. a5, so the received word of the (7, 4)
code can be corrected to a5 a0 a5 a2 0 a2 a0, with the first four symbols being the
information.
Alternatively, create errors in positions 5 and 3, the received sequence being
a1 a5 a4 a5 a1 0 a2 a°. The syndrome of a5 a4 a5
172 ERROR CONTROL CODING

with the value in position 3 being a6. The single-error correcting connection polyno-
mial is O1Z + 1, but this does not correctly predict the next component. We therefore
assume that the edge frequency a6 was correct and add it to the calculated 53 value to
give a syndrome for a double-error correcting code

The key equation for double error correction is

a°A1 + a 1 A 2 = 0

Eliminating A2 gives a1 + a6A1 = 0, AI = a2, A2 = a1 . As in Section 7.5, the roots are

a2 and a4 indicating errors in positions 5 and 3. The error values may be found using
the Forney algorithm.

7. 1 3 DOUBLY EXTENDED REED SOLOMON CODES

The single extension of RS codes can be taken one stage further to create a code of
length q + 1. A t — 1 -error correcting code is created, two edge frequencies selected
and the Fourier transform calculated for those two frequencies to create the two edge
symbols. The decoding process is slightly more complicated than for the singly
extended code. The logic, assuming that no more than t errors have occurred is as
follows:
If both the edge symbols are incorrect then no more than t — 2 errors need be
corrected in the length q — 1 codeword. This can be achieved from the normal parity
symbols with two more parities available to check the correctness of the process.
Therefore if correction of up to t — 2 errors appears to be successful (as verified by
the remaining parity checks), accept the result.
If one edge symbol is incorrect then no more than t — 1 errors need be corrected in
the length q — 1 codeword. This can be achieved from the normal parity symbols.
Therefore if correction of up to t — 1 errors appears to be successful, verify this by
calculating the two edge symbols and checking that at least one of them corresponds
to what was received. If this condition is satisfied then accept the result.
For r-error correction to be needed in the length q — 1 codeword, both edge
symbols must be correct. Therefore if decoding has so far been unsuccessful, assume
that both edge symbols are correct and add them to the received sequence Fourier
transform values at the corresponding edge frequencies. Use the results as two more
syndrome components to achieve t-error correction.
Again the edge frequencies could be chosen at either end of the syndrome frequen-
cies, or even one at each end. However, if the syndromes are S0 to s2i-3, choosing J2/-2
and S2t-1 as the edge symbols will again fit conveniently with the operation of the
Berlekamp-Massey algorithm.
To make the point that extended codes can be viewed as adding information
symbols to a t-error correcting code and that other positions can be chosen for the
 REED SOLOMON CODES 173

edge frequencies, consider a doubly extended RS code whose frequency domain

view is shown in Figure 7.11. The process of encoding is as follows. Put k — 2
( — q - 1 - 2t} information symbols and 2t consecutive zeros into a vector of length
q - 1. Put the two remaining information symbols into the two outside zero pos-
itions, one at the low-order end and one at the high-order end. We now have the
spectrum of a t - 1 error-correcting Reed Solomon code. The vector of length q - 1
is given an inverse Fourier transform over GF(q) to produce a Reed Solomon code-
word which can correct t - 1 errors. The high-order edge frequency is appended at
the beginning (high-order end) of the codeword and the low-order edge frequency at
the (low-order) end of the codeword. The codeword is now of length q + 1.
To decode a received sequence using the extended code, strip the symbols from the
beginning and end and forward transform the remaining sequence of length q - 1.
The syndrome consists of the high-order edge frequency plus the stripped symbol
received in the high-order position, the subsequent 2t - 2 symbol values and the sum
of the low-order edge frequency plus the stripped symbol received in the low-order
position. This is shown in Figure 7.12. Decoding, however, starts off with an attempt
at t - 1 error correction, using only the central 2t — 2 symbols of the syndrome
following the logic outlined previously.

k-2 information symbols 2?-2 zeros) low-order

high-order edge symbol
edge symbol
q~\ point inverse
Fourier transform

q + ! symbol codeword

Figure 7.11 Encoding of doubly extended Reed Solomon code

q+1 symbols
high-order
edge symbol 1 low-order
edge symbol

<y-l point Fourier transform

t^
1 ^\^ 1 1

It symbols syndrome

Figure 7.12 Syndrome formation for doubly extended Reed Solomon code
174 ERROR CONTROL CODING

Example of doubly extended code

We consider the case of a (9, 5) Reed Solomon code over GF(8). In this case we have
a 5 symbol information sequence 1 a3 a a6 a2. We treat the first and last of these as
edge symbols, placing them in positions 3 and 0, respectively, in the frequency
domain. Thus we start from the spectrum of a single-error correcting Reed Solomon
code

C(z) = a3z6 + az5 + a6z4 + z3 -I- a2

The inverse transform gives the codeword of a (7, 5) RS code:

c(X) = a6 A-6 + a2 A-5 + a3*4 + a6*3 + X2 + a3* + 1

The two extra information symbols are now added to the ends of the codeword to
produce the (9, 5) RS codeword

c'(X) = Xs + a6 A-7 + a2 A* + a3*5 + a6*4 + X3 + a?X2 + X + a2

Now assume that errors occur at positions 8 and 5 producing a received sequence

i*(X) = a3 A'8 + a6 A'7 + a2 A* + a5 A'5 + a6 A'4 + A'3 + a3 A'2 + X + a2

The additional symbols are stripped from the sequence to give

c(X) = a6 A* + a2 A'5 + a5 A'4 + a6 A'3 + A'2 + a3* + 1

which transforms to

R(z) = tx2z6 + a3z4 + aV + a6z

The terms of order 3 downwards are extracted as the syndrome, with the add-
itional symbols added at the appropriate points, giving

R(z) = z3 + aV + a6z + a2

The terms in the syndrome are incrementing by multiples of a4 as the order

increases, indicating the equivalence of a single error with the key equation solving
as A1 = a4. The spectrum of the error sequence is therefore

E(z) = a5z6 + az5 + a4z4 + z3 + aV + a6z + a2

which, when added to R(z) gives

C(z) = a3z6 + az5 + a6z4 + z3 + a2

 REED SOLOMON CODES 175

Decoding has been correctly achieved and all the information is directly available
from C(z).

7.14 CONCLUSION

Reed Solomon codes are arguably the most elegant and most useful product of
algebraic coding theory. The origin and the discovery of their relation to BCH
codes were mentioned in Chapter 6. The implementations of algorithms mentioned
in that chapter, and of finite field arithmetic from Chapter 5 are also highly relevant.
The Welch-Berlekamp algorithm was originally embodied in a US patent [2]. The
anticipated expiry of that patent gave rise to considerable interest and the publication
of several papers describing it and its uses, of which [3] describes its application to
GMD decoding. A similar method described in [4] includes a method to keep track of
the results of the Chien search to assist the multiple decoding attempts. Some
applications of Reed Solomon codes will be discussed in Chapters 9 and 10.

7.15 EXERCISES

1 Find the generator polynomial of the double-error-correcting RS code of length 7

whose Fourier transform has zeros in positions 0, 1, 2 and 3, assuming that GF(8)
is generated by X3 + X2 + 1. Find the syndrome of the sequence a2 a4 0 a6
a6 a5 a6 by long division and by computation of the appropriate Fourier trans-
form components.

2 Using the (7, 3) RS code example of question 1, carry out the decoding if the
errors are
e(X} = a5^4 + a2+X2
using Euclid's algorithm for solution of the key equation.

3 Using the RS code of the above question, show the decoding with a single error
affecting all bits in position 4.

4 In the example (7, 3) Reed Solomon code of Section 4.16, erase the transmitted
symbols at positions 6, 5, 3 and 0. Carry out the decoding.

5 Encode the 8-ary information sequence a2 0 a6 1 a into a (9, 5) extended Reed

Solomon code. Carry out the decoding if errors are introduced as follows:
1 in position 8 and a in position 0
a2 in position 7 and a3 in position 2