Hamming Codes: Fixing a Flipped Bit Without Asking Again

Redundancy placed on purpose

A Hamming code adds carefully placed extra bits — parity bits — to a block of data bits so that a single flipped bit can not only be detected but located and corrected without ever resending the data. Richard Hamming developed the scheme in 1950 at Bell Labs after growing frustrated that an early relay computer would abort an entire multi-day job over a single-bit error it could detect but not fix. The classic (7,4) Hamming code takes 4 data bits and adds 3 parity bits to make a 7-bit codeword, at the cost of paying for redundancy, buying automatic correction.

Placing parity bits at powers of two

The trick is where the parity bits go. In a 7-bit word numbered 1 through 7, positions 1, 2 and 4 — the powers of two — hold parity bits; positions 3, 5, 6 and 7 hold data. Each parity bit covers a specific, overlapping subset of positions determined by its own bit in the binary representation of the position number: parity bit at position 1 covers every position whose binary representation has bit 0 set (1, 3, 5, 7), parity bit at position 2 covers positions with bit 1 set (2, 3, 6, 7), and parity bit at position 4 covers positions with bit 2 set (4, 5, 6, 7).

position:   1  2  3  4  5  6  7
content:    p1 p2 d1 p4 d2 d3 d4

p1 checks positions 1,3,5,7   (bit 0 of position set)
p2 checks positions 2,3,6,7   (bit 1 of position set)
p4 checks positions 4,5,6,7   (bit 2 of position set)

each pi is set so the parity (XOR) of its covered positions is even

This overlapping design is the entire trick: each data bit is covered by a unique combination of parity bits, so an error in that one data bit disturbs a unique, identifiable subset of the parity checks.

The syndrome: three checks that spell out a position

On the receiving end, recompute the three parity checks over the received word. If a check comes out even, its result bit is 0; if odd, it's 1. Stack the three results with p4's bit as the most significant: the resulting 3-bit number — the syndrome — is either 0 (no error) or, remarkably, the exact position of the flipped bit, because the covering sets were built directly from the binary digits of each position.

syndrome = (check_p4 << 2) | (check_p2 << 1) | check_p1

syndrome == 0   → no error detected
syndrome == k   → bit at position k is wrong — flip it and you're done

No lookup table, no retransmission — the syndrome computation is itself the address of the fault. This is what people mean by single-error correction: the code corrects exactly one flipped bit per codeword automatically.

SECDED: adding a fourth bit for double-error detection

The plain (7,4) Hamming code has a blind spot: if two bits flip at once, the syndrome still points confidently at some position — the wrong one — and the decoder corrects a bit that was never wrong, silently making the error worse. The fix, used in essentially every real deployment, is SECDED (single error correction, double error detection): add one more overall parity bit covering the entire word including the other parity bits. A single-bit error flips the overall parity and gives a nonzero syndrome — correct as before. A double-bit error gives a nonzero syndrome (falsely pointing somewhere) but leaves the overall parity unchanged, and that mismatch between 'syndrome says an error' and 'overall parity says none' is the unambiguous signature of an uncorrectable double error, so the decoder flags it instead of miscorrecting.

Where it actually runs

SECDED Hamming codes protect ECC RAM in servers and workstations against cosmic-ray and alpha-particle bit flips, satellite and deep-space telemetry links where retransmission can cost minutes of round-trip light delay, and NAND flash storage controllers. The scheme generalizes beyond (7,4): a Hamming code with r parity bits protects 2^r − 1 total bits (2^r − r − 1 data bits), so (15,11), (31,26) and (63,57) codes trade a smaller relative overhead for the same single-bit-correction guarantee as blocks get larger — at the cost of a larger blast radius if a second bit happens to flip inside the same enlarged block.

Frequently asked questions

Try it live

Everything above runs in your browser — open Hamming Codes and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.