Hamming Code

Detect or correct?

A CRC tells the receiver that something went wrong, and the sender has to send the frame again. Sometimes a resend is impossible or too slow: data read back from a memory chip, a photo sent from a space probe, or a QR code with a smudge. Then we want an error-correcting code that says exactly which bit is wrong.

Richard Hamming invented such a code in 1950, frustrated that the computer kept stopping on his weekend jobs whenever it found an error.

The trick: parity bits at the powers of two

Number the bit positions from 1. Put parity bits at positions 1, 2, 4, 8, … and the data bits everywhere else.

Write every position in binary. Parity bit p1 watches every position whose binary number ends in 1 (1, 3, 5, 7, …). p2 watches positions with the 2s bit set (2, 3, 6, 7, …). p4 watches positions with the 4s bit set (4, 5, 6, 7, …), and so on. Each parity bit is chosen to make the number of 1s in its group even.

Position	1	2	3	4	5	6	7
Binary	001	010	011	100	101	110	111
Role	p1	p2	d1	p4	d2	d3	d4
Checked by p1	✓		✓		✓		✓
Checked by p2		✓	✓			✓	✓
Checked by p4				✓	✓	✓	✓

Every position is watched by a different combination of parity bits, and that combination is just its binary number. This is the whole secret.

Encoding 1011

Data bits go to positions 3, 5, 6 and 7: d1 = 1, d2 = 0, d3 = 1, d4 = 1.

• p1 (positions 3, 5, 7 → 1, 0, 1): two 1s, already even → p1 = 0
• p2 (positions 3, 6, 7 → 1, 1, 1): three 1s, odd → p2 = 1
• p4 (positions 5, 6, 7 → 0, 1, 1): two 1s, even → p4 = 0

The code word is 0110011.

Finding and fixing an error

Suppose bit 6 flips and the receiver gets 0110001. It re-checks every group:

• p1 group (1, 3, 5, 7): 0, 1, 0, 1 → even ✓ → 0
• p2 group (2, 3, 6, 7): 1, 1, 0, 1 → odd ✗ → 1
• p4 group (4, 5, 6, 7): 0, 0, 0, 1 → odd ✗ → 1

Read the results as a binary number, p4 p2 p1 = 110 = 6. The syndrome is the position of the wrong bit. Flip bit 6 back and the data is repaired, with no resend needed. A syndrome of 000 means no error.

How many parity bits?

With r parity bits the syndrome can name 2ʳ different things: “no error” plus each of the m + r positions. So we need 2ʳ ≥ m + r + 1.

Data bits m	Parity bits r	Code word	Name
4	3	7	Hamming(7, 4)
11	4	15	Hamming(15, 11)
26	5	31	Hamming(31, 26)
57	6	63	Hamming(63, 57)

The overhead shrinks fast: protecting 57 bits costs only 6 extra bits.

Code

def hamming_encode(data: str) -> str:
    m = len(data)
    r = 0
    while 2 ** r < m + r + 1:
        r += 1
    n = m + r
    word = [0] * (n + 1)                       # 1-based positions
    bits = iter(data)
    for pos in range(1, n + 1):
        if pos & (pos - 1):                    # not a power of two: a data bit
            word[pos] = int(next(bits))
    for i in range(r):
        p = 2 ** i
        word[p] = sum(word[pos] for pos in range(1, n + 1) if pos & p) % 2
    return "".join(map(str, word[1:]))

def hamming_syndrome(word: str) -> int:
    s = 0
    for pos, b in enumerate(word, start=1):
        if b == "1":
            s ^= pos                           # XOR of the positions of all 1s
    return s                                   # 0 = no error, else the bad position

code = hamming_encode("1011")
print(code)                                    # 0110011
bad = code[:5] + ("0" if code[5] == "1" else "1") + code[6:]   # flip bit 6
print(bad, hamming_syndrome(bad))              # 0110001 6

The hamming_syndrome function shows a neat property: XOR together the positions of all the 1s and you get the syndrome directly.

Where is it used?

• ECC memory in servers fixes single-bit errors in RAM on the fly. It uses a Hamming code plus one extra parity bit (SECDED: single error correction, double error detection).
• Flash storage and SSD controllers use stronger relatives (BCH, LDPC codes).
• Space probes and satellites, where asking for a resend can take hours.

Common mistakes

• Numbering positions from 0. Hamming codes number them from 1, otherwise the syndrome is off by one.
• Placing parity bits at the end instead of at the powers of two.
• Reading the syndrome in the wrong order. It is p4 p2 p1, with the highest parity bit on the left.
• Expecting it to fix two flipped bits. A plain Hamming code then points at the wrong position, which is why ECC memory adds one more parity bit to detect double errors.