Why does adding one overall parity bit to a distance-3 code let a memory controller correct one flip and detect two?

seniorshould knowfreq 41%

answer

one more bit over the whole word
odd or even flip count, nothing more
distance climbs from three to four
two signals disagreeing is the evidence
three flips remain outside the promise

basics

~20 s

The extra bit covers every position, so it fails on an odd number of flips and passes on an even one. That raises the minimum distance from 3 to 4 and lets the decoder separate one flip from two instead of miscorrecting the pair.

solid answer

~40 s

A distance-3 code corrects one flipped bit, but a double flip lands one step from some other codeword, so the decoder repairs an innocent position and returns a word that is legal and wrong. Adding one overall parity bit across the whole codeword raises the minimum distance to 4: every pair of codewords now differs in an even number of positions, and no two differ in fewer than four. The decoder then reads two independent signals - the syndrome from the original checks, and the overall parity. Odd parity with a nonzero syndrome means one flip, which it repairs; even parity with a nonzero syndrome means an even number of flips, at least two, which it refuses to repair and reports as uncorrectable. That is exactly the single-correct double-detect behaviour, bought for one bit.

A distance-3 code corrects one flipped bit, but a double flip lands one step from some other codeword, so the decoder repairs an innocent position and returns a word that is legal and wrong. Adding one **overall parity bit** across the whole codeword raises the minimum distance to 4: every pair of codewords now differs in an even number of positions, and no two differ in fewer than four. The decoder then reads two independent signals - the syndrome from the original checks, and the overall parity. Odd parity with a nonzero syndrome means one flip, which it repairs; **even parity with a nonzero syndrome means an even number of flips, at least two**, which it refuses to repair and reports as uncorrectable. That is exactly the single-correct double-detect behaviour, bought for one bit.

code

pseudocode · 11 lines

pseudocode

// c = syndrome recomputed from the distance-3 checks
// p = parity over ALL bits, including the overall parity bit
if p is even and c is 0:
    accept word unchanged
else if p is odd and c is 0:
    accept word                        // the overall parity bit itself flipped
else if p is odd:
    flip bit at position c             // single flip, repairable
    accept repaired word
else:
    report uncorrectable               // even flips, at least two

go deeper

for a junior

Recall the headline: one extra bit taken over the whole word moves a code from correct-one to correct-one-and-detect-two. It works because parity over everything reveals whether the number of flips was odd or even.

for a middle

Explain why the minimum distance goes from 3 to 4, and walk the four combinations of overall parity and syndrome, naming the action for each. The even-parity-with-nonzero-syndrome case is the one that earns the bit.

for a senior

Demonstrate the operational consequence: a double flip that used to be served as data now becomes a surfaced hard failure, so the layer above needs a plan. Also state the limit honestly - three flips can still be miscorrected.

for a principal

The trade is availability against silent corruption, and it is a policy call per class of data. Decide where uncorrectable events are handled, and insist that corrected-error counts are exported, since they are the cheapest predictive signal the system has.

The gap the extra bit closes

At minimum distance 3 a code corrects one flipped bit per word. The uncomfortable part is what it does with two. Two flips move the received word two steps from the sent codeword, which can leave it one step from a different codeword; the decoder, which only ever asks "which codeword is nearest?", repairs that one bit and reports success. The word it hands back is legal, three bits from the truth, and indistinguishable from a good read. Silent wrong data is the failure a store least wants, and it is not rare enough to ignore once flips accumulate.

The fix is one bit. Append an overall parity bit whose value makes the parity of the entire extended word even. Its effect:

Every codeword of the extended code now has an even number of ones.
Two codewords that were an odd distance apart before must now differ in one more position, because their overall parities differed.
The minimum distance rises from 3 to 4, and every pairwise distance becomes even.

Distance 4 is precisely the combined bound d >= t + e + 1 with t = 1 and e = 2: correct one, detect two.

How the decoder uses two signals

The decoder computes two things: the syndrome c from the original checks, which names a position when it is nonzero, and the overall parity p over every bit including the new one, which reports only whether the number of flips is odd or even. Neither alone is enough; the pair is.

overall parity p	syndrome c	interpretation	action
even	zero	no flips seen	accept
odd	nonzero	one flip, at the position c names	repair, accept
odd	zero	the overall parity bit itself flipped	accept the data
even	nonzero	an even number of flips, at least two	report uncorrectable

The fourth row is the whole point. Under the unextended code that combination was invisible - there was no p to contradict the syndrome - and the word was miscorrected. Now the contradiction between "parity says even" and "syndrome says something moved" is itself the evidence, and the decoder can refuse.

What it does and does not guarantee

One flip is repaired, wherever it lands - data, check bit, or the overall parity bit itself.
Two flips are detected and refused. They are never repaired, and never returned as good data.
Three flips are outside the guarantee. They produce odd parity with a nonzero syndrome, which is exactly the signature of a single flip, so the word is silently miscorrected. The code promises correct-one and detect-two; it does not promise anything about three, and claiming it catches every odd count overstates it.

That third point is the honest limit and the one candidates most often get wrong in the optimistic direction.

What it costs, and why systems pay it

