ECC and memory error correction: Worked examples — Hardware deep dive

This page is a drill hall. The parent note built the theory; here we run the machine on every kind of input it can face, so you never meet a case you haven't already seen worked.

Before we touch a single bit, one reminder of the whole trick: we number positions $1, 2, 3, \dots$ , put parity bits at power-of-two positions ( $1, 2, 4, 8$ ), fill the rest with data, and each parity bit at position $2^{i}$ watches every position whose binary index has bit $i$ turned on. The magic payoff: when we recompute the parities on a received word, the list of "which checks failed", read as a binary number, is the address of the broken bit. (If any of those words feel new, re-read the parent's Hamming section — everything below leans on Hamming Code, Parity Bit, and Boolean Algebra / XOR.)

The scenario matrix

Every ECC exercise you will ever be handed lands in one of these cells. The worked examples below are labelled with the cell they cover, and together they fill the whole grid.

Cell	Case class	What is tricky about it	Covered by
A	Encode from scratch (all-parity fresh)	placing bits, computing each parity	Ex 1
B	Decode, zero errors (degenerate input)	syndrome must come out $0$	Ex 2
C	Decode, single error in a data position	syndrome = data-bit address	Ex 3
D	Decode, single error in a parity position	syndrome points at a power-of-two slot	Ex 4
E	SECDED, double error (limiting failure of correction)	syndrome $\neq = 0$ but overall parity even	Ex 5
F	SECDED, error in the overall parity bit itself	edge case: syndrome $0$ , overall parity wrong	Ex 6
G	Sizing / bound (word problem)	choose $r$ for given $k$ ; real DIMM	Ex 7
H	Capability limits (exam twist)	$d_{min}$ vs detect/correct counts	Ex 8

Cells span: fresh encode, all three "where did the flip land" possibilities (data / parity / overall bit), the no-error degenerate case, the beyond-correction double-error case, a real-hardware sizing problem, and a distance-theory twist. That is the complete space.

Cell A — Encode from scratch

Worked example Encode the 4 data bits

1 1 0 1 with Hamming(7,4), even parity. Forecast: guess the final 7-bit codeword before reading. Where do the parity bits sit, and are they likely $0$ or $1$ ?

Lay out the 7 slots, parity at powers of two. Positions $1..7$ : p1 p2 d1 p4 d2 d3 d4. Fill data left-to-right: $d 1 = 1, d 2 = 1, d 3 = 0, d 4 = 1$ . So far: p1 p2 1 p4 1 0 1. Why this step? Powers-of-two placement is what makes the syndrome equal the error address — see the figure.
Compute p1 (watches 1,3,5,7). Data in those slots: pos3=1, pos5=1, pos7=1. $p 1 = 1 \oplus 1 \oplus 1 = 1$ . Why these positions? Indices $3, 5, 7$ in binary are $011, 101, 111$ — each has the lowest bit set, exactly the bit p1 owns.
Compute p2 (watches 2,3,6,7). pos3=1, pos6=0, pos7=1. $p 2 = 1 \oplus 0 \oplus 1 = 0$ . Why these? Indices $3, 6, 7 = 011, 110, 111$ all have the middle bit set.
Compute p4 (watches 4,5,6,7). pos5=1, pos6=0, pos7=1. $p 4 = 1 \oplus 0 \oplus 1 = 0$ . Why these? Indices $5, 6, 7 = 101, 110, 111$ all have the top bit set.
Assemble. Codeword = 1 0 1 0 1 0 1 (positions 1..7).

Verify: re-XOR each watched group and every parity must come out even (total $0$ ). Group 1: $1 \oplus 1 \oplus 1 \oplus 1 = 0$ ✓. Group 2: $0 \oplus 1 \oplus 0 \oplus 1 = 0$ ✓. Group 4: $0 \oplus 1 \oplus 0 \oplus 1 = 0$ ✓.

Figure — ECC and memory error correction

Cell B — Decode with zero errors (degenerate)

Cell C — Single error in a data position

Worked example The codeword

1 0 1 0 1 0 1 is stored; a soft error flips position 6 in DRAM. Received: 1 0 1 0 1 1 1. Recover it. Forecast: position 6 is a data slot — what syndrome do you expect, in binary?

c1 over 1,3,5,7: $1 \oplus 1 \oplus 1 \oplus 1 = 0$ . (pos6 isn't watched by c1.)
c2 over 2,3,6,7: $0 \oplus 1 \oplus 1 \oplus 1 = 1$ (fail — pos6 flipped inside this group).
c4 over 4,5,6,7: $0 \oplus 1 \oplus 1 \oplus 1 = 1$ (fail — pos6 lives here too).
Syndrome $= c_{4} c_{2} c_{1} = 11 0_{2} = 6$ . Why this step? $6 = 110$ : top and middle bits set, lowest clear — the exact "which groups contain position 6" fingerprint.
Flip position 6. 1 0 1 0 1 1 1 → 1 0 1 0 1 0 1. Why trust it blindly? No knowledge of the original was used — the syndrome computed the address.

Verify: decode gives back Ex 1's codeword exactly. Re-run all three checks: $0, 0, 0$ . ✓

Cell D — Single error in a parity position

Worked example Same stored word

1 0 1 0 1 0 1; this time position 2 (a parity bit) flips. Received: 1 1 1 0 1 0 1. What happens? Forecast: many students expect "no problem, it's only a parity bit." Is that true?

c1 over 1,3,5,7: $1 \oplus 1 \oplus 1 \oplus 1 = 0$ . (pos2 not watched.)
c2 over 2,3,6,7: $1 \oplus 1 \oplus 0 \oplus 1 = 1$ (fail — pos2 is watched by c2, since a parity bit at $2^{i}$ watches itself).
c4 over 4,5,6,7: $0 \oplus 1 \oplus 0 \oplus 1 = 0$ .
Syndrome $= c_{4} c_{2} c_{1} = 01 0_{2} = 2$ .
Flip position 2 → 1 0 1 0 1 0 1. Fixed. Why this matters: the syndrome pointed at a parity slot. The code doesn't care whether the flipped bit was data or check — position 2 is position 2.

Verify: restored word matches Ex 1; all checks $0, 0, 0$ . This directly disproves the [!mistake] "syndrome 5 means data bit 5" — the address is over the whole codeword. ✓

Cell E — SECDED with a double error (beyond correction)

We now bolt on the overall parity bit $p_{0}$ = XOR of all codeword bits, giving $d_{min} = 4$ (SECDED). This is the limiting case where "just correct the nearest word" would silently lie to us.

Worked example SECDED word: data codeword

1 0 1 0 1 0 1, with $p_{0} = 1 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus 0 \oplus 1 = 0$ . Two bits flip: positions 3 and 5. Detect the disaster. Forecast: two flips — will the Hamming syndrome be zero or nonzero? Will overall parity look wrong or right?

Received (positions 1..7): flip pos3 and pos5 of 1 0 1 0 1 0 1 → 1 0 0 0 0 0 1. $p_{0}$ still stored as $0$ .
c1 over 1,3,5,7: $1 \oplus 0 \oplus 0 \oplus 1 = 0$ .
c2 over 2,3,6,7: $0 \oplus 0 \oplus 0 \oplus 1 = 1$ (fail).
c4 over 4,5,6,7: $0 \oplus 0 \oplus 0 \oplus 1 = 1$ (fail).
Hamming syndrome $= 11 0_{2} = 6$ — nonzero, so Hamming thinks there's a single error at position 6.
Overall-parity check: XOR all 7 received bits $\oplus p_{0}$ . Received bits: $1 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0$ , and $p_{0} = 0$ , total $= 0$ — parity looks even/OK. Why this is the tell: two flips cancel in the grand total (even number of changes ⇒ overall parity unchanged), but they cannot cancel in the Hamming syndrome.
Decision rule: syndrome $\neq = 0$ and overall parity OK ⇒ DOUBLE ERROR — uncorrectable, raise alarm.

Verify: had we "trusted" syndrome $6$ and flipped position 6, we'd have produced 1 0 0 0 0 1 1 — a third wrong word, not the original. So refusing to correct is the correct behaviour. This is why [!mistake] "SECDED can correct doubles" is false: $t = ⌊(4 - 1) /2 ⌋ = 1$ . ✓

Cell F — Error in the overall parity bit itself

Worked example SECDED word as in Ex 5 arrives clean in positions 1..7 (

1 0 1 0 1 0 1), but the overall parity bit $p_{0}$ itself flips from $0$ to $1$ . What does the decoder conclude? Forecast: the data is perfect. Will the decoder panic?

Hamming syndrome: all three checks over 1..7 give $0$ (data untouched) ⇒ syndrome $= 0$ .
Overall-parity check: XOR of the 7 bits $= 0$ , but stored $p_{0} = 1$ , so total $= 0 \oplus 1 = 1$ — parity wrong.
Decision rule: syndrome $= 0$ but overall parity wrong ⇒ the only bit that can be broken is $p_{0}$ itself. Correct it (flip $p_{0}$ back to $0$ ); the data is fine. Why this is safe: a genuine data single-error would have produced a nonzero syndrome. Zero syndrome + bad overall parity uniquely fingerprints "the overall bit flipped."

Verify: the four SECDED cases now covered completely — $(0, ok)$ : clean; $(\neq = 0, wrong)$ : single, correct; $(\neq = 0, ok)$ : double, alarm; $(0, wrong)$ : overall-bit flip, harmless. ✓

Cell G — Sizing a real code (word problem)

Worked example You are designing ECC for a machine that moves

64-bit words in and out of DRAM. How many parity bits $r$ does plain single-error-correcting Hamming need, and does the real "72-bit DIMM" match? Forecast: guess $r$ before computing. Is it closer to 6, 7, or 8?

Write the bound. We need $2^{r} \geq k + r + 1$ with $k = 64$ . Why this inequality? The syndrome is an $r$ -bit number; it must name $k + r$ possible flip positions plus the reserved all-zero "no error" — that's the $+ 1$ .
Try $r = 6$ : $2^{6} = 64$ , need $\geq 64 + 6 + 1 = 71$ . $64 \geq 71$ ? No.
Try $r = 7$ : $2^{7} = 128 \geq 64 + 7 + 1 = 72$ ? Yes. So SEC-only needs $r = 7$ .
Real DIMMs use 8 ECC bits (72-bit word) — the extra bit is the overall parity that upgrades SEC to SECDED. Check: $2^{8} = 256 \geq 64 + 8 + 1 = 73$ . ✓

Verify: $r = 7$ satisfies the bound (128 ≥ 72) while $r = 6$ fails (64 < 71). The industry 64+8 layout gives SECDED with room to spare. For chip-scale failures you'd move to Reed-Solomon Codes / Chipkill instead. ✓

Cell H — Capability twist (exam-style)

Worked example A code has

$d_{min} = 5$ . (a) How many errors can it detect? (b) How many correct? (c) Could it be configured as "single-correct triple-detect"? Forecast: jot your three numbers now.

Detect: a code detects $s$ errors when codewords are $\geq s + 1$ apart, so $s = d_{min} - 1 = 5 - 1 = 4$ . Why? If two legal words were only $4$ apart, $4$ flips could turn one into the other undetected. At distance $5$ that can't happen for $\leq 4$ flips.
Correct: correction balls of radius $t$ stay disjoint when centres are $\geq 2 t + 1$ apart, so $t = ⌊(d_{min} - 1) /2 ⌋ = ⌊ 4/2 ⌋ = 2$ .
Single-correct triple-detect? Spend some detection power to guarantee no miscorrection: correct $t = 1$ and detect $s$ with $t + s + 1 \leq d_{min}$ ⇒ $1 + s + 1 \leq 5$ ⇒ $s \leq 3$ . So yes, $d_{min} = 5$ supports SEC-3ED. Why the split budget? Distance is a fixed "coin"; you can spend it all on correction ( $t = 2$ ) or reserve some as a safety margin so you never confidently flip the wrong bit.

Verify: $s = 4$ , $t = 2$ , and the SEC-3ED inequality $1 + 3 + 1 = 5 \leq 5$ holds. Contrast with SECDED ( $d_{min} = 4$ ): $t = ⌊ 3/2 ⌋ = 1$ , detect $3$ . ✓

Recall Quick self-test across the matrix

Received Hamming(7,4) word 1 1 1 0 1 0 1 with even parity — which position (if any) is wrong? ::: c1(1,3,5,7)= $1 \oplus 1 \oplus 1 \oplus 1$ =0, c2(2,3,6,7)= $1 \oplus 1 \oplus 0 \oplus 1$ =1, c4(4,5,6,7)= $0 \oplus 1 \oplus 0 \oplus 1$ =0 → syndrome $01 0_{2} = 2$ → position 2 flipped (a parity bit). For $k = 128$ data bits, minimum $r$ for SEC Hamming? ::: $2^{8} = 256 \geq 128 + 8 + 1 = 137$ and $2^{7} = 128 < 128 + 7 + 1 = 136$ , so $r = 8$ . A code has $d_{min} = 3$ . Detect? Correct? ::: Detect $3 - 1 = 2$ ; correct $⌊ 2/2 ⌋ = 1$ (plain SEC, the classic Hamming setting).

Related: Hamming Code · Parity Bit · Boolean Algebra / XOR · Cosmic Rays and Soft Errors · DRAM · Reed-Solomon Codes · Cache Coherence