Chapter 8 - Algebraic Coding Theory

Summary

One of the major applications of finite fields is coding theory. This theory has its origin in a famous theorem of Shannon that guarantees the existence of codes that can transmit information at rates close to the capacity of a communication channel with an arbitrarily small probability of error. One purpose of algebraic coding theory—the theory of error-correcting and errordetecting codes—is to devise methods for the construction of such codes.

During the last two decades more and more abstract algebraic tools such as the theory of finite fields and the theory of polynomials over finite fields have influenced coding. In particular, the description of redundant codes by polynomials over F_q is a milestone in this development. The fact that one can use shift registers for coding and decoding establishes a connection with linear recurring sequences. In our discussion of algebraic coding theory we do not consider any of the problems of the implementation or technical realization of the codes. We restrict ourselves to the study of basic properties of block codes and the description of some interesting classes of block codes.

Section 1 contains some background on algebraic coding theory and discusses the important class of linear codes in which encoding is performed by a linear transformation. A particularly interesting type of linear code is a cyclic code—that is, a linear code invariant under cyclic shifts.