Overview

For an ( n, M, d)-code C over F _q, theoretically we would like both ( C) = (log _q M)/ n and ?( C) = ( d ? 1)/ n to be as large as possible. In other words, we want M to be as large as possible for fixed n and d. Of course, the ideal situation is to find codes with size equal to A _q( n, d) for all given q, n and d. However, from the previous chapter, we know that it is still an open problem that seems difficult to solve. Fortunately, in practice, we are contented to use codes with sizes close to A _q( n, d). In order to do so, we have to find ways to construct such codes.

The construction of good codes has almost as long a history as coding theory itself. The Hamming codes in the previous chapter are one of the earliest classes of codes. Later on, many other codes which are also in practical use were invented: for instance, Reed Muller codes (see Section 6.2); BCH codes (Section 8.1); Reed Solomon codes (Section 8.2); and Goppa codes (Section 9.3).

In this chapter, we concentrate mainly on the construction of linear codes. For the construction of nonlinear codes, the reader is advised to refer to ref. [13] and the following webpage maintained by Simon Litsyn of Tel Aviv University,...