Parity: One Bit That Notices

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

Parity grid

Loading interactive demo…

The data bits laid out as a grid, with a parity bit at the end of every row and, below every column, one more: each makes its line count an even number of ones. The noise flips the cells you tap; the receiver counts every line again, and one failing row and one failing column cross at the flipped cell. Switch the size to 1x8 for a byte with a single parity bit, which only notices.Take the tour, or press and explore. Legend:

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

The line being counted, and the located cell.
Parity bits: the last column, the bottom row, the corner.
A cell the noise flipped, and a line whose count came out odd.
The cell flipped back.
Parity bits the run has not set yet, ghosted.

rows failing and cols failing list the lines whose count came out odd, verdict whether the flip was placed, only noticed, or nothing was found, rate the data bits per bit sent.

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

Even parity. A line of bits $b_1 \dots b_n$ gets one more bit,

p = b_1 \oplus b_2 \oplus \cdots \oplus b_n ,

the XOR of them all, which is $1$ exactly when the line holds an odd number of ones. With $p$ appended the line always counts even. The receiver XORs the whole line again: $0$ means every bit is as sent or an even number flipped, $1$ means an odd number flipped. One flip is noticed. Where it is, the single bit cannot say, and two flips cancel and pass. Switch the stage to 1x8 to watch a byte do exactly that.

Two dimensions. Lay $r \times c$ data bits in a grid, give every row a parity bit and every column one, and let the corner be the parity of the parity column, which makes it the parity of the parity row too. A single flip at $(i, j)$ now makes row $i$ odd and column $j$ odd and nothing else, so the receiver's two passes return one failing row and one failing column, and they cross at the flipped cell. That holds for the parity bits as well: a flipped row parity fails its row and the parity column; a flipped corner fails the parity row and the parity column. Twenty-five cells, every one of them placed.

Two flips. Put them in one row and that row counts even again, while two columns fail: damage is reported, but two columns and no row do not cross anywhere. Put them in different rows and columns and two rows and two columns fail, four cells the flips might be at. Either way the receiver can only ask for the grid again. The grid is a code of minimum distance $4$ : one flip corrected or two detected, and three flips at the corners of a rectangle are miscorrected to the fourth corner, since the received grid is then one flip from another valid grid.

Rate. The grid sends $rc$ data bits in $(r + 1)(c + 1)$ : $16$ of $25$ for the default, $36$ of $49$ at 6x6, tending to $1$ as the grid grows while still placing only one flip. The byte with its single bit sends $8$ of $9$ and places nothing.

Sums that catch more. A checksum folds a message into a few bytes by arithmetic instead of a single XOR: the Internet checksum adds the 16-bit words in one's complement; Fletcher's keeps two running sums so that the position of a byte matters; Luhn's check digit weights every other digit so a swap is seen. Each catches far more than one flip, and none can say where, because a sum of the whole message has no row or column to cross. The next step is a checksum built from polynomial division, which catches every burst up to its length: the CRC.

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

One row is the 1D case. rows === 1 switches the column pass off: a column of a single bit would just copy it, turning the scheme into a repetition code, so the byte with a parity bit is the same class with twoDimensional false.
The corner comes from the column pass, which runs over the parity column like any other column; there is no special case, and that is why a flipped parity bit is placed like a data bit.
checkLine is one call for both axes. The app maps a trace tag to the source line of its emit, so a row check and a column check go through the same method with an axis in the payload.
locate is a two-line rule: nothing failing is clean, one row and one column crossing is corrected, anything else is only detected. It never guesses among several candidate cells.
intact compares the data region only, so a flip in a parity bit that is left alone (as in 1D) still counts as intact data.

The parity bit is older than the computer: teleprinters added a bit that made each character count even, so the far end could ring a bell when one arrived odd. Bell Labs' relay computers checked every word the same way and halted the job when a relay misfired. Richard Hamming's 1950 paper, written out of frustration with those halts, named the single parity check as the simplest code of all and, a few pages on, described laying bits in a rectangle with a parity bit on every row and column: the arrangement that says where a flip was, not only that there was one.

1950Richard Hamming - 'Error Detecting and Error Correcting Codes' opens with the single parity check and describes rectangular codes, a parity bit per row and per column, as a first way to locate an error.source
1954Peter Elias - Generalises the rectangle to product codes, where any two codes are laid out as the rows and columns of one array and decoded a dimension at a time.source
1954Hans Peter Luhn - Files the check-digit formula that credit card and IMEI numbers still carry: a weighted sum of the digits that catches any single wrong digit and most swapped neighbours.source
1981The Internet Protocol - RFC 791 checks every IP header with a one's complement sum of its 16-bit words, a checksum cheap enough for a router to verify on every packet.source
1988Patterson, Gibson, and Katz - The RAID paper puts a parity stripe across a set of disks: the XOR of the others, from which any one lost disk is rebuilt.source

