A block code's minimum Hamming distance is 3 - how many flipped bits can it correct, and how many can it merely detect?

middlemust knowfreq 62%

answer

count disagreeing positions, not numeric gap
smallest gap between any two codewords
noticing is cheaper than repairing
one spare step to detect
balls around codewords must not overlap

basics

~20 s

Minimum distance 3 corrects one flipped bit or detects two, but not both at once. Correcting t flips needs distance at least 2t+1; detecting e flips needs only e+1. Correction costs about twice the distance detection does.

solid answer

~50 s

The Hamming distance between two equal-length bit strings is the number of positions where they differ, and a code's minimum distance d is the smallest such distance over every pair of distinct codewords. Detecting corruption only requires the received word to fall outside the codeword set, so detecting up to e flips needs d >= e + 1. Repairing it requires the received word to stay strictly closer to the codeword that was sent than to any other, so correcting up to t flips needs d >= 2t + 1. At d = 3 you therefore choose one behaviour: decode to the nearest codeword and correct one flip, or refuse to correct and detect two. Doing both - correct one and still detect two - needs d >= t + e + 1 = 4, which is why single-correct double-detect codes are built at distance 4.

The Hamming distance between two equal-length bit strings is the number of positions where they differ, and a code's **minimum distance** `d` is the smallest such distance over every pair of distinct codewords. Detecting corruption only requires the received word to fall outside the codeword set, so detecting up to `e` flips needs `d >= e + 1`. Repairing it requires the received word to stay strictly closer to the codeword that was sent than to any other, so correcting up to `t` flips needs `d >= 2t + 1`. At `d = 3` you therefore choose one behaviour: decode to the nearest codeword and correct one flip, or refuse to correct and detect two. Doing both - correct one *and* still detect two - needs `d >= t + e + 1 = 4`, which is why single-correct double-detect codes are built at distance 4.

go deeper

for a junior

Recall the definition first: distance is the number of positions where two equal-length bit strings differ, and a code's minimum distance is the smallest such gap between legal words. Everything else in this topic is built on that one count.

for a middle

Be able to state both bounds and say why they differ: detection needs the word to leave the codeword set, correction needs it to stay nearer the sent word than any other. Work a concrete case at distance 3 and 4 without hesitating.

for a senior

Show that you treat correcting mode versus detecting mode as an operational decision. Name the failure that matters - a distance-3 decoder in correcting mode can return silently wrong data after two flips - and say how you would find out that it happened.

for a principal

The judgement is how much silent-corruption risk the platform will accept for how much overhead, and whether repair belongs at the word level or at a layer that can retry. Defend a distance target as a reliability budget, not as a formula.

What the distance actually measures

The Hamming distance between two bit strings of the same length is the count of positions where they disagree. 1011001 and 1001001 disagree only at position 3, so their distance is 1. The measure ignores what the bits mean and how far apart the words are as numbers - only the number of disagreeing positions counts, because a corrupting channel works one position at a time.

A block code designates a small set of legal words, the codewords, out of all 2^n words of length n. The code's minimum distance d is the smallest Hamming distance between any two distinct codewords. Almost everything a code can promise about bit flips follows from that single number:

Each flipped bit moves the received word exactly one step away from what was sent.
f flips move it f steps, along some path the decoder cannot see.
The decoder never sees the sent word; it sees only where the received word landed and which words are legal.

Detection needs one spare step

To detect up to e flips, every word reachable within e steps of a codeword must fail to be a codeword itself. The nearest other codeword sits d steps away, so no run of e flips can land exactly on a different legal word as long as e is smaller than d:

detect up to e flips when and only when d >= e + 1.

Detection is the cheap promise because the decoder answers one yes/no question: is this word in the set?

Correction needs the word to stay nearer home

