skip to content

Why does a Fletcher-style checksum keep a second running sum, and which blind spot of a plain additive sum does that close?

level: middleimportance: should knowfreq 37%

answer

  1. one sum is order-blind
  2. second sum accumulates the first
  3. position becomes a weight
  4. early words weigh the most
  5. two additions per word

basics

~20 s

A Fletcher-style checksum accumulates a second sum over the running first sum, which weights each word by its distance from the end. That makes the check order-sensitive and closes a plain additive sum's blindness to reordered words, at two additions per word.

solid answer

~40 s

A plain sum is blind to order because addition commutes. A Fletcher-style check keeps two accumulators: `sum1` adds each word as it arrives, and `sum2` adds the current `sum1` after every word. Expanding that, `sum2` equals the sum of each word multiplied by the number of words from its position to the end, so an early word counts many times and a late one counts once. Swapping two distinct words therefore changes `sum2`, even though `sum1` is untouched. The two accumulators are concatenated into one check value of twice the accumulator width. The cost is one extra addition per word — still no division and no tables — and the blind spots that survive are those preserving **both** sums.

code

pseudocode · 6 lines
pseudocode
sum1 <- 0
sum2 <- 0
for each word w in block:
    sum1 <- (sum1 + w) mod M
    sum2 <- (sum2 + sum1) mod M
check <- (sum2 * (M + 1)) + sum1    # two accumulators concatenated

go deeper

for a junior

Know that some checksums are deliberately sensitive to the order of the data and a plain sum is not. The detail of how the second accumulator produces that is fair to leave for later.

for a middle

Be able to write the two-accumulator loop and expand it into the weighted form, then use it to explain exactly why swapping two words changes the value.

for a senior

Judge when the extra addition per word is worth buying: plausible reordering, truncation or padding on the path. Name what still slips past so the choice does not read as a guarantee.

for a principal

Frame checks by the shape of what they are blind to rather than by width. The design question is which corruption classes the path can produce, and the cheapest computation that makes those classes visible.

## The hole being closed A plain additive checksum is a function of the multiset of covered words: addition commutes, so any permutation of the words produces the same total. A frame whose words arrive out of order, a payload assembled from segments stitched together wrongly, a pair of fields transposed by a framing fault — all pass a plain sum untouched. Widening the sum does not help, because the property comes from the operation rather than the width. To see order, the computation has to depend on **where** a word sits, not merely on which words are present. ## What the second sum computes A Fletcher-style check keeps two accumulators over the same pass: - `sum1` is the running total of the words themselves, reduced modulo some `M`; - `sum2` adds the current value of `sum1` after every word. Expand `sum2` for a block of n words. After word 1, `sum1` is w1; after word 2 it is w1 + w2; and so on. Summing those partial totals gives `sum2 = n*w1 + (n-1)*w2 + ... + 1*wn` Each word is multiplied by the number of words from its own position to the end of the block. The first word carries the largest weight and the last word carries a weight of one. That positional weight is the entire mechanism. ## Why that detects reordering Swap two words at positions i and j with i < j. The multiset is unchanged, so `sum1` is unchanged. But `sum2` changes by `(n-i+1 - (n-j+1)) * (wj - wi)`, which is `(j - i) * (wj - wi)`. That is non-zero whenever the two words differ in value and the modulus does not happen to divide it, so the swap is visible. The same reasoning covers a rotated block, a block reassembled from segments in the wrong sequence, and a word shifted from one position to another. It also changes the effect of inserted or removed padding. A zero word contributes nothing to `sum1`, but it does add the current `sum1` into `sum2` one extra time — so an inserted zero word is detected **unless** the running `sum1` happens to be zero at that point. One widely used 32-bit variant initialises `sum1` to one precisely so that leading zero words cannot hide behind a zero running total, and it reduces both accumulators modulo the prime 65521 rather than 65535. ## Cost and shape | Check | Work per word | Sees order | Result width | |---|---|---|---| | single parity bit | one XOR | no | 1 bit | | plain additive sum | one addition | no | accumulator width | | two-sum, Fletcher-style | two additions | yes | twice the accumulator width | The two accumulators are concatenated to form the transmitted value: with two 8-bit sums the check is 16 bits wide, and with two 16-bit sums it is 32 bits. The arithmetic stays trivial — no division, no lookup tables, and the per-word cost is one addition more than a plain sum — which is the reason this shape exists at all. It is the cheapest way to buy order sensitivity. ## What it still misses A two-sum check is not a general integrity guarantee. What survives is any corruption that preserves **both** accumulators: 1. a pair of changes `+d` at one position and `-d` at another whose weighted contributions also cancel, which happens when the weight difference times `d` is a multiple of the modulus; 2. an inserted or deleted zero word at a point where the running first sum is zero; 3. a wholly different block that happens to reach the same pair of sums, which the width makes unlikely but not impossible; 4. any rewrite by a party that simply recomputes the field afterwards — the check certifies the last writer, never the author. So the honest claim is narrow and worth making precisely: the second sum closes the **order** hole and improves the odds on the others; it does not turn the check into a guarantee. ## Choosing it Reach for a two-sum check when word reordering, truncation or padding are plausible on the path and the budget forbids a heavier check. Reach for a plain sum when the expected fault is unstructured noise and incremental update matters more than order sensitivity. And state which of the two you chose and why — an interviewer asking this question is testing whether you know that checks differ in the **shape** of what they are blind to, not merely in how many bits they emit.

  • What does a two-sum checksum still fail to detect?
    Anything preserving both accumulators: a cancelling pair whose weighted contributions also cancel modulo the chosen modulus, a zero word inserted where the running first sum happens to be zero, and a rewrite by anyone who recomputes the field. Order sensitivity is what the second sum buys — not a general guarantee.
  • Why do some variants reduce modulo a prime such as 65521 instead of 65535?
    Modulo 65535, the all-zero and all-ones words are the same value, so swapping one for the other is invisible. A prime modulus removes that specific equivalence and spreads the accumulators more evenly, at the cost of a slightly narrower value range and a reduction step. It does not remove the structural blind spots.
  • Does the second sum let a receiver repair a corrupted word?
    No. Two sums over a whole block still produce a verdict, not a location, and the pair does not carry enough redundancy to reconstruct a word. Detection stays detection; repairing in place requires a code designed to carry the repair information, which costs considerably more.

saying these in an interview costs you the question

  • Says the second sum makes the check able to correct errors
  • Claims a two-sum checksum has no blind spots left
  • Believes the second sum merely widens the value
  • Assumes both accumulators weight every word equally
  • Thinks a position-weighted sum resists deliberate rewriting