Back to the on-screen lesson ·
d ≤ n − k + 1; codes that meet it; what the bounds allow.
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.
The Singleton bound limits distance by redundancy: any code of length $n$ with $M$ codewords and minimum distance $d$ has $M \le q^{n - d + 1}$ over an alphabet of size $q$, so a linear $[n, k, d]$ code satisfies $$d \le n - k + 1.$$ Proof: delete any $d - 1$ coordinates; codewords still differ, so the $M$ shortened words are distinct among the $q^{n - d + 1}$ words of that length. Codes meeting the bound are maximum distance separable (MDS): every $k$ coordinates determine the codeword, and $k = n - d + 1$, so with $n - k$ redundant symbols they correct $\lfloor (n - k)/2 \rfloor$ errors, two check symbols per corrected error, the best possible. Over the binary alphabet only trivial codes are MDS (repetition, single parity, the whole space); the Hamming $[7, 4, 3]$ code has $d = 3 < 4$. Over larger alphabets Reed-Solomon codes are MDS for every $n \le q$ and $k$, which is why they are used wherever symbols are bytes: discs, QR codes, deep-space links. The Singleton and Hamming bounds are two of several (Plotkin, Elias, linear programming) that together fence in what codes can exist.
Another way: picture
A row of $n$ boxes; the first $d - 1$ crossed out. Two codewords that agreed on every remaining box would differ in at most $d - 1$ places, contradicting $d$. So the surviving $n - d + 1$ boxes already tell the codewords apart, and $2^{n - d + 1}$ is all the room there is.
Another way: steps
The Singleton bound is the simplest bound in coding theory and the easiest to prove. Delete any $d - 1$ coordinates from every codeword. Two codewords that agreed on all the remaining positions would have differed in at most $d - 1$ places, contradicting the minimum distance — so the $M$ shortened words are still distinct, and there are only $q^{n - d + 1}$ words of that length. Hence $$M \le q^{n - d + 1}, \qquad \text{and for a linear code } d \le n - k + 1.$$ Distance costs redundancy, one symbol of redundancy per unit of distance, at best.
| code | $n - k + 1$ | claimed $d$ | verdict |
|---|---|---|---|
| $[7, 4]$ | $4$ | $3$ | possible (Hamming) |
| $[20, 15]$ | $6$ | $7$ | impossible |
| $[12, 8]$ | $5$ | $5$ | would be MDS; not over $\mathbb{F}_2$ |
| $[255, 223]$ over bytes | $33$ | $33$ | MDS: Reed-Solomon |
Codes meeting the bound are maximum distance separable (MDS). They have a striking property: any $k$ coordinates determine the codeword, so any $n - k$ erasures can be filled. With $n - k$ redundant symbols an MDS code corrects $\lfloor (n - k)/2 \rfloor$ errors — two check symbols per corrected error, which is the best any code can do, since each error costs one symbol to locate and one to correct.
Over the binary alphabet only trivial codes are MDS, which is why the interesting MDS codes live over larger alphabets — bytes, most often. That is exactly what Reed-Solomon codes do (lesson 22), and it is why storage and deep-space links use them.
Common mistakes
Someone claims a $[20, 15, 7]$ binary code. Singleton: $d \le 20 - 15 + 1 = 6$.
$7 > 6$: impossible, whatever the construction; the Hamming bound would reject it too.
Over bytes ($q = 256$), the $[255, 223]$ code used on deep-space links has $n - k = 32$ check symbols.
MDS: $d = 33$, correcting $16$ byte errors anywhere in the block, the Singleton maximum.
Someone claims a $[20, 15, 7]$ binary code.
Singleton: $d \le 20 - 15 + 1 = 6$.
$7 > 6$: impossible, whatever the construction — and one line of arithmetic settled it.
The Hamming bound would reject it too, with more work.
Over bytes ($q = 256$), the $[255, 223]$ code has $n - k = 32$ check symbols.
MDS, so $d = n - k + 1 = 33$.
It corrects $\lfloor 32/2 \rfloor = 16$ byte errors anywhere in the block — the Singleton maximum for that much redundancy.
$d \le 12 - 8 + 1 = 5$.
$k = 12 - 5 + 1 = 8$: the same code, if it exists over a large enough alphabet.
An $[\,27, 15\,]$ code: what is the largest minimum distance the Singleton bound allows?
Computed value: answer
A code of length $15$ meets the Singleton bound with minimum distance $8$. What is its dimension $k$?
Computed value: answer
An MDS code has $n - k = 16$ redundant symbols. How many symbol errors can it correct?
Computed value: answer
An $[\,21, 13\,]$ code: what is the largest minimum distance the Singleton bound allows?
Computed value: answer
Why does every $(n, M, d)$ code satisfy $M \le 2^{n - d + 1}$, that is $k \le n - d + 1$ for linear codes?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A code of length $27$ meets the Singleton bound with minimum distance $5$. What is its dimension $k$?
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: largest $d$ for a $[12, 8]$ code, and the $k$ of an MDS code with $n = 12$, $d = 5$, step 2