When you are having a conversation with a friend over a cellular phone, your voice is turned into digital data that has an error correcting code applied to it before it is sent. When your friend receives the data, the errors in transmission must be accounted for by decoding the error correcting code. Only after decoding are the data turned into sound that represents your voice.

The amount of delay it takes for a packet of data to be decoded is critical in such an application. If it took several seconds, then the delay would become aggravating and make holding a conversation difficult.

The problem of efficiently decoding a code is therefore of critical importance. In order to decode quickly, it is helpful to have some structure in the code rather than taking the code to be a random subset of $A^n$. This is one of the primary reasons for studying linear codes. For the remainder of this chapter, we restrict our attention to linear codes.

Henceforth, the alphabet $A$ will be a finite field $\mathbf{F}$. For an introduction to finite fields, see Section 3.11. For much of what we do, the reader can assume that $\mathbf{F}$ is ${\mathbf{Z}}_2=\{0\text{,}1\}$ = the integers mod 2, in which case we are working with binary vectors. Another concrete example of a finite field is ${\mathbf{Z}}_p$ = the integers mod a prime $p$. For other examples, see Section 3.11. In particular, as is pointed out there, $\mathbf{F}$ must be one of the finite fields $GF(q)$; but the present notation is more compact. Since we are working with arbitrary finite fields, we’ll use “=" instead of “$\equiv$" in our equations. If you want to think of $\mathbf{F}$ as being ${\mathbf{Z}}_2$, just replace all equalities between elements of $\mathbf{F}$ with congruences mod 2.

The set of $n$-dimensional vectors with entries in $\mathbf{F}$ is denoted by ${\mathbf{F}}^n$. They form a vector space over $\mathbf{F}$. Recall that a subspace of ${\mathbf{F}}^n$ is a nonempty subset $S$ that is closed under linear combinations, which means that if $s_1\text{,}{s}_2$ are in $S$ and $a_1\text{,}{a}_2$ are in $\mathbf{F}$, then $a_1{s}_1+a_2{s}_2\in S$. By taking $a_1=a_2=0$, for example, we see that $(0\text{,}0\text{,}\text{,}\dots \text{,}0)\in S$.

When $\mathbf{F}={\mathbf{Z}}_2$, the definition can be given more simply. A binary code of length $n$ and dimension $k$ is a set of $2^k$ binary $n$-tuples (the codewords) such that the sum of any two codewords is always a codeword.

Many of the codes we have met are linear codes. For example, the binary repetition code $\{(0\text{,}0\text{,}0)\text{,}(1\text{,}1\text{,}1)\}$ is a one-dimensional subspace of ${\mathbf{Z}}_2^3$. The parity check code from Exercise 2 in Section 24.1 is a linear code of dimension 7 and length 8. It consists of those binary vectors of length 8 such that the sum of the entries is 0 mod 2. It is not hard to show that the set of such vectors forms a subspace. The vectors

form a basis of this subspace. Since there are seven basis vectors, the subspace is seven-dimensional.

The Hamming [7, 4] code from Example 4 of Section 24.1 is a linear code of dimension 4 and length 7. Every codeword is a linear combination of the four rows of the matrix $G$. Since these four rows span the code and are linearly independent, they form a basis.

The ISBN code (Example 5 of Section 24.1) is not linear. It consists of a set of 10-dimensional vectors with entries in ${\mathbf{Z}}_{11}$. However, it is not closed under linear combinations since $X$ is not allowed as one of the first nine entries.

Let $C$ be a linear code of dimension $k$ over a field $\mathbf{F}$. If $\mathbf{F}$ has $q$ elements, then $C$ has $q^k$ elements. This may be seen as follows. There is a basis of $C$ with $k$ elements; call them $v_1\text{,}\dots \text{,}{v}_k$. Every element of $C$ can be written uniquely in the form $a_1{v}_1+\cdots +a_k{v}_k$, with $a_1\text{,}\dots \text{,}{a}_k\in \mathbf{F}$. There are $q$ choices for each $a_i$ and there are $k$ numbers $a_i$. This means there are $q^k$ elements of $C$, as claimed. Therefore, an $[n\text{,}k\text{,}d]$ linear code is an $(n\text{,}{q}^k\text{,}d)$ code in the notation of Section 24.2.

For an arbitrary, possibly nonlinear, code, computing the minimum distance could require computing $d(u\text{,}v)$ for every pair of codewords. For a linear code, the computation is much easier. Define the Hamming weight $wt(u)$ of a vector $u$ to be the number of nonzero places in $u$. It equals $d(u\text{,}0)$, where 0 denotes the vector $(0\text{,}0\text{,}\dots \text{,}0)$.

