Dependability and Error Correction

In 2003 a Belgian election-counting machine gave a candidate exactly 4096 extra votes. No fraud, no bug in the software — a single bit deep in the machine's memory had silently flipped from 0 to 1, and 2^{12} = 4096 is what one flipped bit in that position is worth. The most likely culprit was a cosmic ray: a stray particle from space depositing just enough charge to upset one memory cell. Multiply that machine by the billions of transistors in a data centre and you see why every serious computer treats correctness not as a given but as a statistical property to be engineered.

This lesson is about dependability — how we quantify a machine's trustworthiness, and the beautiful coding theory that lets a chip notice when a bit has gone bad and, remarkably, put it right without ever telling the software anything happened.

Faults, errors, failures — three different things

Reliability engineers are pedantic about vocabulary, and for good reason: confusing these three words makes it impossible to reason about where to spend your defence budget.

Term	What it is	Example
Fault	a defect or upset in the physical machine	a memory cell whose charge got flipped by a particle
Error	a fault that has corrupted some state	the stored value is now wrong
Failure	the error becomes visible in the service delivered	the wrong vote total reaches the screen

The whole art of dependability is to stop the chain before it reaches the last box. A fault that is caught and corrected never becomes a failure. This is why a cosmic ray hits your laptop's RAM roughly once a day yet you almost never notice: the fault happens, but error-correcting hardware breaks the chain.

RAS and the arithmetic of uptime

Industry folds trustworthiness into three letters, RAS: Reliability (does it give the right answer?), Availability (is it up when you need it?), and Serviceability (how fast can you fix it?). The first two have crisp definitions built from three mean times.

\text{MTTF} — mean time to failure, the average time a component runs before it breaks;
\text{MTTR} — mean time to repair, how long it takes to get it working again;
\text{MTBF} = \text{MTTF} + \text{MTTR} — mean time between failures, one full up-then-down cycle.

Availability is the fraction of time the system is actually working:

A \;=\; \frac{\text{MTTF}}{\text{MTTF} + \text{MTTR}} \;=\; \frac{\text{MTTF}}{\text{MTBF}}.

Engineers quote availability in "nines". Five nines — 0.99999 — is the telecom gold standard and allows only about 5 minutes of downtime per year. Each extra nine cuts the allowed outage tenfold, and — crucially — availability depends on the ratio of repair time to lifetime, so making things fast to fix (small MTTR) is often cheaper than making them never break (huge MTTF).

availability A = \dfrac{\text{MTTF}}{\text{MTTF}+\text{MTTR}}; it is a pure ratio, so a long MTTF and a short MTTR are interchangeable levers;
"k nines" means A = 1 - 10^{-k}; five nines \approx 5 min downtime/year;
failure rate is often given in FIT (failures per 10^9 hours); \text{MTTF} = 10^9 / \text{FIT} hours.

Why repair speed is a first-class lever

Slide the \text{MTTF} and watch availability as a function of repair time \text{MTTR} (the horizontal axis, in hours). Two systems with wildly different lifetimes can have the same availability if the flimsier one is repaired proportionally faster. That is the whole logic behind hot-swappable disks and rolling reboots: you cannot stop faults, so you make recovery instant.

From detecting to correcting: parity, then Hamming

Knowing a machine will suffer bit flips, we add redundancy so it can catch them. The cheapest scheme is a single parity bit: append one bit chosen so the total number of 1s is even. Flip any one bit and the count becomes odd — detected. But parity can only detect a single error; it cannot tell you which bit flipped, and two flips cancel and sneak through undetected.

Richard Hamming, furious at a weekend's work lost to a card-reader error in 1950, invented the fix. A Hamming code uses several parity bits, each guarding an overlapping subset of positions, so a single error trips a unique pattern of failed checks — the syndrome — that spells out, in binary, the exact position to flip back. The classic (7,4) code packs 4 data bits into a 7-bit word using 3 parity bits at the power-of-two positions 1, 2, 4.

Each parity bit checks the positions whose index includes its bit. Parity P_1 (position 1) covers all positions with the 1s-bit set — 1,3,5,7; P_2 covers 2,3,6,7; P_4 covers 4,5,6,7. Add up the values of whichever checks fail and you have read the error's address straight off the machine.

