Back to the on-screen lesson ·
[2^r − 1, 2^r − 1 − r, 3] codes whose columns are all nonzero r-bit vectors; perfect codes.
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 compute the syndrome of a received word, explain why it depends only on the error pattern, describe the cosets of a linear code and their leaders, and perform syndrome decoding by hand, including locating and correcting a single error by matching the syndrome to a column of the parity-check matrix. You will construct the Hamming code for any number of parity bits, state its length, dimension, rate and minimum distance, decode it in one step with the binary column ordering, and prove that it is perfect by counting syndromes against error patterns.
For each $r \ge 2$ the binary Hamming code is the linear code whose parity-check matrix has as columns all $2^r - 1$ nonzero $r$-bit vectors. Its parameters are $n = 2^r - 1$, $k = n - r = 2^r - 1 - r$, and $d = 3$: no column is zero and no two are equal, so no codeword has weight $1$ or $2$, while three columns such as $001, 010, 011$ sum to zero. It corrects any single error and detects any double error, at rate $k/n \to 1$: $[3, 1]$ is the repetition code, $[7, 4]$ the classic, $[15, 11]$, $[31, 26]$ and so on. Ordering the columns as the binary numbers $1$ to $n$ makes decoding a one-liner: the syndrome of a single error is the position of the error, written in binary. Hamming codes are perfect: the $2^r$ syndromes are exhausted by the zero pattern and the $n = 2^r - 1$ single errors, so the Hamming balls of radius $1$ around the codewords partition $\mathbb{F}_2^n$, and the sphere-packing bound $2^k (1 + n) \le 2^n$ holds with equality. Adding an overall parity bit gives the extended $[2^r, 2^r - 1 - r, 4]$ code, which corrects one error and detects two at once, the SECDED code inside computer memory.
Another way: picture
The $128$ words of length $7$ drawn as dots, the $16$ codewords marked. Around each codeword a ball of $8$ words (itself and its $7$ neighbours). The $16$ balls of $8$ words cover all $128$ dots without overlap: perfect.
Another way: steps
For each $r \ge 2$ the binary Hamming code is defined by one instruction: let the columns of $H$ be all $2^r - 1$ nonzero $r$-bit vectors. Everything follows. The length is $n = 2^r - 1$ (one position per column), the dimension is $k = n - r$, and the distance is exactly $3$: no column is zero, so no codeword has weight $1$; no two columns are equal, so none has weight $2$; but $001 \oplus 010 \oplus 011 = 000$, so one of weight $3$ exists.
| $r$ | $n = 2^r - 1$ | $k = n - r$ | rate | $d$ | ball size $1 + n$ | $2^k (1 + n)$ |
|---|---|---|---|---|---|---|
| $2$ | $3$ | $1$ | $1/3$ | $3$ | $4$ | $2 \cdot 4 = 2^3$ |
| $3$ | $7$ | $4$ | $4/7$ | $3$ | $8$ | $16 \cdot 8 = 2^7$ |
| $4$ | $15$ | $11$ | $11/15$ | $3$ | $16$ | $2048 \cdot 16 = 2^{15}$ |
| $5$ | $31$ | $26$ | $26/31$ | $3$ | $32$ | $2^{26} \cdot 32 = 2^{31}$ |
| $6$ | $63$ | $57$ | $57/63$ | $3$ | $64$ | $2^{57} \cdot 64 = 2^{63}$ |
The last column is the point. A single-error-correcting code has disjoint balls of radius $1$, each holding $1 + n$ words, and here $2^k (1 + n) = 2^k \cdot 2^r = 2^n$ exactly: the balls tile the space with nothing left over. A code that meets the sphere-packing bound with equality is called perfect (lesson 21), and the Hamming codes are the infinite family of them. Notice also the rate: $k/n = 1 - r/(2^r - 1) \to 1$. Four parity bits protect eleven data bits, six protect fifty-seven — redundancy grows logarithmically while the block grows exponentially.
The three-circle picture is the $[7, 4]$ code drawn by hand: four message bits in the overlaps, three parity bits one per circle, each circle holding an even number of ones. Flip one bit and exactly the circles it belongs to go odd — and which circles those are names the position, which is the syndrome argument again in a picture.
Common mistakes
$r = 4$: $n = 15$, $k = 11$, rate $0.733$, $d = 3$.
Parameters from $r$.
Perfect: $2^{11} \cdot 16 = 2^{15}$. Four parity bits protect eleven data bits against any single error.
Weight $1$ would need a zero column; weight $2$ two equal columns; neither exists among the distinct nonzero vectors.
Weight $3$ exists: columns $001, 010, 011$ sum to zero, so $0000111$ (positions $1, 2, 3$ in the binary ordering) is a codeword.
$n = 2^5 - 1 = 31$ and $k = 31 - 5 = 26$.
Rate $26/31 \approx 0.839$, and $d = 3$ as always.
Perfect: $2^{26} \cdot 32 = 2^{31}$ — five parity bits protect twenty-six data bits against any single error.
Weight $1$ would need a zero column of $H$; every column is nonzero by construction.
Weight $2$ would need two equal columns; the columns are all the distinct nonzero vectors, so none repeats.
Weight $3$ exists: columns $001, 010, 011$ sum to zero, so $1110000$ is a codeword. Hence $d = 3$, no more and no less.
$n = 31$, $k = 26$.
Rate $26/31 \approx 0.84$, $d = 3$, perfect since $2^{26} \cdot 32 = 2^{31}$.
A binary Hamming code has $5$ parity-check bits. What are its length $n$ and dimension $k$? Enter $k$.
Computed value: answer
What is the rate of the Hamming code with $4$ parity bits? Give a fraction.
Computed value: answer
The Hamming code with $4$ parity bits has length $15$. What is its minimum distance, and how many errors does it correct? Enter the minimum distance.
Computed value: answer
A binary Hamming code has $4$ parity-check bits. What are its length $n$ and dimension $k$? Enter $k$.
Computed value: answer
Why is the Hamming code with $3$ parity bits called perfect?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
What is the rate of the Hamming code with $6$ parity bits? Give a fraction.
Computed value: answer
You can decode any single error with a syndrome and build the perfect Hamming codes. Next: the bounds that say how good any code can possibly be.
9. Your turn: $r = 5$, step 2