Hamming Code

Hamming codes add overlapping parity bits so a single-bit error can be located and corrected automatically.

The construction

Hamming codes place parity bits at positions that are powers of two (1, 2, 4, 8…) and data bits in the rest. Each parity bit covers the positions whose index has a particular bit set, so the coverage groups overlap in a structured way.

Locating the error

On receipt, each parity check is recomputed. The failing checks, read as a binary number, give the syndrome — the exact position of the flipped bit. Flipping that bit corrects the error; a zero syndrome means no error.

SECDED

The (7,4) Hamming code corrects any single-bit error in a 7-bit block carrying 4 data bits. Adding one overall parity bit gives single-error correction with double-error detection, known as SECDED, the basis of ECC memory.

Hamming distance and capability

The code's minimum Hamming distance is 3, which is why it can correct one error or detect two. In general a distance of 2t+1 corrects t errors, tying correction power directly to how far apart valid codewords are.

Where it is used

ECC memory in servers and reliability-critical systems uses Hamming-based codes to survive occasional bit flips from radiation or noise, correcting them transparently so computation continues uninterrupted.

def hamming74_syndrome(bits):  # bits indexed 1..7
    s1 = bits[1]^bits[3]^bits[5]^bits[7]
    s2 = bits[2]^bits[3]^bits[6]^bits[7]
    s4 = bits[4]^bits[5]^bits[6]^bits[7]
    return s4*4 + s2*2 + s1  # 0 = no error, else position