Back to the on-screen lesson ·
Sphere packing: M · V(n, t) ≤ 2^n; perfect codes; the Gilbert-Varshamov guarantee.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to count the words in a Hamming ball, derive the sphere-packing bound on the size of a $t$-error-correcting code, recognise perfect codes as the cases of equality, and contrast this upper bound with the Gilbert-Varshamov lower bound that guarantees good codes exist. You will prove the Singleton bound by deleting coordinates, define maximum distance separable codes, compute their dimension and correction capability from their redundancy, explain why nontrivial binary MDS codes do not exist, and use both bounds to test whether a proposed set of code parameters is possible.
How many codewords can a length-$n$ code with minimum distance $d = 2t + 1$ have? The Hamming ball of radius $t$ around a word contains $V(n, t) = \sum_{i=0}^{t} \binom{n}{i}$ words, and $t$-error correction means the balls around distinct codewords are disjoint, so $$M \cdot V(n, t) \le 2^n,$$ the Hamming bound or sphere-packing bound; for linear codes, $k \le n - \log_2 V(n, t)$. A code meeting it with equality is perfect: the balls tile the space. The perfect binary codes are exactly the trivial codes, the odd-length repetition codes, the Hamming codes and the $[23, 12, 7]$ Golay code. In the other direction the Gilbert-Varshamov bound guarantees existence: choosing codewords greedily, each at distance at least $d$ from all previous ones, cannot stop while fewer than $2^n / V(n, d - 1)$ have been chosen, so a code at least that large exists. Asymptotically the two bounds leave a gap, and where the truth lies for large $n$ is still an open problem; Shannon's random codes live in the same territory.
Another way: picture
A box of $2^n$ cells with balls of $V(n, t)$ cells each placed around codewords: the balls cannot overlap, so their number is at most the box divided by the ball. A perfect code leaves no cell uncovered.
Another way: steps
The Hamming ball of radius $t$ around a word contains every word reachable by flipping at most $t$ bits: $$V(n, t) = \sum_{i=0}^{t} \binom{n}{i} = 1 + n + \binom{n}{2} + \cdots$$ — one word at distance $0$, $n$ at distance $1$ (choose the bit to flip), $\binom{n}{2}$ at distance $2$, and so on.
| $n$ | $V(n, 1) = 1 + n$ | $V(n, 2) = 1 + n + \binom{n}{2}$ | $V(n, 3)$ |
|---|---|---|---|
| $7$ | $8$ | $29$ | $64$ |
| $10$ | $11$ | $56$ | $176$ |
| $15$ | $16$ | $121$ | $576$ |
| $23$ | $24$ | $277$ | $2048$ |
| $31$ | $32$ | $497$ | $4992$ |
A $t$-error-correcting code has disjoint balls of radius $t$ around its codewords (lesson 18), and they all live inside the $2^n$ words. Counting gives the Hamming bound, also called the sphere-packing bound: $$M \cdot V(n, t) \le 2^n, \qquad \text{or } k \le n - \log_2 V(n, t) \text{ for a linear code.}$$ It is an upper bound — it says how good a code cannot be. A code that meets it with equality is perfect: the balls tile the space with nothing left over.
| code | $n$ | $M = 2^k$ | $t$ | $V(n, t)$ | $M \cdot V(n, t)$ | perfect? |
|---|---|---|---|---|---|---|
| Hamming $[7, 4]$ | $7$ | $16$ | $1$ | $8$ | $2^7$ | yes |
| $3$-repetition | $3$ | $2$ | $1$ | $4$ | $2^3$ | yes |
| $5$-repetition | $5$ | $2$ | $2$ | $16$ | $2^5$ | yes |
| Golay $[23, 12, 7]$ | $23$ | $2^{12}$ | $3$ | $2^{11}$ | $2^{23}$ | yes |
| single parity $[5, 4]$ | $5$ | $16$ | $0$ | $1$ | $2^4$ | no ($d = 2$) |
That list is essentially complete: the only perfect binary codes are the trivial ones, the odd-length repetition codes, the Hamming codes and the $[23, 12, 7]$ Golay code. In the other direction the Gilbert-Varshamov bound guarantees that good codes exist: greedily choosing codewords, each excluding a ball of radius $d - 1$, keeps working as long as $M \cdot V(n, d - 1) < 2^n$. Two bounds, two jobs — Hamming says what is impossible, Gilbert-Varshamov says what is achievable, and the truth lies between them.
Common mistakes
$d = 5$ corrects $t = 2$; $V(10, 2) = 1 + 10 + 45 = 56$.
Ball size.
Hamming: $M \le 1024/56 \approx 18.3$, so $M = 64$ is impossible; even $M = 19$ is.
The bound rules it out.
$[23, 12, 7]$: $t = 3$, $V(23, 3) = 1 + 23 + 253 + 1771 = 2048 = 2^{11}$.
A remarkable coincidence of binomials.
$2^{12} \cdot 2^{11} = 2^{23}$: equality, so the radius-$3$ balls tile $\mathbb{F}_2^{23}$.
$d = 5$ corrects $t = 2$ errors.
$V(10, 2) = 1 + 10 + 45 = 56$.
Hamming: $M \le 1024/56 = 18.3$, so $M = 64$ is impossible — and so is $M = 19$.
The bound rejects the claim without constructing anything.
$[23, 12, 7]$: $t = 3$, so $V(23, 3) = 1 + 23 + 253 + 1771 = 2048 = 2^{11}$.
$\binom{23}{2} = 253$ and $\binom{23}{3} = 1771$.
$M \cdot V = 2^{12} \cdot 2^{11} = 2^{23}$.
Equality: the radius-$3$ balls tile $\mathbb{F}_2^{23}$, so the Golay code is perfect — one of only four kinds.
$V(15, 1) = 16$; $M \le 2^{15}/16 = 2^{11}$.
$2048$, achieved by the $[15, 11]$ Hamming code.
How many binary words of length $21$ lie within Hamming distance $1$ of a given word?
Computed value: answer
How many binary words of length $13$ lie within Hamming distance $2$ of a given word?
Computed value: answer
A binary code of length $n = 15$ corrects one error. By the Hamming (sphere-packing) bound, at most how many codewords can it have?
Computed value: answer
How many binary words of length $14$ lie within Hamming distance $1$ of a given word?
Computed value: answer
Which statement correctly pairs the Hamming bound and the Gilbert-Varshamov bound?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
How many binary words of length $5$ lie within Hamming distance $2$ of a given word?
Computed value: answer
You can bound what any code can achieve and recognise the codes that hit the bounds. Last: cyclic codes and Reed-Solomon codes, the constructions that do it in practice.
9. Your turn: how many codewords can a length-$15$ single-error-correcting code have?, step 2