How many codewords can fit?
A minimum-distance requirement separates codewords, but it is not obvious how many can be chosen. We will prove a lower bound by building a code and an upper bound by packing disjoint balls. These bounds need not coincide.
Definition 13.1.1
(Hamming distance and ball volume)
Let be an alphabet of symbols, , and , with all three integers. The Hamming distance between two length- words is the number of differing coordinates. A code is a set of words; it need not be linear, and need not be a prime power. Write
This is the number of words within distance of a fixed word: choose coordinates and one of alternatives at each. It is independent of the center.
A greedy existence bound
Theorem 13.1.2
(Greedy covering bound)
There exists a code with pairwise distance at least and
This is the finite greedy Gilbert–Varshamov bound.
Proof
(Greedy selection until the space is covered)
Begin with every word available. Choose any available word, add it to , and remove all words within distance of it. Repeat until no word remains. The process terminates because the finite available set loses at least the chosen word each time. Every later chosen word lies outside the earlier chosen word's radius- ball, so selected words are pairwise at distance at least .
At termination, the radius- balls around the selected words cover all words. They may overlap, so the union has size at most the sum of their sizes. Consequently , which gives the stated ceiling. Since , the ball is smaller than the whole space, so the bound supplies at least two codewords.
Proof X-ray
Covering is not packing
Finiteness is used only for termination: each round removes at least the chosen word from a finite set. Separation comes from the removal rule, since every word within distance of a chosen word is deleted before the next choice. The key move is the stopping condition read backwards: nothing is available, so the radius- balls around the chosen words cover all of .
The argument closes with a union bound, which tolerates overlaps; this is why the inequality points the right way for a lower bound on . The radius here is , not the error-correction radius, and the balls need not be disjoint. The packing bound below uses the opposite kind of counting.
The packing upper bound
Theorem 13.1.3
(Hamming packing bound)
Let . Every code with pairwise distance at least satisfies
Proof
(Disjoint balls of radius t)
Radius- balls around the codewords are disjoint: a shared word would, by the triangle inequality, put two distinct codewords at distance at most . All these balls lie in , so . Since is an integer, the floor may be taken.
The bounds use radii and , respectively, and make different claims: the first constructs some code with a minimum size, whereas the second limits every code with the specified separation. In general these bounds need not determine the largest possible code; if they coincide, they do.
Worked example 13.1.4
(Five binary positions, distance three)
For , , , the greedy ball volume is . The theorem guarantees at least words. The packing radius is and , so every such code has at most words.
The four words give a concrete code of minimum distance three: their nonzero weights are , and their three pairwise differences among the last three words have weights . This construction improves the lower bound for this example; it does not by itself rule out a five-word code.
Counterexample mode
Maximal does not mean maximum
The greedy algorithm stops at an inclusion-maximal code: no further word can be added without violating the distance requirement. That property does not automatically prove that its number of codewords is the largest possible among all codes. In the binary example, choosing then already covers every word within distance two of one of them: each word has weight at most two or at least three. This maximal code has two words, while the four-word code above is larger. The covering argument guarantees a size bound without making an optimality claim.
Worked example 13.1.5
(A ternary code where the bounds meet)
Take , , . The greedy volume is , so some code has at least words. The packing radius is with , so every code has at most words. The code has all pairwise distances equal to three and therefore attains the upper bound: the largest ternary code of length three and minimum distance three has exactly three words. Here the alphabet is used only as a set of symbols; no field structure is needed.
Worked example 13.1.6
(Distance equal to the length)
At the extreme , take , , . A ball of radius misses only the complement of its center, so and the greedy bound gives at least words. With , and the packing bound gives at most . The repetition code meets both bounds, so it is optimal; indeed, any two binary words at distance five are complements, and a third word cannot be the complement of both.
Common mistake
(Swapping the two radii)
The greedy bound divides by a ball of radius , the packing bound by a ball of radius . Using radius in the greedy bound would claim, for binary , , a code with at least words, which contradicts the packing bound of . Disjointness is available only at radius ; covering is guaranteed only at radius .
What the theorem does not supply
The algorithm may inspect an exponentially large ambient set of words. Its existence proof does not supply an efficient encoder or decoder, a linear code, or a channel-specific error probability. The packing argument does imply uniqueness when at most symbols are corrupted, but an efficient method for locating the closest codeword requires additional work.
Exercises
Quick check
(Calculate and the greedy lower bound for .)
Only the center and its neighbors lie within distance one.
Solution · Answer
, so the greedy code has at least words.
Quick check
(For binary , why is the packing radius one while the greedy covering radius is two?)
Compare the radius used for disjointness with the radius removed by the algorithm.
Solution · Answer
Radius-one balls are disjoint when centers are distance at least three; the greedy process excludes all words at distance at most so its selected centers have the required separation.
Quick check
(Verify that have minimum distance three.)
Compute all six pairwise distances.
Solution · Answer
Their nonzero weights are and the distances between the three nonzero words are , so the minimum is three.
Quick check
(Does a maximal greedy code necessarily have the maximum possible number of codewords? What does the proof establish?)
Compare inclusion-maximal with maximum size.
Solution · Answer
The proof does not establish that. It establishes inclusion-maximality, pairwise distance at least , and the stated minimum size.
Further reading
Carnegie Mellon University coding theory course notes list notes on the Gilbert–Varshamov bound and basic code bounds.