SECDED: ECC Memory

in reviewThis lesson is complete and being validated before release - details may still change.

SECDED code

Loading interactive demo…

Six rows of eight positions. The data row holds four bits at positions 3, 5, 6, and 7; the code word row adds the three Hamming parity bits at 1, 2, and 4 and an eighth bit that makes the whole word even; the received row is what the noise left; the checks row re-counts each group and the whole word; the verdict row says which of the four cases the receiver is in; the corrected row flips back what the verdict allows. Tap a data cell to change the message, a received cell to choose where the noise hits.Take the tour, or press and explore. Legend:

The panel beside the stage is the real ExtendedHammingCode class from the published library executing in your browser, with the current line highlighted.

The position being set or checked, ringed with the positions it covers.
Parity bits: the Hamming three and the overall bit at 8.
A bit the noise flipped, a check that failed, and a double flip the receiver reports.
A check that passed, and the bit the correction flipped back.
Rows the run has not reached yet, ghosted.

syndrome is the failing Hamming checks' positions added up, overall whether the whole word is even or odd, verdict the case those two pick, fixed the position flipped back, rate the data bits per bit sent against the (7, 4) code.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The eighth bit. Take the (7, 4) Hamming word $c_1 \ldots c_7$ and append

c_8 = c_1 \oplus c_2 \oplus \cdots \oplus c_7 ,

so that every code word has an even number of ones. Two code words of the (7, 4) code differ in at least three positions; since both extended words are even, they cannot differ in an odd number of positions, so they differ in at least four. The minimum distance rises from $3$ to $4$ .

What distance four buys. A received word with one flip is at distance $1$ from its original and at least $3$ from every other code word, so it is corrected as before. A word with two flips is at distance $2$ from its original and at least $2$ from some other code word: it may sit exactly between two, so it cannot be corrected, but it is never a code word itself, so it is always noticed. Distance $d$ corrects $\lfloor (d-1)/2 \rfloor$ flips and detects $d - 1$ ; at $d = 4$ that is one and three, and the receiver here uses one and two, which is what it can tell apart.

The decision table. The receiver computes the Hamming syndrome $s$ from checks $1$ , $2$ , and $4$ , and the overall parity $o$ of all eight bits:

$s$	$o$	flips	action
$0$	even	none	nothing
$\neq 0$	odd	one, at $s$	flip bit $s$ back
$\neq 0$	even	two	report, touch nothing
$0$	odd	the parity bit	flip bit $8$ back

One flip changes the parity of the whole word, two flips change it back. A nonzero syndrome with an even word is therefore impossible for a single flip, and that one impossible combination is the double-error report. The (7, 4) code lacks $o$ , so it reads a nonzero syndrome as a single flip every time and, on a double, flips a third bit.

Rate. Four data bits in eight is a rate of exactly $1/2$ , down from $4/7$ . Memory uses the same construction at a much better rate: the Hamming code with $7$ check bits covers $127$ positions, so $64$ data bits need $7$ checks plus the overall bit, $(72, 64)$ with rate $8/9$ . The extra chip on a 72-bit DIMM is those eight bits.

Scrubbing. SECDED fixes one flip per word, so the danger is a second flip landing in a word that already holds one. A memory controller therefore walks through memory in the background, reading each word, correcting it, and writing it back, at a rate chosen so that the chance of two flips arriving in one word between visits is negligible. The code and the scrub together are what make a terabyte of DRAM trustworthy.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The (7, 4) encoder is reused, untraced. ExtendedHammingCode builds its first seven bits with the previous lesson's HammingCode and emits every event itself, so the stage's highlighted lines are all in this file.
Bit 8 is a position, not a prefix. Textbooks often put the overall parity bit at position $0$ ; keeping it at $8$ leaves the Hamming positions and the syndrome exactly as they were, and the flip taps simply gain one cell.
One check loop for all four. Positions $1$ , $2$ , $4$ , and $8$ go through the same loop; covers returns the Hamming group for the first three and all eight positions for the last, and the loop sorts a failure into the syndrome or the odd flag by which position it is checking.
classify is the table. Four lines, one per row, in the order the prose gives them; correct with position $0$ is how a double flip is passed on untouched, and the verdict event is where the receiver's decision is visible before anything moves.

Hamming's 1950 paper already noted that one more parity bit raises his code's distance to four, so a double error is detected rather than mistaken for a single one. The idea waited until dynamic memory chips arrived in the 1970s and alpha particles from the packaging began flipping stored bits at random. Memory controllers took up the extended code as eight check bits per 64-bit word, and the name stuck: SECDED, single error correction, double error detection. Every server DIMM still carries it, scrubbed in the background so single flips never get the chance to pair up.

