skip to content

What does the claim that a 16-bit check field misses only one bad block in 65,536 actually assume?

level: seniorimportance: nice to knowfreq 29%

answer

  1. a probability with an assumption attached
  2. random errors versus real ones
  3. blind spots have probability one
  4. independence of the recomputed value
  5. multiply by the block rate

basics

~20 s

The 2^-k figure assumes corruption drives the recomputed check to a value independent of and uniform over the correct one. Structured errors — reordered words, cancelling pairs, faults outside the covered span — break that assumption and pass every time, not one time in 65,536.

solid answer

~40 s

For a k-bit check the residual figure is `2^-k`, which is `1/65536` at k = 16. It comes from a single modelling step: assume a corrupt block's recomputed value is spread uniformly over all `2^k` possibilities and independent of the transmitted one, so the chance it happens to collide is one in `2^k`. Real corruption is not like that. Every structural blind spot — a word swap, a cancelling pair, an inserted zero word — leaves the value **identically** equal, so it passes with probability one regardless of width. The figure also says nothing about corruption outside the covered span. Finally it is a per-block probability, so it must be multiplied by the block rate before it means anything operationally.

go deeper

for a junior

Take away one idea: a residual-error figure is a model output, not a promise, and some corruptions slip past a check every single time rather than occasionally.

for a middle

Be able to state where 2^-k comes from — a uniform, independent recomputed value — and contrast it with a structural blind spot, which is missed with certainty at any width.

for a senior

Do the conversion out loud: residual probability times corrupt-block rate gives an expected interval, and that interval is what determines whether a width is adequate for this path.

for a principal

Decide what the figure may be used to justify. It sizes the random-error term only; durability claims that lean on it while ignoring uncovered spans and structural holes are the ones that fail in production.

## Where the figure comes from Take a block that has been corrupted. Recompute its check and compare with the transmitted value. If the corruption is thought of as replacing the recomputed value with a **uniformly random** draw from all `2^k` possible values, **independent** of the value the sender wrote, the chance of a collision — a corrupt block that passes — is `1/2^k`. For a 16-bit field that is `1/65536`; for a 32-bit field, about one in four billion. That is the whole derivation. It is one modelling assumption wearing an engineering number. ## The assumption, stated plainly > Corruption randomises the recomputed check independently of the correct one. Write it out and the failure modes become obvious, because the assumption is a statement about the **error process**, not about the check. The check contributes only the width `k`. ## How real error patterns break it - **The structural blind spots are not collisions.** Swapping two words leaves an additive sum identically equal. Inserting a word that contributes nothing does the same, as does a pair of changes that cancel. These pass with probability one — not `2^-16` — and widening the field to 32 bits does not move that number at all, because it is set by the algebra rather than the width. - **Errors cluster.** Noise arrives in bursts and faults are systematic: a marginal connector, a lane that fails under temperature, a producer writing past the end of a buffer. Independence across bits, and across blocks, is exactly what such faults violate. - **The covered span is finite.** Corruption before the value is computed or after it is verified is not in the model at all. A block corrupted in the producer's buffer is summed as intended and passes with probability one. - **The population is filtered.** The figure conditions on a block already being corrupt. Comparing it against a raw block count, rather than against the corrupt-block count, is off by the corruption rate itself. ## From a probability to a rate A per-block probability means nothing until it meets a block rate. Work it through: 1. a path carries 1,000,000 blocks per second; 2. one block in 100,000 is corrupted, so 10 corrupt blocks arrive per second; 3. under the random-error assumption, a 16-bit check lets `10 / 65536`, about `1.5e-4`, of them through per second; 4. that is one undetected corrupt block roughly every 6,554 seconds — under two hours. | Check width | Undetected blocks at 10 corrupt/s | Expected interval | |---|---|---| | 16 bits | 1.5e-4 per second | about 1.8 hours | | 32 bits | 2.3e-9 per second | over a decade | The table is the honest use of the figure: it converts a width into an operating horizon, **for the errors the assumption covers**. It says nothing whatever about the structural holes, which sit outside the model and are unaffected by either row. ## What the number is good for It is a **sizing tool**, not a guarantee. Use it to answer: given this block rate and this corruption rate, is a check of this width plausibly adequate for the errors that behave randomly? Do not use it as a floor on how often corrupt data reaches the consumer, because the blind spots and the uncovered span both sit outside it and both are far more likely to hurt in practice. The corresponding measurement trap is that you cannot observe your own undetected-error rate from the passing blocks — by definition they look fine. Evidence has to come from elsewhere: an independent check computed over a wider span, a comparison at the true consumer against the true producer, or a deliberate corruption test that proves the verification path even runs. ## In the interview The weak answer quotes `1/65536` as a property of the check. The strong answer names the assumption behind it in one sentence, points out that the structural blind spots have probability one and are unaffected by width, and multiplies the figure by a block rate before drawing any operational conclusion from it.

  • How do you turn a per-block residual probability into an expected time between undetected corruptions?
    Multiply by the corrupt-block rate. At 10 corrupt blocks per second, a 16-bit check admits about 1.5e-4 per second under the random-error assumption — roughly one every 1.8 hours. Moving to 32 bits divides that by 65,536, pushing it past a decade, but only for errors the assumption actually covers.
  • Does widening the check field help against the structural blind spots?
    No. Reordered words, cancelling pairs and zero-word insertions leave an additive sum identically equal, so they are missed with probability one at any width. Width only shrinks the random-collision term. Closing a structural hole requires a different computation shape — position weighting, for instance — not more bits.
  • Why can you not measure your own undetected-error rate from production traffic?
    Undetected corruption passes the check by definition, so it is invisible to the thing you would measure with. Evidence has to come from outside: an independent check over a wider span, a comparison at the true consumer against the true producer, or a deliberate corruption test proving the verification path runs at all.

saying these in an interview costs you the question

  • Treats one in 65,536 as a guaranteed worst case
  • Assumes real error patterns are uniformly random and independent
  • Ignores block rate when turning a probability into a frequency
  • Thinks a wider check field closes the structural blind spots
  • Believes an undetected-error rate can be measured from passing blocks