One bit per word, on top of the check bits the distance-3 code already spent. On a wide word that is a rounding error against the total overhead.
Nothing in decode latency worth naming: the overall parity is one more parity over bits already being read.
An availability change, which is the real design decision. A double flip that used to be served as data is now a hard failure surfaced to the layer above. That is the correct trade for stored data whose wrongness would propagate, and it means the layer above needs a retry, a redundant copy, or a way to fail loudly.

The operational payoff is not only the caught double flip. A decoder that reports corrected single flips as well as uncorrectable ones turns the code into a sensor: rising correctable counts on one region are an early warning that arrives long before the first uncorrectable event, which is a signal a silent corrector throws away.

## The gap the extra bit closes At minimum distance 3 a code corrects one flipped bit per word. The uncomfortable part is what it does with two. Two flips move the received word two steps from the sent codeword, which can leave it one step from a *different* codeword; the decoder, which only ever asks "which codeword is nearest?", repairs that one bit and reports success. The word it hands back is legal, three bits from the truth, and indistinguishable from a good read. Silent wrong data is the failure a store least wants, and it is not rare enough to ignore once flips accumulate. The fix is one bit. Append an **overall parity bit** whose value makes the parity of the entire extended word even. Its effect: - Every codeword of the extended code now has an even number of ones. - Two codewords that were an odd distance apart before must now differ in one more position, because their overall parities differed. - The minimum distance rises from 3 to 4, and every pairwise distance becomes even. Distance 4 is precisely the combined bound `d >= t + e + 1` with `t = 1` and `e = 2`: correct one, detect two. ## How the decoder uses two signals The decoder computes two things: the **syndrome** `c` from the original checks, which names a position when it is nonzero, and the **overall parity** `p` over every bit including the new one, which reports only whether the number of flips is odd or even. Neither alone is enough; the pair is. | overall parity p | syndrome c | interpretation | action | |---|---|---|---| | even | zero | no flips seen | accept | | odd | nonzero | one flip, at the position c names | repair, accept | | odd | zero | the overall parity bit itself flipped | accept the data | | even | nonzero | an even number of flips, at least two | report uncorrectable | The fourth row is the whole point. Under the unextended code that combination was invisible - there was no `p` to contradict the syndrome - and the word was miscorrected. Now the contradiction between "parity says even" and "syndrome says something moved" is itself the evidence, and the decoder can refuse. ## What it does and does not guarantee 1. **One flip is repaired**, wherever it lands - data, check bit, or the overall parity bit itself. 2. **Two flips are detected and refused.** They are never repaired, and never returned as good data. 3. **Three flips are outside the guarantee.** They produce odd parity with a nonzero syndrome, which is exactly the signature of a single flip, so the word is silently miscorrected. The code promises correct-one and detect-two; it does not promise anything about three, and claiming it catches every odd count overstates it. That third point is the honest limit and the one candidates most often get wrong in the optimistic direction. ## What it costs, and why systems pay it - **One bit per word,** on top of the check bits the distance-3 code already spent. On a wide word that is a rounding error against the total overhead. - **Nothing in decode latency** worth naming: the overall parity is one more parity over bits already being read. - **An availability change,** which is the real design decision. A double flip that used to be served as data is now a hard failure surfaced to the layer above. That is the correct trade for stored data whose wrongness would propagate, and it means the layer above needs a retry, a redundant copy, or a way to fail loudly. The operational payoff is not only the caught double flip. A decoder that reports *corrected* single flips as well as uncorrectable ones turns the code into a sensor: rising correctable counts on one region are an early warning that arrives long before the first uncorrectable event, which is a signal a silent corrector throws away.

What does the decoder do when the overall parity fails but the syndrome is zero?
It concludes that the overall parity bit itself flipped. Every data and check position is covered by at least one of the original checks, so a flip anywhere else would make the syndrome nonzero. The payload is intact and the read succeeds; only the appended bit was wrong.
Does this scheme guarantee anything about three flipped bits in one word?
No. Three flips give odd overall parity and a nonzero syndrome - the exact signature of one flip - so the decoder repairs some innocent position and reports success. The guarantee is correct-one and detect-two; beyond that the behaviour is undefined, and treating it as an odd-count detector overstates what distance 4 buys.
Why report corrected single flips rather than silently fixing them?
Because the corrected count is the early-warning signal. Single flips are repaired transparently and cost nothing, but a rising rate concentrated on one region predicts the uncorrectable event that has not happened yet. A decoder that fixes and stays quiet discards the only cheap evidence available.

saying these in an interview costs you the question

Claims the extra bit lets the code correct two flips
Says it detects every odd number of flipped bits
Thinks the overall parity alone locates the bad position
Believes a double flip is repaired rather than refused
Treats an uncorrectable report as a decoder defect
Assumes distance stays at 3 after the bit is added

Why does adding one overall parity bit to a distance-3 code let a memory controller correct one flip and detect two?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The gap the extra bit closes

How the decoder uses two signals

What it does and does not guarantee

What it costs, and why systems pay it

▾common follow-ups3 questions

▾red flags6 flags

The gap the extra bit closes

How the decoder uses two signals

What it does and does not guarantee

What it costs, and why systems pay it

answer

go deeper