2
Algebraic Coding Theory
In this chapter we will introduce the basic concepts of algebraic coding theory. To this end,
the fundamental properties of block codes are first discussed. We will define important code
parameters and describe how these codes can be used for the purpose of error detection
and error correction. The optimal maximum likelihood decoding strategy will be derived
and applied to the binary symmetric channel.
With these fundamentals at hand we will then introduce linear block codes. These
channel codes can be generated with the help of so-called generator matrices owing to
their special algebraic properties. Based on the closely related parity-check matrix and the
syndrome, the decoding of linear block codes can be carried out. We will also introduce
dual codes and several techniques for the construction of new block codes based on known
ones, as well as bounds for the respective code parameters and the accompanying code
characteristics. As examples of linear block codes we will treat the repetition code, parity-
check code, Hamming code, simplex code and Reed– Muller code.
Although code generation can be carried out efficiently for linear block codes, the
decoding problem for general linear block codes is difficult to solve. By introducing further
algebraic structures, cyclic codes can be derived as a subclass of linear block codes for
which efficient algebraic decoding algorithms exist. Similar to general linear block codes,
which are defined using the generator matrix or the parity-check matrix, cyclic codes
are defined with the help of the so-called generator polynomial or parity-check polynomial.
Based on linear feedback shift registers, the respective encoding and decoding architectures
for cyclic codes can be efficiently implemented. As important examples of cyclic codes
we will discuss BCH codes and Reed–Solomon codes. Furthermore, an algebraic decoding
algorithm is presented that can be used for the decoding of BCH and Reed–Solomon
codes.
In this chapter the classical algebraic coding theory is presented. In particular, we
will follow work (Berlekamp, 1984; Bossert, 1999; Hamming, 1986; Jungnickel, 1995;
Lin and Costello, 2004; Ling and Xing, 2004; MacWilliams and Sloane, 1998; McEliece,
2002; Neubauer, 2006b; van Lint, 1999) that contains further details about algebraic coding
theory.
Coding Theory – Algorithms, Architectures, and Applications Andr
´
e Neubauer, J
¨
urgen Freudenberger, Volker K
¨
uhn
2007 John Wiley & Sons, Ltd