1950Richard Hamming - Observes in 'Error Detecting and Error Correcting Codes' that one extra parity check over the whole word makes a double error detectable.source
1960M. Y. Hsiao and others at IBM - Hsiao's 1970 variant of the SECDED code chooses check groups of odd size so the decoder is faster and cheaper in hardware; most memory controllers use a Hsiao code.source
1979Timothy May and Murray Woods, Intel - Trace soft errors in dynamic RAM to alpha particles from trace uranium and thorium in the chip packaging, the random single-bit flips ECC memory exists to absorb.source
2009Bianca Schroeder, Eduardo Pinheiro, and Wolf-Dietrich Weber - Measure a fleet of Google servers for two and a half years: about a third of machines see at least one correctable memory error a year, far more than lab tests predicted.source

Used today

Server and workstation RAM - A 72-bit DIMM holds 64 data bits and 8 check bits per word; the controller corrects one flip on every read and raises a machine check on two.
Memory scrubbing - In the background the controller reads every word, corrects what it finds, and writes it back, so a single flip is gone before a second can land in the same word.
Caches and register files - On-chip SRAM in CPUs and GPUs carries the same code per line; a double error there is reported as a hardware fault rather than silently computed with.
Spacecraft memory - Where cosmic rays flip bits often, the same code is combined with scrubbing at a high rate and with interleaving so a single hit does not land two flips in one word.

second flipnone

syndrome: 101 = 5
overall: odd
verdict: one flip, fixed
fixed: bit 5
rate: 0.50 vs 0.57

extended-hamming-code.ts

