the Hamming code
/ HAM-ing /
A single parity bit can tell you that one bit flipped, but not which one — so it can detect but not fix. Richard Hamming's insight was to use several parity bits, each watching an overlapping subset of the data bits, arranged so that when an error occurs the pattern of failed checks spells out, in binary, the exact position of the broken bit. Knowing the position, you just flip that bit back. The Hamming code is the classic forward-error-correcting code that corrects any single-bit error.
Here is the mechanism in the small Hamming(7,4) case: 7 bits are sent, of which 4 carry data and 3 are parity, placed at positions 1, 2, and 4 (the powers of two). Each parity bit covers a specific overlapping group of positions. At the receiver, each parity check either passes (0) or fails (1). Read the three results as a 3-bit binary number, the syndrome. If it is 000, no error; otherwise its value, say 101 = 5, points straight at position 5 as the flipped bit, which the receiver simply inverts. Three checks distinguish all seven positions plus no-error, because three bits encode eight possibilities.
The Hamming code matters as the cleanest illustration of how spending a few redundant bits buys outright correction, and the idea scales up to the powerful codes used in RAM (ECC memory), storage, and communications. The honest limit: plain Hamming corrects exactly ONE bit error per block. Two errors in the same block will mislead it into correcting the wrong bit, making things worse. An extra overall parity bit (a SECDED code) lets it at least DETECT, though not correct, double errors.
In a Hamming(7,4) block the receiver runs three parity checks and gets results 1, 0, 1. Read as binary that is 101 = 5, so bit 5 flipped; the receiver inverts bit 5 and the original 4 data bits are recovered — no resend, no questions asked.
The failed-check pattern (the syndrome) is the binary address of the broken bit.
Basic Hamming corrects exactly one error per block; two errors fool it into 'fixing' the wrong bit. Adding one more parity bit (SECDED) lets it detect, but still not correct, a double error.