Hamming Codes: Fixing a Flipped Bit

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Hamming code

Loading interactive demo…

Five rows of seven positions. The data row holds four bits at positions 3, 5, 6, and 7; the code word row adds a parity bit at 1, 2, and 4, each making its group even; the received row is what the noise left; the checks row re-counts each group; the corrected row flips the bit the failing checks name. 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 HammingCode class from the published library executing in your browser, with the current line highlighted.

The parity bit being set or checked, ringed with the positions it covers.
Parity bits, at the power-of-two positions.
A bit the noise flipped, and a check that failed.
A check that passed, and the bit the correction flipped back.
Rows the run has not reached yet, ghosted.

syndrome is the failing checks' positions added up, in binary and decimal, fixed the position flipped back, decoded whether the data came through, rate the data bits per bit sent against sending each bit three times.

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

Positions and groups. Number the seven positions $1$ to $7$ and write each number in binary: $001, 010, 011, 100, 101, 110, 111$ . The powers of two, $1$ , $2$ , and $4$ , have a single bit set; they hold the parity bits. Parity bit $p$ covers every position whose number has $p$ 's bit set, so position $5 = 101$ is covered by $1$ and $4$ , and position $7 = 111$ by all three. Each parity bit is chosen to make its group's count of ones even.

The syndrome. The receiver re-counts every group. A single flip at position $k$ breaks exactly the groups whose bit is set in $k$ , and no others, so

\text{syndrome} = \sum_{\text{failing } p} p = k ,

the position of the flip, in binary. Flip it back and the word is restored. No flip at all leaves every group even and a syndrome of $0$ , which is why $0$ is not a position.

Distance. Two code words differ in at least three positions, since changing one data bit changes it and at least two parity groups (every data position is in at least two groups). So a word with one flip is still nearer its original than any other code word, and the decoder picks right; a word with two flips may be nearer a wrong one, and the syndrome then names a third position. The second flip slider shows it: the code's minimum distance is $3$ , which buys one correction or two detections, never both. An eighth bit, the parity of all seven, extends the code to distance $4$ : one corrected and two detected, the form ECC memory uses.

Rate and the limit. Four data bits in seven is a rate of $4/7 \approx 0.571$ ; sending each bit three times and voting corrects a single flip per triple at $1/3$ . The general Hamming code with $r$ parity bits has length $2^r - 1$ and rate $(2^r - 1 - r) / (2^r - 1)$ , which tends to $1$ ; but it still corrects only one flip per word, so its reliability on a channel that flips $f$ of the bits falls as the word grows. Capacity, the previous lesson's $1 - H(f)$ , is reached by codes that correct many flips per long word, which is what the fifty years after Hamming were spent building.

Why it is perfect. The $16$ code words each own their $7$ single-flip neighbours; $16 \times 8 = 128 = 2^7$ , so every seven-bit word is a code word or one flip from exactly one. Nothing is wasted, and no shorter code of the same rate could do the job.

In 1947 Richard Hamming ran long jobs on Bell Labs' relay computer over the weekends, when nobody else was there. The machine checked each word with a parity bit, and when a relay misfired it dropped the job and moved on to the next, so on Monday he found nothing. If the machine could tell a bit was wrong, he asked, why could it not say which one? Three years of thinking about that produced the first codes that correct an error rather than just notice it, published in 1950 the moment the patent allowed, and the notion of distance between code words that every later code is measured by.

1948Claude Shannon - Proves that codes approaching channel capacity exist, and cites Hamming's then-unpublished (7, 4) code as the one concrete example he knows.source
1949Marcel Golay - Publishes a half-page note generalising Hamming's construction and giving the perfect binary and ternary Golay codes.source
1950Richard Hamming - Publishes 'Error Detecting and Error Correcting Codes', with the (7, 4) code, the whole family, and the distance that bears his name.source
1960Irving Reed and Gustave Solomon - Introduce codes over larger alphabets that correct bursts of errors; they protect CDs, QR codes, and deep-space links.source
1970sMemory makers - ECC memory adopts an extended Hamming code, one error corrected and two detected per 64-bit word, which servers still use.source

Used today

ECC memory - Server RAM stores 72 bits per 64-bit word, an extended Hamming code that fixes any single flipped bit and flags any two.
Flash and disks - Every sector and page carries a correcting code; without one, modern storage densities would not be readable.
The hat puzzle - Seven players guessing their own hat colours win 7 times in 8 by agreeing on a Hamming code: a favourite puzzle for the code's covering property.

second flipnone

syndrome: 101 = 5
fixed: bit 5
decoded: 1011 intact
rate: 4/7 vs 1/3

hamming-code.ts

