Foundations — ECC and memory error correction

This page assumes you know nothing. We start from what a bit is and end holding every symbol the parent note throws at you. Read top to bottom; each idea is used only after it's built.

1. A bit — the atom of everything

Why we need it: memory is nothing but a huge row of these switches. A "bit flip" — the villain of this whole topic — is simply one switch getting knocked to the wrong position by noise (see Cosmic Rays and Soft Errors).

Figure s01 below draws a bit as a physical switch: the left switch is down (value $0$, violet), the right switch is up (value $1$, magenta), and the orange arrow shows a cosmic ray "flipping" it — knocking a switch to the wrong position. That knock is the single event this whole topic fights.

2. A bit-string, and its length $n$

The picture: a row of switches. If someone says "$n=7$", picture seven switches in a line.

Why the topic needs it: a Hamming codeword is a bit-string, and every counting formula in this topic tallies positions in that string. You can't count positions without a symbol for "how many". We will meet the exact formula in section 5, once we have named all the pieces it counts.

3. Position numbers — counting from 1

The picture: put a tiny tag under each switch: 1, 2, 3, … That numbering is what the treasure-map syndrome will read out.

4. Reading a bit-string as a binary number

Before any "syndrome" can spell an address, we need to agree how a row of bits turns into an ordinary counting number. This is the missing translator between "pattern of bits" and "position 5".

Figure s05 stacks the string 101 over its weights $4,2,1$ and shows the running sum $=5$. Keep this picture: when the parent note writes "syndrome $=c_4{c}_2{c}_1=101_2=5$", it is doing exactly this multiply-and-add, with $c_4$ sitting in the MSB (weight $4$) slot and $c_1$ in the LSB (weight $1$) slot. The little subscript "${}_2$" just means "this is written in binary".

Why the topic needs it: a syndrome is a handful of pass/fail bits. Only by reading them with place value (MSB on the left) does that handful become a single position number to flip.

5. Powers of two — $2^r$ and the counting bound

We now name the two quantities the bound will compare:

• $k$ ::: the number of data bits (the actual message).
• $r$ ::: the number of parity / check bits we add.
• $n=k+r$ ::: total bits, matching the $n$ from section 2.

Figure s02 is a bar chart: as $r$ climbs $1,2,3,4$ the height $2^r$ jumps $2,4,8,16$ — each bar twice the last. The orange "×2" arrow marks the doubling. This is why only a few check bits can name many positions.

So the $+1$ is not a mystery: it is the "all clear" verdict, reserved so that a syndrome of $0$ can mean "nothing is wrong" (we cash this in fully in section 9).

6. XOR — the $\oplus$ symbol (how a parity check is computed)

Figure s03 lines up four bits 1 0 1 1 joined by $\oplus$ signs. Three of them are $1$ — an odd count — so the whole row collapses to the orange result $1$. Picture: XOR "erases" pairs of $1$s and reports whether one is left over. That single output bit is one parity check.

Why the topic needs it: every parity bit in a Hamming code is set so that its group of bits XORs to $0$ (that's "even parity"). When a bit later flips, that group's XOR becomes $1$ — the check "fails". No XOR, no check.

7. The parity bit — the simplest ECC there is

The picture: one guard bit watching a row. If exactly one switch flips, the guard notices something is wrong — but shrugs when you ask "which one?". Full story in Parity Bit.

Why the topic needs it: Hamming code is just many parity bits, each watching a cleverly chosen subset, so that together they don't just say "wrong" but say "wrong here". One parity bit is the seed of the whole idea.

8. Hamming distance $d(x,y)$ and $d_{min}$

Figure s04 stacks $x$ over $y$ and boxes in orange only the positions where they disagree. Count the orange boxes — that count is $d(x,y)$. Picture $d_{min}$ as the shortest such gap anywhere in the codebook.

Why the topic needs it: the entire "can I correct / detect?" question is answered by $d_{min}$ alone. Detect $s=d_{min}-1$ errors; correct $t=\lfloor (d_{min}-1)/2\rfloor$. Those two formulas in the parent note are pure distance geometry — a single flip moves you $1$ step, so if legal words are far apart you always land nearest the right one.

9. The floor bracket $\lfloor \rfloor$

Why the topic needs it: correction capability $t=\lfloor (d_{min}-1)/2\rfloor$ must be a whole number of bits — you can't correct "one and a half" bits. For SECDED, $d_{min}=4$ gives $t=\lfloor 3/2\rfloor =\lfloor 1.5\rfloor =1$: correct exactly one.

10. The syndrome — the treasure map

Why the topic needs it: this is the payoff of every earlier symbol. $2^r$ verdicts (section 5) come from XOR checks (section 6) on subsets picked by binary position numbers (sections 3–4), and the verdict is the location. See Hamming Code for the full construction; Reed-Solomon Codes extend the same idea to whole symbols.

How the foundations feed the topic

The map reads left-to-right into the parent topic: switches become strings, place value turns strings into numbers, XOR turns groups into checks, binary positions turn checks into addresses, and distance tells you how many errors survive.

Equipment checklist

Cover the right side and answer before revealing.