Hamming Code Parity Bits

Richard Hamming had weekend access to a relay computer that would find an error, halt, and throw away two days of work. His response in 1950 was a code that not only detects a single-bit error but says exactly which bit it was. The trick is that $r$ parity bits produce an $r$-bit syndrome with $2^r$ possible values, and those values must cover every one of the $m + r$ bit positions plus one spare meaning "nothing is wrong". Hence $2^r \ge m + r + 1$.

Four data bits need three parity bits, giving the famous (7,4) code where 43% of the transmission is overhead. Eleven data bits need four, giving (15,11) at 27%. Two hundred and forty-seven data bits need eight, giving (255,247) at barely 3%. The overhead shrinks logarithmically while the payload grows exponentially, which is why error correction is nearly free on large blocks and expensive on small ones. Real ECC memory uses (72,64), spending 8 bits to protect 64.

Two things get missed. First, plain Hamming corrects one error and is fooled by two: a double bit flip produces a syndrome pointing confidently at some innocent third bit, which it then corrects, leaving three errors. That is why production ECC adds one more parity bit for the SECDED variant, single error correction with double error detection. Second, the $r$ in the inequality appears on both sides, because the parity bits must be able to identify errors in themselves as well. Forget that and you will size the code one bit short at exactly the boundary cases.