SECDED: correct one, detect two

The general rule uses the Hamming distance — the number of bit positions in which two legal code words differ. A code that guarantees a minimum distance d between any two valid words can detect up to d-1 errors and correct up to \lfloor (d-1)/2 \rfloor. Plain parity has d = 2 (detect 1, correct 0); the bare Hamming code has d = 3 (correct 1).

Add one more overall parity bit and you reach d = 4: the workhorse SECDED code — Single Error Correct, Double Error Detect. This is what guards the ECC DRAM in every server on Earth: it silently fixes the everyday single-bit cosmic-ray flip and raises an alarm on the rarer double flip. The code below encodes a nibble, corrupts one bit, and watches the syndrome walk the machine straight to the culprit.

// Hamming(7,4): encode 4 data bits, inject a 1-bit error, and correct it via the syndrome. // Positions are 1..7; parity bits sit at the powers of two (1,2,4), data at 3,5,6,7. function encode(d: number[]): number[] { const c = [0, 0, 0, 0, 0, 0, 0, 0]; // index 1..7 (0 unused) c[3] = d[0]; c[5] = d[1]; c[6] = d[2]; c[7] = d[3]; c[1] = (c[3] + c[5] + c[7]) % 2; // P1 checks 1,3,5,7 c[2] = (c[3] + c[6] + c[7]) % 2; // P2 checks 2,3,6,7 c[4] = (c[5] + c[6] + c[7]) % 2; // P4 checks 4,5,6,7 return c; } function syndrome(c: number[]): number { const s1 = (c[1] + c[3] + c[5] + c[7]) % 2; const s2 = (c[2] + c[3] + c[6] + c[7]) % 2; const s4 = (c[4] + c[5] + c[6] + c[7]) % 2; return s1 * 1 + s2 * 2 + s4 * 4; // binary address of the bad bit } const word = encode([1, 0, 1, 1]); console.log("encoded (pos 1..7):", word.slice(1).join("")); const bad = word.slice(); const flip = 5; // pretend a cosmic ray flipped position 5 bad[flip] = 1 - bad[flip]; console.log("corrupted: ", bad.slice(1).join(""), " (bit", flip, "flipped)"); const s = syndrome(bad); console.log("syndrome points to position", s); if (s !== 0) bad[s] = 1 - bad[s]; // correct it console.log("corrected: ", bad.slice(1).join("")); console.log("matches original? ", bad.join("") === word.join(""));

Beyond one bit: chipkill and redundancy

SECDED assumes errors are independent single bits. But a whole DRAM chip can die at once — a stuck driver, a shattered package — flipping many bits in one word and defeating an ordinary ECC. Chipkill (IBM's name; Intel calls it SDDC) spreads each word's bits across many chips and uses a stronger code so that the complete loss of any single chip still corrects. It is RAID, but for memory chips.

Zoom out and the same idea — redundancy — is the master strategy of all dependable design: RAID mirrors disks, error-correcting codes duplicate information, triple-modular-redundancy runs three copies of a circuit and votes, and data centres replicate whole machines across continents. You cannot make a component that never fails; you make a system that survives its components failing.

Measurements put the soft-error rate of DRAM at very roughly one bit-flip per few gigabytes per few days at sea level — and it climbs sharply with altitude, because more of the cosmic-ray shower survives the thinner atmosphere. Aircraft and spacecraft avionics see errors far more often, which is why they use radiation-hardened parts and heavy ECC. Google, running fleets of millions of machines, published a famous 2009 field study finding that DRAM errors were orders of magnitude more common than lab estimates had predicted — vindicating every server that ships with ECC memory as standard. The particles are not exotic: mostly neutrons from ordinary cosmic-ray air showers, plus a trickle of alpha particles from trace radioactive impurities in the chip packaging itself.

A single parity bit tells you that something is wrong, never what. With no way to locate the bad bit it cannot repair anything, and — worse — if two bits flip, the parity check passes again and the corruption is invisible. Conversely, do not over-claim for SECDED: it corrects one error and detects two, but a triple error can alias onto a valid-looking single-error syndrome and be "corrected" to the wrong value — silent corruption. Every code has a distance budget; spend it knowingly. More protection always costs more redundant bits, and there is no free lunch.