Correcting errors

The Hamming(7,4) code

Detecting is not always enough

When retransmission is impossible (a scratched CD, a signal from a distant satellite), the error must be corrected on the spot, without asking for the message again. The Hamming(7,4) code, invented in 1950, achieves this feat: it transmits 4 data bits protected by 3 check bits, and automatically corrects any single-bit error.

Three overlapping parity bits

The trick: each check bit monitors a different subset of the data bits, and these subsets overlap. This is represented by three overlapping circles (a Venn diagram): the 4 data bits in the center, each parity bit covering one circle.

Hamming(7,4) diagram: 3 overlapping circles

            ___________
           /  P1       \
          /    ___________
         |    /  d1   \    \
         |   |  ___________|
          \  | /  d4   \ | /
           \_|_|   d2  |_|/
             | \_______/ |
          P2 |    d3     | P3
              \_________/

(each parity bit P1, P2, P3 makes the total of ITS circle even)
(a single faulty bit belongs to a unique combination of circles: this reveals its exact position)

Correction, like a treasure hunt

On reception, the three parities are recomputed. If all three are correct, there is no error. Otherwise, the combination of wrong parities points exactly to the faulty bit: each position belongs to a unique combination of circles. You flip that bit, and the message is repaired — without having asked for anything again.

The price of correction

Hamming(7,4) has a minimum distance of 3: the minimum needed to correct 1 error (2d+1 = 3 with d=1). It pays for this capability with redundancy: 7 bits transmitted for 4 useful bits, an overhead of about 43%. Correcting always costs more than detecting.

Classic pitfall