Hamming Code

Hamming(7,4): rate 4/7, single-error correction, syndrome = error position.

The idea

The Hamming code arranges parity checks so that together they locate a single flipped bit exactly.

Number the seven positions $1$ through $7$ and write each number in binary. Reserve the power-of-two positions $1$, $2$ and $4$ for parity bits; the other four, $3, 5, 6, 7$, carry the message. Assign each parity bit the positions whose binary index has a $1$ in its place: the bit at position $1$ checks $\{1, 3, 5, 7\}$, the bit at position $2$ checks $\{2, 3, 6, 7\}$, and the bit at position $4$ checks $\{4, 5, 6, 7\}$. Set each parity bit so that its group holds an even number of $1$s. The three settings are independent, because each parity bit belongs to exactly one group — its own.

Now suppose one bit flips in transit. The receiver recomputes the three checks, and a check comes out odd exactly when the flipped position belongs to its group. Read the three results as a three-digit binary number: it equals the flipped position's index, because that index records which groups the position belongs to. If all three checks come out even, nothing was flipped.

The code's parameters are written $[n, k, d] = [7, 4, 3]$: length $n = 7$, dimension $k = 4$, minimum distance $d = 3$. Three parity bits correct any single error at rate $k/n = 4/7$, where repeating each bit three times gives the same guarantee at rate $1/3$.

Ways to work on it

• Walkthrough. Encode a short message, corrupt one bit, and decode it using the syndrome.
• Practice. Compute the syndrome of a received word and find the error.
• Hardest. Random received word — includes some valid-codeword (no-error) cases.

Not sure where to start? Take the ten-question placement test.