import { DATA_POSITIONS, HAMMING_DATA, HAMMING_LENGTH, HammingCode, PARITY_POSITIONS } from "../binary/hamming-code";import type { Tracer } from "../trace";/** Eight positions, 1-based: the seven of the (7, 4) code and an overall parity bit at 8. */export const EXTENDED_LENGTH = 8;export const OVERALL_POSITION = 8;/** Every position the receiver checks: the three Hamming groups, then the whole word. */export const CHECK_POSITIONS = [1, 2, 4, 8] as const;/** The (7, 4) code's length and parity positions, re-exported so a stage can tone them without reaching into the binary area. */export const INNER_LENGTH = HAMMING_LENGTH;export const INNER_PARITY_POSITIONS = PARITY_POSITIONS;/** * What the receiver concludes: nothing wrong, one flip put back, two * flips reported and left alone, or the overall parity bit itself flipped. */export type SecdedVerdict = "clean" | "single" | "double" | "parity";export interface ExtendedHammingResult {  data: number[];  /** Eight bits, position 1 first; bit 8 makes the whole word even. */  codeword: number[];  received: number[];  /** The positions the noise inverted, in order. */  flips: number[];  /** The failing Hamming checks' positions added up: a position, or 0. */  syndrome: number;  /** The received word has an odd number of ones. */  odd: boolean;  verdict: SecdedVerdict;  /** The position flipped back, 0 when nothing was touched. */  position: number;  corrected: number[];  decoded: number[];  /** The decoded data matches what was sent. */  intact: boolean;}/** * The extended Hamming (8, 4) code, SECDED: single error corrected, * double error detected. The seven bits of the (7, 4) code get an * eighth, the parity of all seven, so every code word has an even * number of ones and the code's distance rises from three to four. * The receiver re-counts the three Hamming groups as before and the * whole word besides. One flip makes the word odd and the syndrome * names it; two flips leave the word even while the syndrome is not * zero, which no single flip can do, so the receiver reports the pair * instead of guessing a third position; a flip of the parity bit * alone makes the word odd with a syndrome of zero. ECC memory does * this at (72, 64), eight check bits per 64-bit word, and scrubs * single flips before a second can join them. * * Time: O(1), eight positions. Space: O(1). */export class ExtendedHammingCode {  /** The (7, 4) encoder, run without a tracer: this file emits every event itself. */  private readonly inner = new HammingCode();  constructor(private readonly tracer?: Tracer) {}  /** The positions a check at p covers: a Hamming group for 1, 2, 4; the whole word for 8. */  static covers(p: number): number[] {  static covers(checkAt: number): number[] {    if (p === OVERALL_POSITION) return Array.from({ length: EXTENDED_LENGTH }, (_, i) => i + 1);    if (checkAt === OVERALL_POSITION) return Array.from({ length: EXTENDED_LENGTH }, (_, i) => i + 1);    return HammingCode.covers(p);    return HammingCode.covers(checkAt);  }  /** Four data bits to eight: the (7, 4) code word, then a bit that makes all eight even. */  encode(data: readonly number[]): number[] {    if (data.length !== HAMMING_DATA) throw new RangeError(`expected ${HAMMING_DATA} data bits, got ${data.length}`);    const word = this.inner.encode(data);    const ones = word.reduce((sum, bit) => sum + bit, 0);    const onesCovered = word.reduce((sum, bit) => sum + bit, 0);    const parity = ones % 2;    const parity = onesCovered % 2;    const codeword = [...word, parity];    // ▸ add an eighth bit so the whole word has an even number of ones    this.tracer?.emit("extend", { codeword: [...codeword], ones, parity });    this.tracer?.emit("extend", { codeword: [...codeword], onesCovered, parity });    return codeword;  }  /** The word with the bit at a 1-based position inverted; 0 leaves it alone. */  flip(codeword: readonly number[], position: number): number[] {    const received = [...codeword];    const inRange = position >= 1 && position <= EXTENDED_LENGTH;    if (inRange) received[position - 1] = 1 - received[position - 1]!;    // ▸ the noise inverts a bit in transit    this.tracer?.emit("flip", { position, before: inRange ? codeword[position - 1] : null, received: [...received] });    return received;  }  /** Re-counts the three Hamming groups and the whole word: the failing groups add up to the syndrome, the whole word says odd or even. */  check(received: readonly number[]): { syndrome: number; odd: boolean } {    const word = [0, ...received];    let syndrome = 0;    let odd = false;    for (const p of CHECK_POSITIONS) {    for (const checkAt of CHECK_POSITIONS) {      const covered = ExtendedHammingCode.covers(p);      const covered = ExtendedHammingCode.covers(checkAt);      const ones = covered.reduce((sum, position) => sum + word[position]!, 0);      const onesCovered = covered.reduce((sum, position) => sum + word[position]!, 0);      const ok = ones % 2 === 0;      const ok = onesCovered % 2 === 0;      if (!ok && p === OVERALL_POSITION) odd = true;      if (!ok && checkAt === OVERALL_POSITION) odd = true;      else if (!ok) syndrome += p;      else if (!ok) syndrome += checkAt;      // ▸ re-count the group, or for 8 the whole word: still even, or not      this.tracer?.emit("check", { position: p, covers: covered, ones, ok });      this.tracer?.emit("check", { position: checkAt, covers: covered, onesCovered, ok });    }    return { syndrome, odd };  }  /** The decision table: syndrome and overall parity together say what happened and what to flip back. */  classify(syndrome: number, odd: boolean): { verdict: SecdedVerdict; position: number } {    if (syndrome === 0 && !odd) return { verdict: "clean", position: 0 };    if (syndrome !== 0 && odd) return { verdict: "single", position: syndrome };    if (syndrome !== 0) return { verdict: "double", position: 0 };    return { verdict: "parity", position: OVERALL_POSITION };  }  /** The word with the bit at a position flipped back; 0 leaves it alone. */  correct(received: readonly number[], position: number): number[] {    const corrected = [...received];    if (position >= 1 && position <= EXTENDED_LENGTH) corrected[position - 1] = 1 - corrected[position - 1]!;    // ▸ flip the named bit back; on two flips touch nothing and report them    this.tracer?.emit("correct", { position, corrected: [...corrected] });    return corrected;  }  /** Check, classify, correct what the verdict allows, and read the data off positions 3, 5, 6, 7. */  decode(received: readonly number[]): { syndrome: number; odd: boolean; verdict: SecdedVerdict; position: number; corrected: number[]; decoded: number[] } {    const { syndrome, odd } = this.check(received);    const { verdict, position } = this.classify(syndrome, odd);    // ▸ syndrome and overall parity together: clean, one flip, two flips, or the parity bit    this.tracer?.emit("verdict", { syndrome, bits: syndrome.toString(2).padStart(3, "0"), odd, verdict, position });    const corrected = this.correct(received, position);    const decoded = DATA_POSITIONS.map((p) => corrected[p - 1]!);    const decoded = DATA_POSITIONS.map((checkAt) => corrected[checkAt - 1]!);    return { syndrome, odd, verdict, position, corrected, decoded };  }  /** Encode, flip the chosen positions (0 for none), decode. */  run(data: readonly number[], flipAt = 0, flipAlso = 0): ExtendedHammingResult {    const codeword = this.encode(data);    const flips: number[] = [];    let received = this.flip(codeword, flipAt);    if (flipAt >= 1 && flipAt <= EXTENDED_LENGTH) flips.push(flipAt);    if (flipAlso >= 1 && flipAlso <= EXTENDED_LENGTH && flipAlso !== flipAt) {      received = this.flip(received, flipAlso);      flips.push(flipAlso);    }    const { syndrome, odd, verdict, position, corrected, decoded } = this.decode(received);    const intact = decoded.every((bit, i) => bit === (data[i]! & 1));    return { data: data.map((bit) => bit & 1), codeword, received, flips, syndrome, odd, verdict, position, corrected, decoded, intact };  }}

flips =: 1
verdict =: one flip, fixed
intact =: yes
rate =: 0.500

One flip, and the data came back right. Eight bits carry four, a rate of 0.500 against 0.571 for the (7, 4) code: one more bit buys the double-flip report.

s

o

flips

action

0

even

none

nothing

\neq 0

odd

one, at

s

flip bit

s

back

\neq 0

even

two

report, touch nothing

0

odd

the parity bit

flip bit

8

back

import { DATA_POSITIONS, HAMMING_DATA, HAMMING_LENGTH, HammingCode, PARITY_POSITIONS } from "../binary/hamming-code";import type { Tracer } from "../trace";/** Eight positions, 1-based: the seven of the (7, 4) code and an overall parity bit at 8. */export const EXTENDED_LENGTH = 8;export const OVERALL_POSITION = 8;/** Every position the receiver checks: the three Hamming groups, then the whole word. */export const CHECK_POSITIONS = [1, 2, 4, 8] as const;/** The (7, 4) code's length and parity positions, re-exported so a stage can tone them without reaching into the binary area. */export const INNER_LENGTH = HAMMING_LENGTH;export const INNER_PARITY_POSITIONS = PARITY_POSITIONS;/** * What the receiver concludes: nothing wrong, one flip put back, two * flips reported and left alone, or the overall parity bit itself flipped. */export type SecdedVerdict = "clean" | "single" | "double" | "parity";export interface ExtendedHammingResult { data: number[]; /** Eight bits, position 1 first; bit 8 makes the whole word even. */ codeword: number[]; received: number[]; /** The positions the noise inverted, in order. */ flips: number[]; /** The failing Hamming checks' positions added up: a position, or 0. */ syndrome: number; /** The received word has an odd number of ones. */ odd: boolean; verdict: SecdedVerdict; /** The position flipped back, 0 when nothing was touched. */ position: number; corrected: number[]; decoded: number[]; /** The decoded data matches what was sent. */ intact: boolean;}/** * The extended Hamming (8, 4) code, SECDED: single error corrected, * double error detected. The seven bits of the (7, 4) code get an * eighth, the parity of all seven, so every code word has an even * number of ones and the code's distance rises from three to four. * The receiver re-counts the three Hamming groups as before and the * whole word besides. One flip makes the word odd and the syndrome * names it; two flips leave the word even while the syndrome is not * zero, which no single flip can do, so the receiver reports the pair * instead of guessing a third position; a flip of the parity bit * alone makes the word odd with a syndrome of zero. ECC memory does * this at (72, 64), eight check bits per 64-bit word, and scrubs * single flips before a second can join them. * * Time: O(1), eight positions. Space: O(1). */export class ExtendedHammingCode { /** The (7, 4) encoder, run without a tracer: this file emits every event itself. */ private readonly inner = new HammingCode(); constructor(private readonly tracer?: Tracer) {} /** The positions a check at p covers: a Hamming group for 1, 2, 4; the whole word for 8. */ static covers(p: number): number[] { static covers(checkAt: number): number[] { if (p === OVERALL_POSITION) return Array.from({ length: EXTENDED_LENGTH }, (_, i) => i + 1); if (checkAt === OVERALL_POSITION) return Array.from({ length: EXTENDED_LENGTH }, (_, i) => i + 1); return HammingCode.covers(p); return HammingCode.covers(checkAt); } /** Four data bits to eight: the (7, 4) code word, then a bit that makes all eight even. */ encode(data: readonly number[]): number[] { if (data.length !== HAMMING_DATA) throw new RangeError(`expected ${HAMMING_DATA} data bits, got ${data.length}`); const word = this.inner.encode(data); const ones = word.reduce((sum, bit) => sum + bit, 0); const onesCovered = word.reduce((sum, bit) => sum + bit, 0); const parity = ones % 2; const parity = onesCovered % 2; const codeword = [...word, parity]; // ▸ add an eighth bit so the whole word has an even number of ones this.tracer?.emit("extend", { codeword: [...codeword], ones, parity }); this.tracer?.emit("extend", { codeword: [...codeword], onesCovered, parity }); return codeword; } /** The word with the bit at a 1-based position inverted; 0 leaves it alone. */ flip(codeword: readonly number[], position: number): number[] { const received = [...codeword]; const inRange = position >= 1 && position <= EXTENDED_LENGTH; if (inRange) received[position - 1] = 1 - received[position - 1]!; // ▸ the noise inverts a bit in transit this.tracer?.emit("flip", { position, before: inRange ? codeword[position - 1] : null, received: [...received] }); return received; } /** Re-counts the three Hamming groups and the whole word: the failing groups add up to the syndrome, the whole word says odd or even. */ check(received: readonly number[]): { syndrome: number; odd: boolean } { const word = [0, ...received]; let syndrome = 0; let odd = false; for (const p of CHECK_POSITIONS) { for (const checkAt of CHECK_POSITIONS) { const covered = ExtendedHammingCode.covers(p); const covered = ExtendedHammingCode.covers(checkAt); const ones = covered.reduce((sum, position) => sum + word[position]!, 0); const onesCovered = covered.reduce((sum, position) => sum + word[position]!, 0); const ok = ones % 2 === 0; const ok = onesCovered % 2 === 0; if (!ok && p === OVERALL_POSITION) odd = true; if (!ok && checkAt === OVERALL_POSITION) odd = true; else if (!ok) syndrome += p; else if (!ok) syndrome += checkAt; // ▸ re-count the group, or for 8 the whole word: still even, or not this.tracer?.emit("check", { position: p, covers: covered, ones, ok }); this.tracer?.emit("check", { position: checkAt, covers: covered, onesCovered, ok }); } return { syndrome, odd }; } /** The decision table: syndrome and overall parity together say what happened and what to flip back. */ classify(syndrome: number, odd: boolean): { verdict: SecdedVerdict; position: number } { if (syndrome === 0 && !odd) return { verdict: "clean", position: 0 }; if (syndrome !== 0 && odd) return { verdict: "single", position: syndrome }; if (syndrome !== 0) return { verdict: "double", position: 0 }; return { verdict: "parity", position: OVERALL_POSITION }; } /** The word with the bit at a position flipped back; 0 leaves it alone. */ correct(received: readonly number[], position: number): number[] { const corrected = [...received]; if (position >= 1 && position <= EXTENDED_LENGTH) corrected[position - 1] = 1 - corrected[position - 1]!; // ▸ flip the named bit back; on two flips touch nothing and report them this.tracer?.emit("correct", { position, corrected: [...corrected] }); return corrected; } /** Check, classify, correct what the verdict allows, and read the data off positions 3, 5, 6, 7. */ decode(received: readonly number[]): { syndrome: number; odd: boolean; verdict: SecdedVerdict; position: number; corrected: number[]; decoded: number[] } { const { syndrome, odd } = this.check(received); const { verdict, position } = this.classify(syndrome, odd); // ▸ syndrome and overall parity together: clean, one flip, two flips, or the parity bit this.tracer?.emit("verdict", { syndrome, bits: syndrome.toString(2).padStart(3, "0"), odd, verdict, position }); const corrected = this.correct(received, position); const decoded = DATA_POSITIONS.map((p) => corrected[p - 1]!); const decoded = DATA_POSITIONS.map((checkAt) => corrected[checkAt - 1]!); return { syndrome, odd, verdict, position, corrected, decoded }; } /** Encode, flip the chosen positions (0 for none), decode. */ run(data: readonly number[], flipAt = 0, flipAlso = 0): ExtendedHammingResult { const codeword = this.encode(data); const flips: number[] = []; let received = this.flip(codeword, flipAt); if (flipAt >= 1 && flipAt <= EXTENDED_LENGTH) flips.push(flipAt); if (flipAlso >= 1 && flipAlso <= EXTENDED_LENGTH && flipAlso !== flipAt) { received = this.flip(received, flipAlso); flips.push(flipAlso); } const { syndrome, odd, verdict, position, corrected, decoded } = this.decode(received); const intact = decoded.every((bit, i) => bit === (data[i]! & 1)); return { data: data.map((bit) => bit & 1), codeword, received, flips, syndrome, odd, verdict, position, corrected, decoded, intact }; }}