What is it?

Hamming codes detect and correct single-bit errors in blocks of transmitted data. The (7,4) variant takes 4 data bits and adds 3 parity bits, creating a 7-bit codeword that can survive one flipped bit.

This is the simplest and most elegant error correction code. It was invented by Richard Hamming in 1950 at Bell Labs, after he grew frustrated with punched card readers that would abort on single-bit errors. His insight: add parity bits at positions that are powers of 2, each covering a specific subset of bit positions. The syndrome — the pattern of which parities disagree — directly points to the error's location.

Concrete Example

Message HELLO — each character is 8 bits. Split into 4-bit nibbles:

H = 0100 1000 → nibble 1 = 0100, nibble 2 = 1000

Encode each nibble with the generator matrix G:

G = [I₄ | P]
    1 0 0 0 | 1 1 0
    0 1 0 0 | 1 0 1
    0 0 1 0 | 0 1 1
    0 0 0 1 | 1 1 1

codeword = data_bits · G

Parity-check matrix H:
    1 1 0 1 | 1 0 0
    1 0 1 1 | 0 1 0
    0 1 1 1 | 0 0 1

To decode: compute syndrome s = H · r^T where r is the received 7-bit block. If s = (0,0,0), no error. If s matches a column of H, that column index tells you which bit flipped.

How It Works

1. Encoding: split message into 4-bit chunks, multiply by generator matrix G (over GF(2))
2. Channel: noise may flip bits — each 7-bit block can survive at most 1 flipped bit
3. Syndrome: compute H · r^T = s. If s ≠ 0, the error is at the column position in H matching s
4. Correction: flip the erring bit, extract data bits (positions 0,1,2,3), reassemble ASCII

Solving The Puzzle

def hamming_decode(block_7bit, H):
    s = [0, 0, 0]  # syndrome
    for row in range(3):
        for col in range(7):
            s[row] ^= block_7bit[col] & H[row][col]
    if s != [0, 0, 0]:
        # Find which column of H matches s
        for col in range(7):
            if [H[r][col] for r in range(3)] == s:
                block_7bit[col] ^= 1  # flip error
                break
    # Extract data bits (positions 0-3)
    return block_7bit[:4]

Difficulty Table

Real-World Applications

• ECC RAM: Every server DIMM uses Hamming codes to correct single-bit memory errors
• Satellites: NASA's deep space network uses Hamming codes for telemetry data
• Voyager: The Voyager spacecraft used (7,4) Hamming codes for image transmission
• NOR Flash: Hamming codes protect data integrity in embedded flash memory