ALGEBRAIC CODING THEORY 37
Because of the close relationship between B(n,k,d) and its dual B
⊥
(n
,k
,d
),wecan
derive the properties of the dual code B
⊥
(n
,k
,d
) from the properties of the original
code B(n,k,d). In particular, the MacWilliams identity holds for the corresponding weight
distributions W
⊥
(x) and W(x) (Bossert, 1999; Lin and Costello, 2004; Ling and Xing,
2004; MacWilliams and Sloane, 1998). The MacWilliams identity states that
W
⊥
(x) = q
−k
(
1 + (q − 1)x
)
n
W
1 − x
1 + (q − 1)x
.
For linear binary block codes with q = 2 we obtain
W
⊥
(x) = 2
−k
(1 + x)
n
W
1 − x
1 + x
.
The MacWilliams identity can, for example, be used to determine the minimum Hamming
distance d
of the dual code B
⊥
(n
,k
,d
) on the basis of the known weight distribution
of the original code B(n,k,d).
2.2.6 Bounds for Linear Block Codes
The code rate R = k/n and the minimum Hamming distance d are important parameters
of a linear block code B(n,k,d). It is therefore useful to know whether a linear block code
theoretically exists for a given combination of R and d. In particular, for a given minimum
Hamming distance d we will consider a linear block code to be better than another linear
block code with the same minimum Hamming distance d if it has a higher code rate R. There
exist several theoretical bounds which we will briefly discuss in the following (Berlekamp,
1984; Bossert, 1999; Ling and Xing, 2004; van Lint, 1999) (see also Figure 2.22). Block
codes that fulfil a theoretical bound with equality are called optimal codes.
Singleton Bound
The simplest bound is the so-called Singleton bound. For a linear block code B(n,k,d) it
is given by
k ≤ n − d +1.
A linear block code that fulfils the Singleton bound with equality according to k = n − d +
1 is called MDS (maximum distance separable). Important representatives of MDS codes
are Reed–Solomon codes which are used, for example, in the channel coding scheme
within the audio compact disc (see also Section 2.3.7).
Sphere Packing Bound
The so-called sphere packing bound or Hamming bound can be derived for a linear e
cor
=
(d − 1)/2-error correcting q-nary block code B(n,k,d) by considering the correction
balls within the code space F
n
q
. Each correction ball encompasses a total of
e
cor
i=0
n
i
(q − 1)
i