ECC and memory error correction: Exercises — Hardware deep dive

Before the drills, two ideas must be pinned down, because every figure and solution leans on them.

With those two ideas in hand, here is the figure we will reuse throughout:

Figure — ECC and memory error correction

Intuition How to read Figure s01 (and use it in decoding)

Alt-text / walkthrough. The figure has two rulers.

Left ruler — position ruler. Seven slots numbered $1$ to $7$ (Hamming always counts from $1$ , never $0$ ). Yellow squares are parity slots at the powers of two ( $1, 2, 4$ ); blue squares are data slots ( $3, 5, 6, 7$ ). When a syndrome tells you "position 6," you count along this ruler to find the culprit — parity or data alike.
Right ruler — codeword space. Green dots $A, B, C$ are legal codewords, spread apart in Hamming distance. The red X is a received word one hop away from $A$ . The red arrow shows decoding: snap to the nearest legal dot. That single hop is exactly one bit flip; because $A$ is the only dot within one hop, the decode is unambiguous. Using it: encoding puts you on a green dot; a soft error nudges you off it (red X); the syndrome measures which hop you took, and the arrow snaps you back. Keep both rulers in mind for every problem below.

Level 1 — Recognition

(Can you spot the right term / read a formula off by heart?)

L1.1

A DRAM cell silently holds the wrong value after a cosmic-ray neutron hits it, but the chip still works fine. What is this called, and what is it not?

Recall Solution

It is a soft error (a transient bit flip). It is not a hard error — the hardware is undamaged, and rewriting the cell fixes it. See Cosmic Rays and Soft Errors and DRAM.

L1.2

A code has minimum distance $d_{min} = 5$ . Without building anything, state how many errors it can detect and how many it can correct.

Recall Solution

Detect $s = d_{min} - 1 = 4$ . Correct $t = ⌊ \frac{d _{min} - 1}{2} ⌋ = ⌊ \frac{4}{2} ⌋ = 2$ .

L1.3

In a Hamming code, at which bit positions do the parity bits live? Name the first four.

Recall Solution

At powers of two: positions $1, 2, 4, 8$ . Everything else holds data. (Position counting starts at 1.)

Level 2 — Application

(Plug into the machinery and turn the crank.)

L2.1

You must protect $k = 4$ data bits. Find the smallest number of parity bits $r$ that satisfies the Hamming bound, and hence the total codeword length $n$ .

Recall Solution

The Parity Bit-counting bound is $2^{r} \geq k + r + 1 = 4 + r + 1 = r + 5$ .

$r = 2$ : $2^{2} = 4 \geq 7$ ? No.
$r = 3$ : $2^{3} = 8 \geq 8$ ? Yes. So $r = 3$ , and $n = k + r = 7$ . This is the famous Hamming(7,4) code.

L2.2

Encode the data bits 1010 with Hamming(7,4), even parity. Give the 7-bit codeword.

Recall Solution

Lay data into the non-power-of-two slots. Positions $1..7$ : $p1 p2 d1 p4 d2 d3 d4 = p1 p2 1 p4 0 1 0$ Apply the parity-check rule (XOR of covered bits $= 0$ , so each parity = XOR of the data it covers):

$p_{1}$ covers positions $1, 3, 5, 7$ ; data there are $1, 0, 0$ → $p_{1} = 1 \oplus 0 \oplus 0 = 1$ .
$p_{2}$ covers positions $2, 3, 6, 7$ ; data there are $1, 1, 0$ → $p_{2} = 1 \oplus 1 \oplus 0 = 0$ .
$p_{4}$ covers positions $4, 5, 6, 7$ ; data there are $0, 1, 0$ → $p_{4} = 0 \oplus 1 \oplus 0 = 1$ . Codeword (positions 1→7): $1 0 1 1 0 1 0$ . Check: each covered set now XORs to $0$ . ✓

L2.3

Take the codeword you just built, 1011010, and flip position 6. Decode it: compute the syndrome and recover the original.

Recall Solution

Flipped word: position 6 was 1 → now 0: $1 0 1 1 0 0 0$ . Recompute each syndrome bit ("ok" if XOR = 0):

$c_{1}$ : positions $1, 3, 5, 7 = 1, 1, 0, 0$ → $\oplus = 0$ (ok).
$c_{2}$ : positions $2, 3, 6, 7 = 0, 1, 0, 0$ → $\oplus = 1$ (fail).
$c_{4}$ : positions $4, 5, 6, 7 = 1, 0, 0, 0$ → $\oplus = 1$ (fail). Syndrome $= c_{4} c_{2} c_{1} = 11 0_{2} = 6$ . So position 6 is wrong — matches our flip. Flip it back → $1 0 1 1 0 1 0$ , and the data slots read back 1010. ✓

Level 3 — Analysis

(Why does the machinery behave this way? Probe the edges.)

L3.1

A single parity bit gives $d_{min} = 2$ . Using the capability formulas, prove it can detect one error but correct zero. Then say why we bother with it at all.

Recall Solution