To construct a linear $[n\text{,}k]$ code, we have to construct a $k$-dimensional subspace of ${\mathbf{F}}^n$. The easiest way to do this is to choose $k$ linearly independent vectors and take their span. This can be done by choosing a $k\times n$ generating matrix $G$ of rank $k$, with entries in $\mathbf{F}$. The set of vectors of the form $vG$, where $v$ runs through all row vectors in ${\mathbf{F}}^k$, then gives the subspace.

For our purposes, we’ll usually take $G=[I_k\text{,}P]$, where $I_k$ is the $k\times k$ identity matrix and $P$ is a $k\times (n-k)$ matrix. The rows of $G$ are the basis for a $k$-dimensional subspace of the space of all vectors of length $n$. This subspace is our linear code $C$. In other words, every codeword is uniquely expressible as a linear combination of rows of $G$. If we use a matrix $G=[I_k\text{,}P]$ to construct a code, the first $k$ columns determine the codewords. The remaining $n-k$ columns provide the redundancy.

The code in the second half of Example 1, Section 24.1, has

The codewords 101010 and 010101 appear as rows in the matrix and the codeword 111111 is the sum of these two rows. This is a $[6\text{,}2]$ code.

The code in Example 2 has

For example, the codeword 11001001 is the sum mod 2 of the first, second, and fifth rows, and hence is obtained by multiplying $(1\text{,}1\text{,}0\text{,}0\text{,}1\text{,}0\text{,}0)$ times $G$. This is an $[8\text{,}7]$ code.

In Exercise 4, the matrix $G$ is given in the description of the code. As you can guess from its name, it is a $[7\text{,}4]$ code.

As mentioned previously, we could start with any $k\times n$ matrix of rank $k$. Its rows would generate an $[n\text{,}k]$ code. However, row and column operations can be used to transform the matrix to the form of $G$ we are using, so we usually do not work with the more general situation. A code described by a matrix $G=[I_k\text{,}P]$ as before is said to be systematic. In this case, the first $k$ bits are the information symbols and the last $n-k$ symbols are the check symbols.

Suppose we have $G=[I_k\text{,}P]$ as the generating matrix for a code $C$. Let

where $P^T$ is the transpose of $P$. In Exercise 4 of Section 24.1, this is the matrix that was used to correct errors. For Exercise 2, we have $H=[1\text{,}1\text{,}1\text{,}1\text{,}1\text{,}1\text{,}1\text{,}1]$. Note that in this case a binary string $v$ is a codeword if and only if the number of nonzero bits is even, which is the same as saying that its dot product with $H$ is zero. This can be rewritten as $v{H}^T=0$, where $H^T$ is the transpose of $H$.

More generally, suppose we have a linear code $C\subset {\mathbf{F}}^n$. A matrix $H$ is called a parity check matrix for $C$ if $H$ has the property that a vector $v\in {\mathbf{F}}^n$ is in $C$ if and only if $v{H}^T=0$. We have the following useful result.

We now have a way of detecting errors: If $v$ is received during a transmission and $v{H}^T\ne 0$, then there is an error. If $v{H}^T=0$, we cannot conclude that there is no error, but we do know that $v$ is a codeword. Since it is more likely that no errors occurred than enough errors occurred to change one codeword into another codeword, the best guess is that an error did not occur.

We can also use a parity check matrix to make the task of decoding easier. First, let’s look at an example.

We now consider the general situation. The method of the example leads us to two definitions.

It is easy to see that if $v\in u+C$, then the sets $v+C$ and $u+C$ are the same (Exercise 9).

The syndrome of a vector $u$ is defined to be $S(u)=u{H}^T$. The following lemma allows us to determine the cosets easily.

Decoding can be achieved by building a syndrome lookup table, which consists of the coset leaders and their corresponding syndromes. With a syndrome lookup table, we can decode with the following steps:

1. For a received vector $r$, calculate its syndrome $S(r)={rH}^T$.

2. Next, find the coset leader with the same syndrome as $S(r)$. Call the coset leader $c_0$.

3. Decode $r$ as $r-c_0$.

Syndrome decoding requires significantly fewer steps than searching for the nearest codeword to a received vector. However, for large codes it is still too inefficient to be practical. In general, the problem of finding the nearest neighbor in a general linear code is hard; in fact, it is what is known as an NP-complete problem. However, for certain special types of codes, efficient decoding is possible. We treat some examples in the next few sections.