Richard Hamming was a mathematician. Learning about Hamming Code, once again made me realize that clever theory goes a long way.

Hamming Code is an error correction technique. Error correction techniques are useful if the data transmission takes a long time and it’s not cheap to retransmit the data. Consider transmitting data to a satellite orbiting a distant planet: It might take hours. And if the data gets corrupted in transit, sending it once again would mean added hours. Instead, adding an error correction code and transmiting it with the data itself gives the receiver the option to detect corruption and correct it.

I’m not sure how widely Hamming Code is used in practice today as it’s single-error correcting, double-error detecting. So it fails to correct errors if there are multiple. Still I believe it’s a clever method to detect errors with decreasing overhead as the data size grows.

As an example, I’ll give Hamming(7,4):

The setup

We’re sending 4 bits of data. We’ll transmit 7 bits total — 3 of them redundant. A single bit may flip somewhere in transit. The receiver must recover the original 4 bits without asking us to resend.

flowchart LR
    A["Message<br/>1011"] -->|encode| B["Codeword<br/>0110011"]
    B -->|channel noise| C["Received<br/>0110111"]
    C -->|decode| D["Message<br/>1011"]

The three parity bits go at positions 1, 2, and 4. Data fills the leftovers: 3, 5, 6, and 7.

When we write out each position number in binary, the rule becomes visible:

Position Binary Checked by
1 001 check 1
2 010 check 2
3 011 check 1, check 2
4 100 check 4
5 101 check 1, check 4
6 110 check 2, check 4
7 111 check 1, check 2, check 4

The rule: the parity bit at position 2ⁱ covers every position whose binary form has bit i switched on.

  • Check 1 watches positions {1, 3, 5, 7}
  • Check 2 watches positions {2, 3, 6, 7}
  • Check 4 watches positions {4, 5, 6, 7}

When we draw it as a grid, we can also see that every every column is different and each parity bit is the only power-of-two in its own group

position:   1   2   3   4   5   6   7
          ─────────────────────────────
check 1:    ●       ●       ●       ●
check 2:        ●   ●           ●   ●
check 4:                ●   ●   ●   ●

How to encode the parity bits

  1. Drop the data into positions 3, 5, 6, 7 — that’s 1, 0, 1, 1.
  2. Then set each parity bit so that its group contains an even number of ones. To find the parity bit’s value, we can use a chained XOR operation on the data bits the parity bit should be watching.
Parity bit Watches Data in group XOR Value
p₁ (pos 1) 3, 5, 7 1, 0, 1 1⊕0⊕1 0
p₂ (pos 2) 3, 6, 7 1, 1, 1 1⊕1⊕1 1
p₄ (pos 4) 5, 6, 7 0, 1, 1 0⊕1⊕1 0

Values of parity (p) and data (d) bits by their positions are as follows:

position:   1   2   3   4   5   6   7
value:      0   1   1   0   0   1   1
            ↑   ↑   ↑   ↑   ↑   ↑   ↑
            p   p   d   p   d   d   d

The full data that would be in transit becomes 0110011.

How to decode the data

Happy path

Let’s first suppose the data is not corrupted in transmit and the receiver gets 0110011:

Check Positions Bits received XOR Verdict
1 1, 3, 5, 7 0, 1, 0, 1 0 pass
2 2, 3, 6, 7 1, 1, 1, 1 0 pass
4 4, 5, 6, 7 0, 0, 1, 1 0 pass

Everything passes, which means the data is correctly transmitted. We pull the data bits and that’s 1, 0, 1, 1.

Failure mode

Now let’s suppose position 5 is corrupted. The receiver gets 0110111 (p5 is 1) instead of 0110011 (p5 was 0). If we recompute all three checks:

Check Positions Bits received XOR Verdict
1 1, 3, 5, 7 0, 1, 1, 1 1 fail
2 2, 3, 6, 7 1, 1, 1, 1 0 pass
4 4, 5, 6, 7 0, 1, 1, 1 1 fail

The failure indicates that there is data corruption: 1, 1, 1, 1 is not the data we sent. By writing the three results as a binary number, we can find the position of the corrupted bit. We write it by most significant first — check 4, check 2, check 1:

   1     0     1     =  5
   ↑     ↑     ↑
 chk4  chk2  chk1

Position 5. We flip it back and get 0110011 which then translates to the correct data sequence when we pull the data positions of 3, 5, 6, and 7: 1, 0, 1, 1.

SECDED

We are able to correct a single error with Hamming(7,4). But what if there is a second error? We can add an eight bit, making it Hamming(8,4), and that gives us Single Error Correcting, Double Error Detecting. We can’t correct both errors, but we at least know the data is corrupted, and it doesn’t become a silent error that goes unnoticed.

The overall parity is the chained XOR operation of all seven bits.

flowchart TD
    S{"Syndrome = 0?"} -->|yes| P1{"Overall parity ok?"}
    S -->|no| P2{"Overall parity ok?"}
    P1 -->|yes| A["Clean"]
    P1 -->|no| B["The parity bit itself flipped"]
    P2 -->|no| C["Single error — correct it"]
    P2 -->|yes| D["Double error — detected,<br/>not correctable"]

When syndrome is non-zero and overall parity fails, this tells us that there is a single error we can correct. If, on the other hand, the syndrome is non-zero but overall parity checks out, that tells us something is wrong. If there is an error, the overall parity should also fail. In this case, we find out that there is a double error that we cannot fix.

One extra bit costs us 12.5% but converts a silent wrong answer into a visible error.

Scaling up

The family generalises to Hamming(2ᵐ−1, 2ᵐ−1−m):

m Code Data bits Overhead
3 (7, 4) 4 42.9%
4 (15, 11) 11 26.7%
5 (31, 26) 26 16.1%
6 (63, 57) 57 9.5%

As we can see from the table above, longer blocks are dramatically cheaper. They can only correct one error, though. The bigger the data block gets, the odds of a second error inside the same block grows. That’s why Hamming codes pay off when errors are rare and independent.