To correct up to t flips, the received word must remain strictly closer to the codeword that was sent than to any other, so that nearest-codeword decoding picks the original. Picture a ball of radius t drawn around every codeword; correction is reliable exactly when those balls never overlap. Two codewords d apart have disjoint balls when 2t < d:

correct up to t flips when and only when d >= 2t + 1.

Correction costs roughly twice the distance of detection because the decoder must not merely notice that the word is wrong - it must decide which way it is wrong. Asking for both behaviours at once is a third bound: correcting t while still detecting a larger e needs d >= t + e + 1.

minimum distance d	corrects up to	detects up to (no correction)	correct 1 and detect 2 together
2	0 flips	1 flip	no
3	1 flip	2 flips	no
4	1 flip	3 flips	yes
5	2 flips	4 flips	yes

Reading a row of that table

Take the distance the code actually achieves - it is a property of the chosen codeword set, not of how many check bits you bolted on.
Pick the behaviour the system needs: repair in place, or report and let a higher layer retry.
Check the matching bound. If the mode you want is not covered, the code is the wrong code; you cannot decode your way past the distance.

The choice at d = 3, in a memory word

A memory module that protects each stored word with a distance-3 code has one decision to make in its decoder, and it is a design decision rather than a computation:

Correcting mode. One flipped cell is repaired transparently and the read succeeds. The price is that two flipped cells land within one step of some third codeword, so the decoder may hand back confidently wrong data. Silent corruption is the worst failure a store can have.
Detecting mode. The decoder refuses to repair anything and reports any word that is not legal. One or two flips are caught, but a single flip - the overwhelmingly common case - now fails a read that could have been served.

Neither mode is wrong; they trade availability against the risk of silent wrong answers. What you cannot do at d = 3 is have both, and a candidate who claims otherwise has not separated the two bounds.

Common confusions worth naming

Distance is a property of the code, not of the word you received. A received word has a distance to each codeword; the code has one minimum distance.
More check bits do not automatically buy distance. Badly chosen checks can leave two codewords one step apart no matter how many bits you spend.
The bounds are guarantees, not descriptions of typical behaviour. A distance-3 code often happens to notice three flips; it just does not promise to.

## What the distance actually measures The **Hamming distance** between two bit strings of the same length is the count of positions where they disagree. `1011001` and `1001001` disagree only at position 3, so their distance is 1. The measure ignores what the bits mean and how far apart the words are as numbers - only the number of disagreeing positions counts, because a corrupting channel works one position at a time. A **block code** designates a small set of legal words, the **codewords**, out of all `2^n` words of length `n`. The code's **minimum distance** `d` is the smallest Hamming distance between any two distinct codewords. Almost everything a code can promise about bit flips follows from that single number: - Each flipped bit moves the received word exactly one step away from what was sent. - `f` flips move it `f` steps, along some path the decoder cannot see. - The decoder never sees the sent word; it sees only where the received word landed and which words are legal. ## Detection needs one spare step To **detect** up to `e` flips, every word reachable within `e` steps of a codeword must fail to be a codeword itself. The nearest other codeword sits `d` steps away, so no run of `e` flips can land exactly on a different legal word as long as `e` is smaller than `d`: > detect up to `e` flips when and only when `d >= e + 1`. Detection is the cheap promise because the decoder answers one yes/no question: is this word in the set? ## Correction needs the word to stay nearer home To **correct** up to `t` flips, the received word must remain strictly closer to the codeword that was sent than to any other, so that nearest-codeword decoding picks the original. Picture a ball of radius `t` drawn around every codeword; correction is reliable exactly when those balls never overlap. Two codewords `d` apart have disjoint balls when `2t < d`: > correct up to `t` flips when and only when `d >= 2t + 1`. Correction costs roughly twice the distance of detection because the decoder must not merely notice that the word is wrong - it must decide *which way* it is wrong. Asking for both behaviours at once is a third bound: correcting `t` while still detecting a larger `e` needs `d >= t + e + 1`. | minimum distance d | corrects up to | detects up to (no correction) | correct 1 and detect 2 together | |---|---|---|---| | 2 | 0 flips | 1 flip | no | | 3 | 1 flip | 2 flips | no | | 4 | 1 flip | 3 flips | yes | | 5 | 2 flips | 4 flips | yes | ## Reading a row of that table 1. Take the distance the code actually achieves - it is a property of the chosen codeword set, not of how many check bits you bolted on. 2. Pick the behaviour the system needs: repair in place, or report and let a higher layer retry. 3. Check the matching bound. If the mode you want is not covered, the code is the wrong code; you cannot decode your way past the distance. ## The choice at d = 3, in a memory word A memory module that protects each stored word with a distance-3 code has one decision to make in its decoder, and it is a design decision rather than a computation: - **Correcting mode.** One flipped cell is repaired transparently and the read succeeds. The price is that two flipped cells land within one step of some *third* codeword, so the decoder may hand back confidently wrong data. Silent corruption is the worst failure a store can have. - **Detecting mode.** The decoder refuses to repair anything and reports any word that is not legal. One or two flips are caught, but a single flip - the overwhelmingly common case - now fails a read that could have been served. Neither mode is wrong; they trade availability against the risk of silent wrong answers. What you cannot do at `d = 3` is have both, and a candidate who claims otherwise has not separated the two bounds. ## Common confusions worth naming - **Distance is a property of the code, not of the word you received.** A received word has a distance *to* each codeword; the code has one minimum distance. - **More check bits do not automatically buy distance.** Badly chosen checks can leave two codewords one step apart no matter how many bits you spend. - **The bounds are guarantees, not descriptions of typical behaviour.** A distance-3 code often happens to notice three flips; it just does not promise to.

