We have shown that an code can correct errors if . Hence, we would like the minimum distance to be large so that we can correct as many errors as possible. But we also would like for to be large so that the code rate will be as close to as possible. This would allow us to use bandwidth efficiently when transmitting messages over noisy channels. Unfortunately, increasing tends to increase or decrease .
In this section, we study the restrictions on , , and without worrying about practical aspects such as whether the codes with good parameters have efficient decoding algorithms. It is still useful to have results such as the ones we’ll discuss since they give us some idea of how good an actual code is, compared to the theoretical limits.
First, we treat upper bounds for in terms of and . Then we show that there exist codes with larger than certain lower bounds. Finally, we see how some of our examples compare with these bounds.
Our first result was given by R. Singleton in 1964 and is known as the Singleton bound.
Let be a -ary code. Then
Proof. For a codeword , let . If are two codewords, then they differ in at least places. Since and are obtained by removing entries from and , they must differ in at least one place, so . Therefore, the number of codewords equals the number of vectors obtained in this way. There are at most vectors since there are positions in these vectors. This implies that , as desired.
The code rate of a -ary code is at most .
Proof. The corollary follows immediately from the definition of code rate.
The corollary implies that if the relative minimum distance is large, the code rate is forced to be small.
A code that satisfies the Singleton bound with equality is called an MDS code (maximum distance separable). The Singleton bound can be rewritten as , so an MDS code has the largest possible value of for a given and . The Reed-Solomon codes (Section 24.9) are an important class of MDS codes.
Before deriving another upper bound, we need to introduce a geometric interpretation that is useful in error correction. A Hamming sphere of radius centered at a codeword is denoted by and is defined to be all vectors that are at most a Hamming distance of from the codeword . That is, a vector belongs to the Hamming sphere if . We calculate the number of vectors in in the following lemma.
A sphere in -dimensional -ary space has
elements.
Proof. First we calculate the number of vectors that are a distance from . These vectors are the ones that differ from in exactly one location. There are possible locations and ways to make an entry different. Thus the number of vectors that have a Hamming distance of from is . Now let’s calculate the number of vectors that have Hamming distance from . There are ways in which we can choose locations to differ from the values of . For each of these locations, there are choices for symbols different from the corresponding symbol from . Hence, there are
vectors that have a Hamming distance of from . Including the vector itself, and using the identity , we get the result:
We may now state the Hamming bound, which is also called the sphere packing bound.
Let be a -ary code with . Then
Proof. Around each codeword we place a Hamming sphere of radius . Since the minimum distance of the code is , these spheres do not overlap. The total number of vectors in all of the Hamming spheres cannot be greater than . Thus, we get
This yields the desired inequality for .
An code with that satisfies the Hamming bound with equality is called a perfect code. A perfect -error correcting code is one such that the Hamming spheres of radius with centers at the codewords cover the entire space of -ary -tuples. The Hamming codes (Section 24.5) and the Golay code (Section 24.6) are perfect. Other examples of perfect codes are the trivial code obtained by taking all -tuples, and the binary repetition codes of odd length (Exercise 15).
Perfect codes have been studied a lot, and they are interesting from many viewpoints. The complete list of perfect codes is now known. It includes the preceding examples, plus a ternary code constructed by Golay. We leave the reader a caveat. A name like perfect codes might lead one to assume that perfect codes are the best error correcting codes. This, however, is not true, as there are error correcting codes, such as Reed-Solomon codes, that are not perfect codes yet have better error correcting capabilities for certain situations than perfect codes.
One of the problems central to the theory of error correcting codes is to find the largest code of a given length and given minimum distance . This leads to the following definition.
Let the alphabet have elements. Given and with , the largest such that an code exists is denoted .
We can always find at least one code: Fix an element of . Let be the set of all vectors (with copies of and copies of ) with . There are such vectors, and they are at distance from each other, so we have an code. This gives the trivial lower bound . We’ll obtain much better bounds later.
It is easy to see that : When a code has minimum distance , we can take the code to be all -ary -tuples. At the other extreme, (Exercise 7).
The following lower bound, known as the Gilbert-Varshamov bound, was discovered in the 1950s.
Given with , there exists a -ary code with
This means that
Proof. Start with a vector and remove all vectors in (where is an alphabet with symbols) that are in a Hamming sphere of radius about that vector. Now choose another vector from those that remain. Since all vectors with distance at most from have been removed, . Now remove all vectors that have distance at most from , and choose from those that remain. We cannot have or , since all vectors satisfying these inequalities have been removed. Therefore, for . Continuing in this way, choose , until there are no more vectors.
The selection of a vector removes at most
vectors from the space. If we have chosen vectors , then we have removed at most
vectors, by the preceding lemma. We can continue until all vectors are removed, which means we can continue at least until
Therefore, there exists a code with satisfying the preceding inequality.
Since is the largest such , it also satisfies the inequality.
There is one minor technicality that should be mentioned. We actually have constructed an code with . However, by modifying a few entries of if necessary, we can arrange that . The remaining vectors are then chosen by the above procedure. This produces a code where the minimal distance is exactly .
If we want to send codewords with bits over a noisy channel, and there is a probability that any given bit will be corrupted, then we expect the number of errors to be approximately when is large. Therefore, we need an code with . We therefore need to consider codes with , for some given . How does this affect and the code rate?
Here is what happens. Fix and choose with . The asymptotic Gilbert-Varshamov bound says that there is a sequence of -ary codes with and such that the code rate approaches a limit , where
The graph of is as in Figure 24.2. Of course, we would like to have codes with high error correction (that is, high ), and with high code rate (). The asymptotic result says that there are codes with error correction and code rate good enough to lie arbitrarily close to, or above, the graph.
The existence of certain sequences of codes having code rate limit strictly larger than (for certain and ) was proved in 1982 by Tsfasman, Vladut, and Zink using Goppa codes arising from algebraic geometry.
Consider the binary repetition code of length with the two vectors and . It is a code. The Singleton bound says that , so is an MDS code. The Hamming bound says that
so is also perfect. The Gilbert-Varshamov bound says that there exists a binary code with
which means .
The Hamming code has and , so it is a code. The Singleton bound says that , so it is not an MDS code. The Hamming bound says that
so the code is perfect. The Gilbert-Varshamov bound says that there exists a code with
so the Hamming code is much better than this lower bound. Codes that have efficient error correction algorithms and also exceed the Gilbert-Varshamov bound are currently relatively rare.
The Hadamard code from Section 24.1 is a binary (because there are two symbols) code. The Singleton bound says that , so it is not very sharp in this case. The Hamming bound says that
The Gilbert-Varshamov bound says there exists a binary code with