Error-Correcting Codes: Hamming Codes

A Hamming code is a way of adding a few extra check bits to your data so that, if one bit gets flipped on the way, the receiver can work out exactly which one and flip it back. It's named after Richard Hamming, who invented it, and "(7,4)" means 7 bits get sent for every 4 bits of data. That makes it the tool for places where you can't just ask for a resend, like memory chips and spacecraft. The syndrome formula $\mathbf s = H\mathbf r \bmod 2$ looks heavy, but it's just three small pieces: $\mathbf r$ (the 7 bits that arrived), $H$ (three yes/no checks, each asking "does this group of bits have an even number of 1s?") and $\bmod 2$ (we only care about even or odd), and the three answers, read as a binary number, point straight at the bad bit. It looks complex, but it's just three parity checks working together; bear with it.

Parity and CRCs from the last lesson only tell you that something went wrong, and then you ask for a resend. Sometimes you can't: a spacecraft is hours away, a memory chip just returned bad data, a scratched disc can't be reread. Then the code has to correct the error.

Repetition. Send every bit three times: 0 becomes 000 and 1 becomes 111. If one copy flips, the majority still wins. It works, but two thirds of everything sent is overhead.

Distance is the key. Why does repetition work at all? Because its two codewords are far apart. The Hamming distance between two words is the number of positions where they differ, which is the number of 1s in their XOR. If every two codewords are at least $d$ apart, then:

• up to $d - 1$ flips can't turn one codeword into another, so they're detected;
• up to $\lfloor (d - 1)/2 \rfloor$ flips leave the received word closer to the original than to any other codeword, so decoding to the nearest codeword corrects them.

000 and 111 are 3 apart, so repetition corrects one error.

Hamming(7,4) also has distance 3 but spends only 3 check bits on 4 data bits. Number the positions 1 to 7. The check bits sit at the powers of 2 (positions 1, 2 and 4) and the data bits at 3, 5, 6 and 7. Each check bit covers the positions whose binary numbers share its 1:

• $p_1$ covers 1, 3, 5, 7, the positions with a 1 in the ones place;
• $p_2$ covers 2, 3, 6, 7, with a 1 in the twos place;
• $p_4$ covers 4, 5, 6, 7, with a 1 in the fours place.

Each is set so its group has an even number of 1s.

Decoding reads a binary number. Here's where the clever numbering pays off. The receiver reruns the three checks. If position $k$ flipped, the checks that fail are exactly the ones covering $k$, and by design those are the 1 bits of $k$. So the failures, written as $c_4c_2c_1$, spell out $k$ in binary, and 000 means no error. Equivalently, the syndrome is the XOR of the positions that hold a 1:

int syndrome = 0;
for (int pos = 1; pos <= 7; pos++)
    if (bit(word, pos)) syndrome ^= pos;   // 0 when every check passes
if (syndrome) flip(word, syndrome);

It's linear algebra mod 2. If you've seen null spaces before, this will feel familiar. Over the field $\{0, 1\}$, where $1 + 1 = 0$, the codewords are exactly the null space of $H$, whose columns are 1 through 7 in binary. If $\mathbf c$ is sent and bit $k$ flips, then $H(\mathbf c + \mathbf e_k) = H\mathbf c + H\mathbf e_k = \mathbf 0 + (\text{column } k)$. Row reduction, null spaces and dimension all work over this two-element field: $H$ has rank 3, so its null space has dimension $7 - 3 = 4$, which makes $2^4 = 16$ codewords.

Perfect packing. Each codeword has 7 neighbors one flip away, so its ball of radius 1 holds 8 words, and $16 \times 8 = 128 = 2^7$. The balls fill the whole space with nothing left over, so every possible received word decodes to exactly one codeword. Richard Hamming found these codes at Bell Labs around 1950, fed up with a relay computer that stopped on errors over the weekend instead of fixing them.

In practice, one more overall parity bit makes an (8,4) code that corrects one error and detects two (SECDED). Server ECC memory stores each 64-bit word as 72 bits this way. CDs, QR codes and deep-space links use stronger codes (Reed–Solomon, LDPC) built on the same idea: keep the codewords far apart.

ECC memory in servers corrects single-bit flips from cosmic rays and electrical noise on every 64-bit word, using a Hamming code plus a parity bit. QR codes, CDs and deep-space probes use stronger relatives built on the same idea of keeping codewords far apart.