ALGEBRAIC CODING THEORY 81
Owing to the roots α and α
2
there exist δ − 1 = 2 successive roots. According to the BCH
bound, the minimum Hamming distance is bounded below by d ≥ δ = 3. In fact, as we
already know, Hamming codes have a minimum Hamming distance d = 3.
In general, for the definition of a cyclic BCH code we prescribe δ − 1 successive zeros
α
β
, α
β+1
, α
β+2
, ..., α
β+δ−2
. By adding the corresponding conjugate roots, we obtain the
generator polynomial g(z) which can be written as
g(z) = lcm
m
β
(z), m
β+1
(z), . . . , m
β+δ−2
(z)
.
The generator polynomial g(z) is equal to the least common multiple of the respective
polynomials m
i
(z) which denote the minimal polynomials for α
i
with β ≤ i ≤ β + δ − 2.
2.3.7 Reed–Solomon Codes
As an important special case of primitive BCH codes we now consider BCH codes over
the finite field F
q
with code word length
n = q − 1.
These codes are called Reed–Solomon codes (Berlekamp, 1984; Bossert, 1999; Lin and
Costello, 2004; Ling and Xing, 2004); they are used in a wide range of applications ranging
from communication systems to the encoding of audio data in a compact disc (Costello
et al., 1998). Because of α
n
= α
q−1
= 1, the nth root of unity α is an element of the finite
field F
q
. Since the corresponding minimal polynomial of α
i
over the finite field F
q
is
simply given by
m
i
(z) = z − α
i
the generator polynomial g(z) of such a primitive BCH code to the design distance δ is
g(z) = (z − α
β
)(z− α
β+1
) ···(z − α
β+δ−2
).
The degree of the generator polynomial is equal to
deg(g(z)) = n − k = δ − 1.
Because of the BCH bound, the minimum Hamming distance is bounded below by d ≥ δ =
n − k + 1 whereas the Singleton bound delivers the upper bound d ≤ n − k + 1. Therefore,
the minimum Hamming distance of a Reed–Solomon code is given by
d = n − k + 1 = q − k.
Since the Singleton bound is fulfilled with equality, a Reed–Solomon code is an MDS
(maximum distance separable) code. In general, a Reed–Solomon code over the finite field
F
q
is characterised by the following code parameters
n = q − 1,
k = q −δ,
d = δ.
In Figure 2.52 the characteristics of a Reed–Solomon code are summarised. For practically
relevant code word lengths n, the cardinality q of the finite field F
q
is large. In practical
applications q = 2
l
is usually chosen. The respective elements of the finite field F
2
l
are
then represented as l-dimensional binary vectors over F
2
.