Detect: $s = d_{min} - 1 = 1$ . Correct: $t = ⌊(2 - 1) /2 ⌋ = ⌊ 0.5 ⌋ = 0$ . Why zero correction: with $d_{min} = 2$ , a single flip sits exactly halfway between two codewords — there is no unique nearest neighbour to snap to. You know something broke but not where. Still useful: cheap detection lets a system re-fetch/retry, which is far better than silent corruption.

L3.2

In Hamming(7,4) you compute the syndrome and get $c_{4} c_{2} c_{1} = 000$ . Then separately you're told two bits actually flipped. Explain, using the "ball" picture, why the decoder is now wrong — and what the syndrome would look like.

Recall Solution

A pure Hamming(7,4) has $d_{min} = 3$ , so its balls have radius $t = 1$ . Two flips push you a distance 2 from your codeword — outside your own ball, and possibly inside a neighbour's ball (its decoding region).

If the two flips land you exactly on another legal codeword, the recomputed syndrome is $000$ → decoder says "no error" (silent miscorrect). This is exactly why raw Hamming(7,4) is unsafe for 2 errors.
More often the syndrome is nonzero but points at a third, innocent position (you have drifted into a neighbour's decoding region) → the decoder "corrects" a bit that was fine, making things worse. The picture: two hops leave the safe radius-1 zone, so nearest-neighbour logic can no longer be trusted.

L3.3

Given the Hamming bound $2^{r} \geq k + r + 1$ , find the largest number of data bits $k$ that $r = 8$ Hamming parity bits can protect for single-error correction. Then reconcile this with real ECC DRAM, which uses 7 Hamming bits + 1 overall parity bit.

Recall Solution

Pure single-error-correcting count. With $r = 8$ Hamming check bits (all of them addressing the syndrome), the bound is $2^{8} \geq k + 8 + 1 \Rightarrow 256 \geq k + 9 \Rightarrow k \leq 247$ (total $n = 255$ ). This is a $d_{min} = 3$ code — correct 1, no double-detect. Real ECC DRAM is different in how it spends its 8 bits. It does not use 8 Hamming bits. It uses 7 Hamming check bits (enough to address the syndrome for $k = 64$ : $2^{7} = 128 \geq 64 + 7 + 1 = 72$ ✓) plus 1 overall parity bit $p_{0}$ that upgrades the code to $d_{min} = 4$ (SECDED). Total ECC width $= 7 + 1 = 8$ bits, giving the familiar 72-bit-wide DIMM ( $64$ data $+ 8$ ECC). The key distinction: the "8 ECC bits" of DRAM are not 8 syndrome-addressing Hamming bits — they are $7$ Hamming $+ 1$ overall. Conflating "total ECC bits" with "Hamming bits" is the trap the next callout addresses.

Level 4 — Synthesis

(Assemble the parts into a new working code.)

L4.1

Upgrade Hamming(7,4) to SECDED by adding an overall parity bit $p_{0}$ over all 7 bits (even parity), making an 8-bit word. Encode data 1010 (whose Hamming(7,4) codeword you found in L2.2 was 1011010) and give the full 8-bit SECDED word.

Recall Solution

Hamming codeword: $1 0 1 1 0 1 0$ — count the ones: $1 + 0 + 1 + 1 + 0 + 1 + 0 = 4$ (even). Overall parity $p_{0} =$ XOR of all 7 bits $= 0$ (even count → 0). 8-bit SECDED word (put $p_{0}$ first): $0 ∣ 1 0 1 1 0 1 0$ . Now the code has $d_{min} = 4$ : $t = ⌊ 3/2 ⌋ = 1$ correct, $s = 3$ detect (in particular all doubles).

L4.2

Using your L4.1 word 0 1011010 ( $p_{0}$ then positions 1–7), corrupt it with a double error: flip positions 3 and 6. Run the SECDED decode logic and show it correctly refuses to miscorrect.

Recall Solution

Original: $p_{0} = 0$ , body $1 0 1 1 0 1 0$ . Flip pos 3 (1→0) and pos 6 (1→0): body becomes $1 0 0 1 0 0 0$ , $p_{0}$ unchanged $= 0$ . Hamming syndrome on the body:

$c_{1}$ : pos $1, 3, 5, 7 = 1, 0, 0, 0 \to \oplus = 1$ (fail).
$c_{2}$ : pos $2, 3, 6, 7 = 0, 0, 0, 0 \to \oplus = 0$ (ok).
$c_{4}$ : pos $4, 5, 6, 7 = 1, 0, 0, 0 \to \oplus = 1$ (fail). Syndrome $= c_{4} c_{2} c_{1} = 10 1_{2} = 5 \neq = 0$ . Overall-parity check $P$ : XOR of all 8 bits ( $p_{0}$ + body). Count of 1s $= 0 + (1 + 0 + 0 + 1 + 0 + 0 + 0) = 2$ → even, so $P = 0$ (ok). Full SECDED decode table (all four quadrants):

syndrome	overall parity $P$	verdict
$0$	ok ( $P = 0$ )	no error
$0$	wrong ( $P = 1$ )	the overall-parity bit $p_{0}$ itself flipped → correct $p_{0}$
$\neq = 0$	wrong ( $P = 1$ )	single error at syndrome position → correct it
$\neq = 0$	ok ( $P = 0$ )	double error → detect only, do NOT correct

We are in the last row: syndrome $= 5 \neq = 0$ but overall parity even/OK → double error detected, uncorrectable → raise alarm. The decoder correctly does not touch position 5 (which was never flipped). ✓ (The new second row matters: if only $p_{0}$ flips, the body's Hamming syndrome is $000$ but $P$ is wrong — so we know the lone bad bit is $p_{0}$ and simply flip it back.)

Level 5 — Mastery

(Design decisions, trade-offs, and one contest-grade problem.)

L5.1

A designer proposes protecting a 64-bit word by simply repeating each bit 3 times (192 bits total). Compare its correction power and overhead against SECDED(72,64). Which wins for DRAM and why?

Recall Solution

Triple repetition (majority vote): each triple has $d_{min} = 3$ → $t = 1$ error corrected per triple. Overhead: $192 - 64 = 128$ redundant bits = 200% overhead. It can correct up to one flip in every group, so many total errors — but at ruinous cost. SECDED(72,64): $8$ ECC bits ( $7$ Hamming $+ 1$ overall) → 12.5% overhead, corrects 1 and detects 2 per 64-bit word. Winner for DRAM: SECDED, overwhelmingly. Soft errors are rare per word; single-error correction covers the common case at $1/16$ the storage of repetition. Repetition only pays off in extreme radiation environments where multi-bit-per-word errors are expected. For chip-failure resilience you instead move to Reed-Solomon Codes-style Chipkill, not naive repetition.

L5.2

Contest problem. You receive a Hamming(7,4) word (even parity, no overall bit) and read $1 1 1 0 0 1 0$ . (a) Is there an error? (b) If so, where, and what is the corrected codeword? (c) Extract the original 4 data bits.

Recall Solution

Body positions 1–7: $1 1 1 0 0 1 0$ .

$c_{1}$ : pos $1, 3, 5, 7 = 1, 1, 0, 0 \to \oplus = 0$ (ok).
$c_{2}$ : pos $2, 3, 6, 7 = 1, 1, 1, 0 \to \oplus = 1$ (fail).
$c_{4}$ : pos $4, 5, 6, 7 = 0, 0, 1, 0 \to \oplus = 1$ (fail). Syndrome $= c_{4} c_{2} c_{1} = 11 0_{2} = 6 \neq = 0$ . (a) Yes, an error at position 6. (b) Flip position 6 (1→0): corrected word $1 1 1 0 0 0 0$ . Verify: $c_{1}$ pos $1, 3, 5, 7 = 1, 1, 0, 0 \to 0$ ; $c_{2}$ pos $2, 3, 6, 7 = 1, 1, 0, 0 \to 0$ ; $c_{4}$ pos $4, 5, 6, 7 = 0, 0, 0, 0 \to 0$ . Syndrome $000$ ✓. (c) Data slots are positions $3, 5, 6, 7$ → $d_{1} d_{2} d_{3} d_{4} = 1, 0, 0, 0 = 1000$ .

L5.3

Prove the general claim behind Hamming Code: with $r$ parity bits placed at powers of two, the syndrome equals the binary index of the single flipped position. (One-paragraph argument.)

Recall Solution

Assign each position $j$ its binary expansion. Parity bit $2^{i}$ is defined to check exactly the positions whose index has bit $i$ set. If position $j$ flips, then syndrome bit $c_{2^{i}}$ changes value iff bit $i$ of $j$ is $1$ (that flip is inside $c_{2^{i}}$ 's coverage precisely when bit $i$ of $j$ is set). So the vector of failing checks reads out, bit by bit, the binary digits of $j$ — i.e. syndrome $= j$ . If nothing flipped, every check passes → syndrome $000 \dots 0$ , reserved for "no error." This is why the placement must be powers of two: they make each check correspond to one independent binary digit of the address, and it is why $2^{r} - 1$ nonzero syndromes name exactly $2^{r} - 1$ positions (the Hamming bound).

Active-recall flashcards

For

k = 4

data bits, how many Hamming parity bits are needed?

r = 3

(since

2^{3} = 8 \geq 4 + 3 + 1 = 8

), giving Hamming(7,4).

Encode 1010 in Hamming(7,4) even parity.

1011010.

What does syndrome bit

c_{i}

mean?

The re-run parity check at position

i

c_{i} = 0

if it balances (ok),

c_{i} = 1

if it fails; stacked as

c_{4} c_{2} c_{1}

they give the flip's position.

Hamming(7,4) syndrome

c_{4} c_{2} c_{1} = 110

points where?

Position 6 of the whole codeword.

How many Hamming bits vs overall bits does ECC DRAM use?

7 Hamming check bits + 1 overall parity bit = 8 ECC bits for SECDED over 64 data bits.

In SECDED, nonzero syndrome + even overall parity means?

A double error — detect only, do not correct.

In SECDED, zero syndrome + wrong overall parity means?

Only the overall-parity bit

p_{0}

flipped — correct

p_{0}

Overhead of triple-repetition vs SECDED for 64 data bits?

200% (128 extra bits) vs 12.5% (8 extra bits).