What distance does a code need to correct one flip and still detect two in the same word?
Distance 4. The combined bound is `d >= t + e + 1`, so correcting `t = 1` while detecting `e = 2` needs `d >= 4`. That is exactly what single-correct double-detect codes are built for: at distance 3 the double-flip pattern sits one step from another codeword and gets miscorrected, while at distance 4 it sits two steps from its neighbours, which the decoder can recognise as ambiguous and refuse to repair.
If a code has minimum distance 5, what are its options?
It can correct up to two flips (`5 >= 2*2 + 1`), or detect up to four without correcting (`5 >= 4 + 1`), or mix the two: correct one and detect three, since `1 + 3 + 1 = 5`. The decoder's mode is a configuration choice; the distance only fixes which combinations are achievable.
Does the minimum distance tell you anything about how many bits the code spends?
Not directly. Distance constrains the codeword set, and the cost shows up separately as the code rate - data bits over total bits. Two codes of the same length and distance can carry different amounts of data, and a code with many check bits can still have a poor distance if the checks overlap badly.

Think of codewords as towns on a grid and each flipped bit as one step you are forced to take. Detecting asks only whether you have left town; correcting asks which town you must have started in, so the towns have to sit more than twice your step budget apart.

saying these in an interview costs you the question

Says a distance-3 code both corrects one flip and detects two
Computes distance as the numeric difference between two codewords
Claims correcting t flips needs only distance t+1
Believes more check bits automatically raise the minimum distance
Assumes a distance-3 decoder can tell one flip from two
Thinks the bounds describe typical behaviour rather than guarantees

A block code's minimum Hamming distance is 3 - how many flipped bits can it correct, and how many can it merely detect?

§ answer

basics

solid answer

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What the distance actually measures

Detection needs one spare step

Correction needs the word to stay nearer home

Reading a row of that table

The choice at d = 3, in a memory word

Common confusions worth naming

▾common follow-ups3 questions

▾analogy~20 s

▾red flags6 flags

What the distance actually measures

Detection needs one spare step

Correction needs the word to stay nearer home

Reading a row of that table

The choice at d = 3, in a memory word

Common confusions worth naming

answer

go deeper