Used today

Serial links - A UART can send each byte with a parity bit, even or odd, and flag the frame when the count comes out wrong: the 8-N-1 and 7-E-1 of a terminal setting.
Parity memory - PCs of the 1980s and 1990s stored nine bits per byte; a parity error halted the machine rather than let a flipped bit run.
RAID 5 - One stripe in each row holds the XOR of the others, so a failed disk is rebuilt bit by bit from what remains: row parity, with disks for columns.
Checksums - The Internet checksum, Fletcher's, and Adler-32 fold a message into a few bytes that catch far more than one flip, and still cannot say where.

size

data7

rows failing: 1
cols failing: 2
verdict: corrected
rate: 16/25

parity-grid.ts

import type { Tracer } from "../trace";export const MAX_PARITY_ROWS = 8;export const MAX_PARITY_COLS = 8;export type ParityVerdict = "clean" | "corrected" | "detected";/** A cell of the grid, row 0 at the top; the parity column is column `cols`, the parity row is row `rows`. */export interface GridCell {  row: number;  col: number;}export interface ParityGridResult {  rows: number;  cols: number;  /** The data bits, row-major. */  data: number[];  /** The encoded grid: data with a parity column, and (in 2D) a parity row whose corner guards the parity column. */  grid: number[][];  received: number[][];  flips: GridCell[];  failingRows: number[];  failingCols: number[];  verdict: ParityVerdict;  /** The cell the correction flipped back, or null. */  position: GridCell | null;  corrected: number[][];  /** The data region of the corrected grid matches what was sent. */  intact: boolean;}/** * Parity, in one and two dimensions. A parity bit makes its line hold * an even number of ones, so a single flip anywhere in the line is * noticed when the receiver counts again. One row of data and its bit * (the byte with a parity bit) can only notice. Lay the data out as a * grid, give every row a parity bit and every column one too (the * corner guards the parity column), and a single flip fails exactly one * row and one column, which cross at the flipped cell: noticed and * placed, so it can be put back. Two flips fail two lines on some axis, * or none when they share a line, and can be noticed but not placed; * four flips on the corners of a rectangle fail nothing at all. * * Time: O(rows * cols). Space: O(rows * cols). */export class ParityGrid {  constructor(    readonly rows = 4,    readonly cols = 4,    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(rows) || rows < 1 || rows > MAX_PARITY_ROWS) throw new RangeError(`rows must be 1 to ${MAX_PARITY_ROWS}, got ${rows}`);    if (!Number.isInteger(cols) || cols < 1 || cols > MAX_PARITY_COLS) throw new RangeError(`cols must be 1 to ${MAX_PARITY_COLS}, got ${cols}`);  }  /** One row of data is the 1D case: a parity bit per row and no column pass. */  get twoDimensional(): boolean {    return this.rows > 1;  }  /** Rows of the encoded grid: the data rows plus the parity row in 2D. */  get height(): number {    return this.twoDimensional ? this.rows + 1 : 1;  }  /** Columns of the encoded grid: the data columns plus the parity column. */  get width(): number {    return this.cols + 1;  }  /** The even-parity bit of some bits: 1 when they hold an odd number of ones. */  static parity(bits: readonly number[]): number {  static parity(lineBits: readonly number[]): number {    return bits.reduce((sum, bit) => sum ^ (bit & 1), 0);    return lineBits.reduce((sum, bit) => sum ^ (bit & 1), 0);  }  /** Lays the data out in rows, appends a parity bit to each, and (in 2D) a parity row under every column, the parity column included. */  encode(data: readonly number[]): number[][] {    if (data.length !== this.rows * this.cols) throw new RangeError(`expected ${this.rows * this.cols} data bits, got ${data.length}`);    const grid: number[][] = [];    for (let row = 0; row < this.rows; row++) {      const bits = data.slice(row * this.cols, (row + 1) * this.cols).map((bit) => bit & 1);      const lineBits = data.slice(row * this.cols, (row + 1) * this.cols).map((bit) => bit & 1);      const ones = bits.reduce((sum, bit) => sum + bit, 0);      const onesInLine = lineBits.reduce((sum, bit) => sum + bit, 0);      const parity = ones % 2;      const parity = onesInLine % 2;      grid.push([...bits, parity]);      grid.push([...lineBits, parity]);      // ▸ append a bit that makes the row's count of ones even      this.tracer?.emit("parity-row", { row, bits, ones, parity });      this.tracer?.emit("parity-row", { row, lineBits, onesInLine, parity });    }    if (this.twoDimensional) {      const parityRow: number[] = [];      for (let col = 0; col < this.width; col++) {        const bits = grid.map((line) => line[col]!);        const lineBits = grid.map((line) => line[col]!);        const ones = bits.reduce((sum, bit) => sum + bit, 0);        const onesInLine = lineBits.reduce((sum, bit) => sum + bit, 0);        const parity = ones % 2;        const parity = onesInLine % 2;        parityRow.push(parity);        // ▸ a bit under each column, the parity column too        this.tracer?.emit("parity-col", { col, bits, ones, parity });        this.tracer?.emit("parity-col", { col, lineBits, onesInLine, parity });      }      grid.push(parityRow);    }    return grid;  }  /** The grid with one cell inverted; a null cell is the noise leaving the word alone. */  flip(grid: readonly (readonly number[])[], cell: GridCell | null): number[][] {    const received = grid.map((line) => [...line]);    const inside = cell !== null && cell.row >= 0 && cell.row < this.height && cell.col >= 0 && cell.col < this.width;    const before = inside ? received[cell.row]![cell.col]! : null;    if (inside) received[cell.row]![cell.col] = 1 - before!;    // ▸ the noise inverts the cells it hits    this.tracer?.emit("flip", { row: inside ? cell.row : null, col: inside ? cell.col : null, before, received: received.map((line) => [...line]) });    return received;  }  /** Counts every row and (in 2D) every column again: a line with an odd count fails. */  check(received: readonly (readonly number[])[]): { failingRows: number[]; failingCols: number[] } {    const failingRows: number[] = [];    const failingCols: number[] = [];    for (let row = 0; row < this.height; row++) {      if (!this.checkLine("row", row, received[row]!)) failingRows.push(row);    }    if (this.twoDimensional) {      for (let col = 0; col < this.width; col++) {        if (!this.checkLine("col", col, received.map((line) => line[col]!))) failingCols.push(col);      }    }    return { failingRows, failingCols };  }  /** One line counted again: still even, or not. The same call for a row and a column, so one tag traces both passes. */  private checkLine(axis: "row" | "col", index: number, bits: readonly number[]): boolean {  private checkLine(axis: "row" | "col", index: number, lineBits: readonly number[]): boolean {    const ones = bits.reduce((sum, bit) => sum + bit, 0);    const onesInLine = lineBits.reduce((sum, bit) => sum + bit, 0);    const ok = ones % 2 === 0;    const ok = onesInLine % 2 === 0;    // ▸ count the line again: still even, or not    this.tracer?.emit("check", { axis, index, ones, ok });    this.tracer?.emit("check", { axis, index, onesInLine, ok });    return ok;  }  /** One failing row and one failing column cross at the flipped cell; nothing failing is clean; anything else is noticed but not placed. */  locate(failingRows: readonly number[], failingCols: readonly number[]): { verdict: ParityVerdict; position: GridCell | null } {    let verdict: ParityVerdict = "detected";    let position: GridCell | null = null;    if (failingRows.length === 0 && failingCols.length === 0) verdict = "clean";    else if (failingRows.length === 1 && failingCols.length === 1) {      verdict = "corrected";      position = { row: failingRows[0]!, col: failingCols[0]! };    }    // ▸ one failing row and one failing column cross at the flip    this.tracer?.emit("locate", { rows: [...failingRows], cols: [...failingCols], verdict, position: position ? { ...position } : null });    return { verdict, position };  }  /** Flips the located cell back; with no position the received grid is handed on as it is. */  correct(received: readonly (readonly number[])[], position: GridCell | null): number[][] {    const corrected = received.map((line) => [...line]);    if (position) corrected[position.row]![position.col] = 1 - corrected[position.row]![position.col]!;    // ▸ flip that cell back; nothing to fix, or only noticed    this.tracer?.emit("correct", { position: position ? { ...position } : null, corrected: corrected.map((line) => [...line]) });    return corrected;  }  /** Encode, flip the chosen cells (none for a clean run), check every line, locate, correct. */  run(data: readonly number[], flips: readonly GridCell[] = []): ParityGridResult {    const grid = this.encode(data);    let received: number[][] = grid.map((line) => [...line]);    if (flips.length === 0) received = this.flip(received, null);    for (const cell of flips) received = this.flip(received, cell);    const { failingRows, failingCols } = this.check(received);    const { verdict, position } = this.locate(failingRows, failingCols);    const corrected = this.correct(received, position);    const intact = data.every((bit, i) => (bit & 1) === corrected[Math.floor(i / this.cols)]![i % this.cols]);    return {      rows: this.rows,      cols: this.cols,      data: data.map((bit) => bit & 1),      grid,      received,      flips: flips.map((cell) => ({ ...cell })),      failingRows,      failingCols,      verdict,      position,      corrected,      intact,    };  }}

flips =: 1
verdict =: corrected
intact =: yes
rate =: 0.64

One flip, placed and put back: the data came through at a rate of 0.64 data bits per bit sent.

import type { Tracer } from "../trace";export const MAX_PARITY_ROWS = 8;export const MAX_PARITY_COLS = 8;export type ParityVerdict = "clean" | "corrected" | "detected";/** A cell of the grid, row 0 at the top; the parity column is column `cols`, the parity row is row `rows`. */export interface GridCell { row: number; col: number;}export interface ParityGridResult { rows: number; cols: number; /** The data bits, row-major. */ data: number[]; /** The encoded grid: data with a parity column, and (in 2D) a parity row whose corner guards the parity column. */ grid: number[][]; received: number[][]; flips: GridCell[]; failingRows: number[]; failingCols: number[]; verdict: ParityVerdict; /** The cell the correction flipped back, or null. */ position: GridCell | null; corrected: number[][]; /** The data region of the corrected grid matches what was sent. */ intact: boolean;}/** * Parity, in one and two dimensions. A parity bit makes its line hold * an even number of ones, so a single flip anywhere in the line is * noticed when the receiver counts again. One row of data and its bit * (the byte with a parity bit) can only notice. Lay the data out as a * grid, give every row a parity bit and every column one too (the * corner guards the parity column), and a single flip fails exactly one * row and one column, which cross at the flipped cell: noticed and * placed, so it can be put back. Two flips fail two lines on some axis, * or none when they share a line, and can be noticed but not placed; * four flips on the corners of a rectangle fail nothing at all. * * Time: O(rows * cols). Space: O(rows * cols). */export class ParityGrid { constructor( readonly rows = 4, readonly cols = 4, private readonly tracer?: Tracer, ) { if (!Number.isInteger(rows) || rows < 1 || rows > MAX_PARITY_ROWS) throw new RangeError(`rows must be 1 to ${MAX_PARITY_ROWS}, got ${rows}`); if (!Number.isInteger(cols) || cols < 1 || cols > MAX_PARITY_COLS) throw new RangeError(`cols must be 1 to ${MAX_PARITY_COLS}, got ${cols}`); } /** One row of data is the 1D case: a parity bit per row and no column pass. */ get twoDimensional(): boolean { return this.rows > 1; } /** Rows of the encoded grid: the data rows plus the parity row in 2D. */ get height(): number { return this.twoDimensional ? this.rows + 1 : 1; } /** Columns of the encoded grid: the data columns plus the parity column. */ get width(): number { return this.cols + 1; } /** The even-parity bit of some bits: 1 when they hold an odd number of ones. */ static parity(bits: readonly number[]): number { static parity(lineBits: readonly number[]): number { return bits.reduce((sum, bit) => sum ^ (bit & 1), 0); return lineBits.reduce((sum, bit) => sum ^ (bit & 1), 0); } /** Lays the data out in rows, appends a parity bit to each, and (in 2D) a parity row under every column, the parity column included. */ encode(data: readonly number[]): number[][] { if (data.length !== this.rows * this.cols) throw new RangeError(`expected ${this.rows * this.cols} data bits, got ${data.length}`); const grid: number[][] = []; for (let row = 0; row < this.rows; row++) { const bits = data.slice(row * this.cols, (row + 1) * this.cols).map((bit) => bit & 1); const lineBits = data.slice(row * this.cols, (row + 1) * this.cols).map((bit) => bit & 1); const ones = bits.reduce((sum, bit) => sum + bit, 0); const onesInLine = lineBits.reduce((sum, bit) => sum + bit, 0); const parity = ones % 2; const parity = onesInLine % 2; grid.push([...bits, parity]); grid.push([...lineBits, parity]); // ▸ append a bit that makes the row's count of ones even this.tracer?.emit("parity-row", { row, bits, ones, parity }); this.tracer?.emit("parity-row", { row, lineBits, onesInLine, parity }); } if (this.twoDimensional) { const parityRow: number[] = []; for (let col = 0; col < this.width; col++) { const bits = grid.map((line) => line[col]!); const lineBits = grid.map((line) => line[col]!); const ones = bits.reduce((sum, bit) => sum + bit, 0); const onesInLine = lineBits.reduce((sum, bit) => sum + bit, 0); const parity = ones % 2; const parity = onesInLine % 2; parityRow.push(parity); // ▸ a bit under each column, the parity column too this.tracer?.emit("parity-col", { col, bits, ones, parity }); this.tracer?.emit("parity-col", { col, lineBits, onesInLine, parity }); } grid.push(parityRow); } return grid; } /** The grid with one cell inverted; a null cell is the noise leaving the word alone. */ flip(grid: readonly (readonly number[])[], cell: GridCell | null): number[][] { const received = grid.map((line) => [...line]); const inside = cell !== null && cell.row >= 0 && cell.row < this.height && cell.col >= 0 && cell.col < this.width; const before = inside ? received[cell.row]![cell.col]! : null; if (inside) received[cell.row]![cell.col] = 1 - before!; // ▸ the noise inverts the cells it hits this.tracer?.emit("flip", { row: inside ? cell.row : null, col: inside ? cell.col : null, before, received: received.map((line) => [...line]) }); return received; } /** Counts every row and (in 2D) every column again: a line with an odd count fails. */ check(received: readonly (readonly number[])[]): { failingRows: number[]; failingCols: number[] } { const failingRows: number[] = []; const failingCols: number[] = []; for (let row = 0; row < this.height; row++) { if (!this.checkLine("row", row, received[row]!)) failingRows.push(row); } if (this.twoDimensional) { for (let col = 0; col < this.width; col++) { if (!this.checkLine("col", col, received.map((line) => line[col]!))) failingCols.push(col); } } return { failingRows, failingCols }; } /** One line counted again: still even, or not. The same call for a row and a column, so one tag traces both passes. */ private checkLine(axis: "row" | "col", index: number, bits: readonly number[]): boolean { private checkLine(axis: "row" | "col", index: number, lineBits: readonly number[]): boolean { const ones = bits.reduce((sum, bit) => sum + bit, 0); const onesInLine = lineBits.reduce((sum, bit) => sum + bit, 0); const ok = ones % 2 === 0; const ok = onesInLine % 2 === 0; // ▸ count the line again: still even, or not this.tracer?.emit("check", { axis, index, ones, ok }); this.tracer?.emit("check", { axis, index, onesInLine, ok }); return ok; } /** One failing row and one failing column cross at the flipped cell; nothing failing is clean; anything else is noticed but not placed. */ locate(failingRows: readonly number[], failingCols: readonly number[]): { verdict: ParityVerdict; position: GridCell | null } { let verdict: ParityVerdict = "detected"; let position: GridCell | null = null; if (failingRows.length === 0 && failingCols.length === 0) verdict = "clean"; else if (failingRows.length === 1 && failingCols.length === 1) { verdict = "corrected"; position = { row: failingRows[0]!, col: failingCols[0]! }; } // ▸ one failing row and one failing column cross at the flip this.tracer?.emit("locate", { rows: [...failingRows], cols: [...failingCols], verdict, position: position ? { ...position } : null }); return { verdict, position }; } /** Flips the located cell back; with no position the received grid is handed on as it is. */ correct(received: readonly (readonly number[])[], position: GridCell | null): number[][] { const corrected = received.map((line) => [...line]); if (position) corrected[position.row]![position.col] = 1 - corrected[position.row]![position.col]!; // ▸ flip that cell back; nothing to fix, or only noticed this.tracer?.emit("correct", { position: position ? { ...position } : null, corrected: corrected.map((line) => [...line]) }); return corrected; } /** Encode, flip the chosen cells (none for a clean run), check every line, locate, correct. */ run(data: readonly number[], flips: readonly GridCell[] = []): ParityGridResult { const grid = this.encode(data); let received: number[][] = grid.map((line) => [...line]); if (flips.length === 0) received = this.flip(received, null); for (const cell of flips) received = this.flip(received, cell); const { failingRows, failingCols } = this.check(received); const { verdict, position } = this.locate(failingRows, failingCols); const corrected = this.correct(received, position); const intact = data.every((bit, i) => (bit & 1) === corrected[Math.floor(i / this.cols)]![i % this.cols]); return { rows: this.rows, cols: this.cols, data: data.map((bit) => bit & 1), grid, received, flips: flips.map((cell) => ({ ...cell })), failingRows, failingCols, verdict, position, corrected, intact, }; }}