Why does a single-error-correcting block code cost proportionally fewer check bits as the protected word grows wider?

## Check bits address, they do not guard The intuition that goes wrong here is one-check-per-data-bit: a mental model where each check bit stands watch over some piece of the payload, so more payload means proportionally more watchers. That is not what the checks do. Their job is to produce an **address** - a value that identifies which single position needs inverting - and addresses are cheap because they scale by exponent. Count what the decoder must be able to say for a single-error-correcting code over `n = k + r` bits: - one outcome meaning **no flip seen**; - one distinct outcome per position that might have flipped, and every position counts, because the check bits are corruptible too. With `r` binary checks there are `2^r` outcomes, one of which is spent on "clean". So the code is only possible when > `2^r - 1 >= n = k + r`, equivalently `2^r >= k + r + 1`. ## Solving it at real widths | data bits k | check bits r | total n | checks as share of data | share of the whole word | |---|---|---|---|---| | 4 | 3 | 7 | 75% | 43% | | 8 | 4 | 12 | 50% | 33% | | 16 | 5 | 21 | 31% | 24% | | 32 | 6 | 38 | 19% | 16% | | 64 | 7 | 71 | 11% | 10% | Each doubling of the payload adds roughly **one** check bit, because one more check doubles the number of addressable positions. Add the extra overall parity bit for single-correct double-detect and the 64-bit case becomes 8 check bits in a 72-bit word - 12.5 percent - which is why wide-word protection is affordable and narrow-word protection is not. Two details keep the claim honest: 1. **The inequality is a necessary condition, not a construction.** It says how few checks could possibly suffice; a code achieving the bound exactly exists only at the widths where `n = 2^r - 1`, and at other widths the code is shortened and leaves some addresses unused. 2. **The bound is specific to correcting one flip.** Correcting two means naming *pairs* of positions, and the number of pairs grows quadratically, so the check count grows far faster than one per doubling. ## The cost that moves the other way Wider words are cheaper per bit and more fragile per word. Protection is applied per word, so: - A wider word contains more cells, so it is more likely to hold at least one flip at any moment. - The failure that matters is **two flips in one word**, and widening the word makes two independent flips more likely to share one. - When a word does fail uncorrectably, more payload is lost at once, so the blast radius of a single event grows with the width. So the width choice is not "as wide as possible". It is a balance between the overhead rate, which falls with width, and the uncorrectable-event rate and blast radius, which rise with it. In practice the width is usually fixed by the access granularity of the surrounding system, and the code is then chosen to fit that width rather than the reverse. ## How this is asked An interviewer rarely wants the algebra. The probes are: - **"Why is protection not simply a duplicate copy?"** Duplication costs 100 percent and still only *detects* a disagreement without saying which copy is right; the addressing code costs a logarithm and repairs. - **"Why do narrow words get protected so rarely?"** Because at 4 or 8 data bits the overhead is 75 or 50 percent, which is close to the cost of outright duplication with less benefit. - **"What breaks if you just keep widening?"** The overhead rate keeps improving and the reliability per word keeps degrading, and the second effect eventually dominates. The short version worth being able to say out loud: check bits grow with the logarithm of the word, payload grows with the word, so the ratio between them falls - and the thing that stops you from widening forever is not arithmetic but the probability of a second flip landing in the word you just made bigger.