import type { Tracer } from "../trace";/** Code word positions are 1-based; a parity bit sits at each power of two. */export const HAMMING_LENGTH = 7;export const HAMMING_DATA = 4;export const PARITY_POSITIONS = [1, 2, 4] as const;export const DATA_POSITIONS = [3, 5, 6, 7] as const;export interface HammingResult {  data: number[];  /** Seven bits, position 1 first. */  codeword: number[];  received: number[];  /** The positions whose check failed, added up: the position of a single flipped bit, or 0. */  syndrome: number;  corrected: number[];  decoded: number[];  /** The decoded data matches what was sent. */  intact: boolean;}/** * The Hamming (7, 4) code: four data bits become seven, with a parity * bit at each power-of-two position covering every position whose * number has that bit set. A received word is checked the same way, * and the failing checks, added up, spell the position of a single * flipped bit in binary, so the decoder flips it back. Two flips * still produce a syndrome, but one that names the wrong position, * and the corrected word is wrong: the code's distance is three, one * error corrected or two detected, not both. Four bits in seven is a * rate of 4/7, against 1/3 for sending each bit three times. * * Time: O(1), seven positions. Space: O(1). */export class HammingCode {  constructor(private readonly tracer?: Tracer) {}  /** The positions a parity bit at p covers: every position whose number has p's bit set, p itself included. */  static covers(p: number): number[] {  static covers(parityAt: number): number[] {    const out: number[] = [];    for (let position = 1; position <= HAMMING_LENGTH; position++) if ((position & p) !== 0) out.push(position);    for (let position = 1; position <= HAMMING_LENGTH; position++) if ((position & parityAt) !== 0) out.push(position);    return out;  }  /** Four data bits to seven: data at 3, 5, 6, 7, then each parity bit set so its group has an even number of ones. */  encode(data: readonly number[]): number[] {    if (data.length !== HAMMING_DATA) throw new RangeError(`expected ${HAMMING_DATA} data bits, got ${data.length}`);    const word = new Array<number>(HAMMING_LENGTH + 1).fill(0);    DATA_POSITIONS.forEach((position, i) => {      word[position] = data[i]! & 1;    });    for (const p of PARITY_POSITIONS) {    for (const parityAt of PARITY_POSITIONS) {      const covered = HammingCode.covers(p).filter((position) => position !== p);      const covered = HammingCode.covers(parityAt).filter((position) => position !== parityAt);      const ones = covered.reduce((sum, position) => sum + word[position]!, 0);      const onesCovered = covered.reduce((sum, position) => sum + word[position]!, 0);      word[p] = ones % 2;      word[parityAt] = onesCovered % 2;      // ▸ set the parity bit so its group has an even number of ones      this.tracer?.emit("parity", { position: p, covers: covered, ones, parity: word[p] });      this.tracer?.emit("parity", { position: parityAt, covers: covered, onesCovered, parity: word[parityAt] });    }    return word.slice(1);  }  /** 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];    if (position >= 1 && position <= HAMMING_LENGTH) received[position - 1] = 1 - received[position - 1]!;    // ▸ the noise inverts a bit in transit    this.tracer?.emit("flip", { position, before: position >= 1 && position <= HAMMING_LENGTH ? codeword[position - 1] : null, received: [...received] });    return received;  }  /** Re-checks every parity group; the failing positions add up to the flipped position, which is flipped back. */  decode(received: readonly number[]): { syndrome: number; corrected: number[]; decoded: number[] } {    const word = [0, ...received];    let syndrome = 0;    for (const p of PARITY_POSITIONS) {    for (const parityAt of PARITY_POSITIONS) {      const covered = HammingCode.covers(p);      const covered = HammingCode.covers(parityAt);      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) syndrome += p;      if (!ok) syndrome += parityAt;      // ▸ re-count the group: still even, or not      this.tracer?.emit("check", { position: p, covers: covered, ones, ok });      this.tracer?.emit("check", { position: parityAt, covers: covered, onesCovered, ok });    }    // ▸ the failing groups' positions add up to the flipped position    this.tracer?.emit("syndrome", { syndrome, bits: syndrome.toString(2).padStart(3, "0") });    const corrected = [...received];    if (syndrome >= 1 && syndrome <= HAMMING_LENGTH) corrected[syndrome - 1] = 1 - corrected[syndrome - 1]!;    // ▸ flip the bit at that position back; 0 means nothing to fix    this.tracer?.emit("correct", { position: syndrome, corrected: [...corrected] });    const decoded = DATA_POSITIONS.map((position) => corrected[position - 1]!);    return { syndrome, corrected, decoded };  }  /** Encode, flip the chosen positions (0 for none), decode. */  run(data: readonly number[], flipAt: number, flipAlso = 0): HammingResult {    const codeword = this.encode(data);    let received = this.flip(codeword, flipAt);    if (flipAlso >= 1 && flipAlso <= HAMMING_LENGTH && flipAlso !== flipAt) received = this.flip(received, flipAlso);    const { syndrome, corrected, decoded } = this.decode(received);    const intact = decoded.every((bit, i) => bit === (data[i]! & 1));    return { data: data.map((bit) => bit & 1), codeword, received, syndrome, corrected, decoded, intact };  }}

flips =: 1
intact =: yes
rate =: 0.571

One flip, and the data came back right: 4 bits in 7, a rate of 0.571, against 0.333 for sending each bit three times.

import type { Tracer } from "../trace";/** Code word positions are 1-based; a parity bit sits at each power of two. */export const HAMMING_LENGTH = 7;export const HAMMING_DATA = 4;export const PARITY_POSITIONS = [1, 2, 4] as const;export const DATA_POSITIONS = [3, 5, 6, 7] as const;export interface HammingResult { data: number[]; /** Seven bits, position 1 first. */ codeword: number[]; received: number[]; /** The positions whose check failed, added up: the position of a single flipped bit, or 0. */ syndrome: number; corrected: number[]; decoded: number[]; /** The decoded data matches what was sent. */ intact: boolean;}/** * The Hamming (7, 4) code: four data bits become seven, with a parity * bit at each power-of-two position covering every position whose * number has that bit set. A received word is checked the same way, * and the failing checks, added up, spell the position of a single * flipped bit in binary, so the decoder flips it back. Two flips * still produce a syndrome, but one that names the wrong position, * and the corrected word is wrong: the code's distance is three, one * error corrected or two detected, not both. Four bits in seven is a * rate of 4/7, against 1/3 for sending each bit three times. * * Time: O(1), seven positions. Space: O(1). */export class HammingCode { constructor(private readonly tracer?: Tracer) {} /** The positions a parity bit at p covers: every position whose number has p's bit set, p itself included. */ static covers(p: number): number[] { static covers(parityAt: number): number[] { const out: number[] = []; for (let position = 1; position <= HAMMING_LENGTH; position++) if ((position & p) !== 0) out.push(position); for (let position = 1; position <= HAMMING_LENGTH; position++) if ((position & parityAt) !== 0) out.push(position); return out; } /** Four data bits to seven: data at 3, 5, 6, 7, then each parity bit set so its group has an even number of ones. */ encode(data: readonly number[]): number[] { if (data.length !== HAMMING_DATA) throw new RangeError(`expected ${HAMMING_DATA} data bits, got ${data.length}`); const word = new Array<number>(HAMMING_LENGTH + 1).fill(0); DATA_POSITIONS.forEach((position, i) => { word[position] = data[i]! & 1; }); for (const p of PARITY_POSITIONS) { for (const parityAt of PARITY_POSITIONS) { const covered = HammingCode.covers(p).filter((position) => position !== p); const covered = HammingCode.covers(parityAt).filter((position) => position !== parityAt); const ones = covered.reduce((sum, position) => sum + word[position]!, 0); const onesCovered = covered.reduce((sum, position) => sum + word[position]!, 0); word[p] = ones % 2; word[parityAt] = onesCovered % 2; // ▸ set the parity bit so its group has an even number of ones this.tracer?.emit("parity", { position: p, covers: covered, ones, parity: word[p] }); this.tracer?.emit("parity", { position: parityAt, covers: covered, onesCovered, parity: word[parityAt] }); } return word.slice(1); } /** 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]; if (position >= 1 && position <= HAMMING_LENGTH) received[position - 1] = 1 - received[position - 1]!; // ▸ the noise inverts a bit in transit this.tracer?.emit("flip", { position, before: position >= 1 && position <= HAMMING_LENGTH ? codeword[position - 1] : null, received: [...received] }); return received; } /** Re-checks every parity group; the failing positions add up to the flipped position, which is flipped back. */ decode(received: readonly number[]): { syndrome: number; corrected: number[]; decoded: number[] } { const word = [0, ...received]; let syndrome = 0; for (const p of PARITY_POSITIONS) { for (const parityAt of PARITY_POSITIONS) { const covered = HammingCode.covers(p); const covered = HammingCode.covers(parityAt); 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) syndrome += p; if (!ok) syndrome += parityAt; // ▸ re-count the group: still even, or not this.tracer?.emit("check", { position: p, covers: covered, ones, ok }); this.tracer?.emit("check", { position: parityAt, covers: covered, onesCovered, ok }); } // ▸ the failing groups' positions add up to the flipped position this.tracer?.emit("syndrome", { syndrome, bits: syndrome.toString(2).padStart(3, "0") }); const corrected = [...received]; if (syndrome >= 1 && syndrome <= HAMMING_LENGTH) corrected[syndrome - 1] = 1 - corrected[syndrome - 1]!; // ▸ flip the bit at that position back; 0 means nothing to fix this.tracer?.emit("correct", { position: syndrome, corrected: [...corrected] }); const decoded = DATA_POSITIONS.map((position) => corrected[position - 1]!); return { syndrome, corrected, decoded }; } /** Encode, flip the chosen positions (0 for none), decode. */ run(data: readonly number[], flipAt: number, flipAlso = 0): HammingResult { const codeword = this.encode(data); let received = this.flip(codeword, flipAt); if (flipAlso >= 1 && flipAlso <= HAMMING_LENGTH && flipAlso !== flipAt) received = this.flip(received, flipAlso); const { syndrome, corrected, decoded } = this.decode(received); const intact = decoded.every((bit, i) => bit === (data[i]! & 1)); return { data: data.map((bit) => bit & 1), codeword, received, syndrome, corrected, decoded, intact }; }}