Interleaving: Spreading a Burst

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

Block interleaver

Loading interactive demo…

Two grids of the same SECDED words, one word per row and a verdict cell at the end of each. On the left the words are sent one after another and the burst falls on consecutive bits of one word. On the right the words are written into a block by row and sent by column, so the same burst falls one bit on each row, and the receiver takes the rows back out before decoding. Tap a bit on the left to start the burst there.Take the tour, or press and explore. Legend:

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

Check bits: the Hamming parities at 1, 2, 4 and the whole-word bit at 8.
A bit the burst inverted, and a word the decoder could not save.
A word whose data came through: clean, or one flip put back.
The row being written, judged, or taken back, or the column being sent.
Cells the run has not reached yet, ghosted.

plain and interleaved count the words whose data survived each sending, worst word the most flips any one word took in each, depth the rows of the block, which is the longest burst it spreads into single flips.

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

Two models of noise. The channel of the capacity lesson flips each bit independently with probability $f$ , so the chance of two flips in one eight-bit word is small, about $28 f^2$ , and a code that fixes one flip per word is nearly always enough. A real channel also has bursts: a scratch, a fade, a spark, a dropped packet. A burst of $L$ consecutive bits lands on $\lceil L / n \rceil$ or so of the $n$ -bit words in a row, and gives one of them most of its flips. SECDED reports two and mends three wrong; no code of one flip per word can help.

The transpose. Write $D$ codewords of length $n$ into a block, one per row, and send the block column by column. Stream position $s$ carries the bit at row $s \bmod D$ , column $\lfloor s / D \rfloor$ . Two bits of the same word sit $D$ positions apart in the stream, so any burst of length $L \le D$ touches each word at most once. The receiver writes the stream into its own block by column and reads the rows back out: the transpose undone, and every word carrying at most one flip, which it fixes.

Depth times power. A code that corrects $t$ errors per word, interleaved to depth $D$ , corrects any burst of length $t D$ . The (8, 4) word on the stage has $t = 1$ , so a block of $4$ tames a burst of $4$ and a block of $8$ a burst of $8$ . Push the length one past the depth and the burst wraps round to a row it already hit: two flips, reported, not fixed. Reed-Solomon words with $t = 2$ over symbols of $8$ bits, interleaved $28$ deep as on a CD, cover a burst of $2 \times 28 \times 8 = 448$ bits before the second code and its own interleave take over.

What it costs. Nothing can be decoded until the whole block has arrived, so the latency is $D n$ bits at both ends and the memory is two blocks. The rate does not change: the same codewords are sent, only in a different order. And the shuffle is not free of failure: a burst longer than $t D$ now damages several words a little instead of one word a lot, and whether that is better depends on what each word can still do. The stage's worst word readout is the number to watch.

Beyond the block. A convolutional interleaver delays row $r$ by $r$ stages instead of waiting for a full block, which halves the latency and memory for the same spread. A cross-interleave, as on the CD, puts a second code around the first so the inner decoder's failures become erasures, bad symbols at known positions, which the outer Reed-Solomon code corrects two at a time for the price of one.

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

The corrector is composed, not traced. ExtendedHammingCode is built once without a tracer and only its encode and decode are used, so every event the stage steps through is this file's own: the burst, the block, the columns, the rows back, the verdicts. The SECDED lesson shows the decoder's inside.
One burst and one correct for both sendings. Each takes a phase and is called twice, so the plain run and the interleaved run are the same code on the same burst, which is the comparison the lesson makes; the tag rule of one call site per tag is what forces the shape.
read is the whole interleaver: stream index s takes grid[s mod rows][s div rows], and deinterleave is the same formula read the other way. There is no table and no state; the transpose is arithmetic on the index.
The burst is clamped, never wrapped. A run that starts near the end of the stream inverts what is there and stops; hit reports how many bits it really touched, so the readouts and the narration never claim more flips than happened.
intact means the data, not the verdict. A double that lands on two parity bits leaves the data right, and a single that was really three flips mends the wrong bit; the counts the stage reports are of words whose four data bits came back as sent.

The codes of the 1950s assumed a channel that flipped each bit on its own, but real channels, radio in a storm, a crackling relay, dust on a tape, make their errors in runs, and a burst of twenty bad bits defeats any code built to fix one per word. The fix was not a better code but a shuffle: write the codewords into a block by row, send it by column, and a run of bad bits in the sent order arrives as one bad bit per word. Ramsey and Forney made the shuffle precise around 1970, and the compact disc of 1982 tamed its scratches the same way, with two Reed-Solomon codes cross-interleaved.

1970John Ramsey - Shows how to build an interleaver with the least memory and delay for a given spread, and Forney's 1971 convolutional interleaver halves the block's latency again; both are still the standard designs.source
1982Sony and Philips - The compact disc ships with CIRC, two Reed-Solomon codes with a cross-interleave between them, which corrects about 4000 consecutive bad bits, a scratch 2.5 millimetres long.source
1994Denso Wave - The QR code interleaves its Reed-Solomon blocks across the symbol, so a smudge over one patch costs each block a little instead of one block everything.source
1999IEEE 802.11a - Wi-Fi's OFDM physical layer interleaves coded bits across subcarriers, so a faded frequency band damages scattered bits that the convolutional decoder can absorb.source

Used today

Optical discs - CDs, DVDs, and Blu-ray spread every word across the track so a scratch, which is a burst along the spiral, becomes single symbol errors the Reed-Solomon codes fix.
QR codes and barcodes - The data blocks are interleaved module by module, which is why a QR code still scans with a logo pasted over its middle.
Wireless and broadcast - Fading knocks out a whole stretch of a frame at once; DVB, LTE, and Wi-Fi interleave across time and frequency before the error-correcting decoder sees the bits.
Memory and storage - ECC memory and flash controllers spread one logical word over several chips or planes, so a failed chip or a damaged page is one symbol per word, not one word gone.

depth4 rows

data

burst atbit 10

burst4 bits

plain: 3 of 4
interleaved: 4 of 4
worst word: 4 vs 1 flips
depth: 4 words

block-interleaver.ts

import type { Tracer } from "../trace";import { EXTENDED_LENGTH, ExtendedHammingCode, type SecdedVerdict } from "./extended-hamming-code";/** A block of this many codewords is the most the stage draws legibly. */export const MAX_INTERLEAVE_ROWS = 8;/** Each row of the block is one SECDED word, eight bits wide. */export const INTERLEAVE_COLS = EXTENDED_LENGTH;/** The two sendings compared: the codewords one after another, or the block read out column by column. */export type InterleavePhase = "plain" | "interleaved";export interface CodewordOutcome {  row: number;  /** The eight bits this codeword's decoder was handed. */  received: number[];  verdict: SecdedVerdict;  corrected: number[];  /** The decoded data matches what was sent. */  intact: boolean;  /** How many of the row's bits the burst inverted. */  flips: number;}export interface PhaseReport {  /** The bits in the order they were sent. */  stream: number[];  /** The same bits after the burst. */  received: number[];  outcomes: CodewordOutcome[];  /** Codewords whose data came through intact. */  survived: number;}export interface InterleaverResult {  rows: number;  cols: number;  data: number[][];  codewords: number[][];  burst: { start: number; length: number };  plain: PhaseReport;  interleaved: PhaseReport;  /** Codewords in the block, the denominator of both survived counts. */  total: number;}/** * A block interleaver over SECDED codewords. Noise on a real channel * comes in bursts, a scratch or a fade that wrecks many bits in a row, * and a code built for one flip per word loses every word the burst * lands on. Write the codewords into a block one per row, read the * block out column by column, and the sent order holds one bit of each * row before it returns to the first: a burst of up to `rows` bits now * touches every word once instead of one word `rows` times, and each * word corrects its single flip. The receiver writes the stream back * in by column and reads the rows out, the transpose undone. The cost * is latency, since nothing can be decoded until the whole block has * arrived, and a burst longer than the depth still puts two flips in * some row. The same bits sent plainly, codeword after codeword, are * run first so the two sendings can be compared. * * Time: O(rows * cols) per phase. Space: O(rows * cols). */export class BlockInterleaver {  /** The corrector of every row, run without a tracer: this file emits every event itself. */  private readonly code = new ExtendedHammingCode();  readonly cols = INTERLEAVE_COLS;  constructor(    readonly rows = 4,    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(rows) || rows < 1 || rows > MAX_INTERLEAVE_ROWS) throw new RangeError(`rows must be 1 to ${MAX_INTERLEAVE_ROWS}, got ${rows}`);  }  /** One SECDED codeword per row of data, quietly. */  encode(data: readonly (readonly number[])[]): number[][] {    if (data.length !== this.rows) throw new RangeError(`expected ${this.rows} data rows, got ${data.length}`);    return data.map((nibble) => this.code.encode(nibble));  }  /** The codewords written into the block, one per row. */  write(codewords: readonly (readonly number[])[]): number[][] {    const grid: number[][] = [];    codewords.forEach((codeword, row) => {      grid.push([...codeword]);      // ▸ one codeword into each row of the block      this.tracer?.emit("write", { row, codeword: [...codeword] });    });    return grid;  }  /** The block read out column by column: stream index s holds grid[s mod rows][s div rows]. */  read(grid: readonly (readonly number[])[]): number[] {    const stream: number[] = [];    for (let col = 0; col < this.cols; col++) {      const bits = grid.map((row) => row[col] ?? 0);      stream.push(...bits);      // ▸ send the block a column at a time: one bit from every row      this.tracer?.emit("read", { col, bits, stream: [...stream] });    }    return stream;  }  /** The stream with `length` consecutive bits from `start` inverted, clamped to the stream; 0 bits is no burst. */  burst(stream: readonly number[], start: number, length: number, phase: InterleavePhase): number[] {    const received = [...stream];    const from = Math.max(0, start);    const to = Math.min(stream.length, from + Math.max(0, length));    for (let s = from; s < to; s++) received[s] = 1 - received[s]!;    for (let streamIndex = from; streamIndex < to; streamIndex++) received[streamIndex] = 1 - received[streamIndex]!;    const hit = Math.max(0, to - from);    const bitsHit = Math.max(0, to - from);    // ▸ the noise inverts a run of consecutive bits of whatever was sent    this.tracer?.emit("burst", { phase, start, length, hit, received: [...received] });    this.tracer?.emit("burst", { phase, start, length, bitsHit, received: [...received] });    return received;  }  /** The received stream written back in by column and read out by row: the transpose undone. */  deinterleave(received: readonly number[], codewords: readonly (readonly number[])[]): number[][] {    const rows: number[][] = [];    for (let row = 0; row < this.rows; row++) {      const word = Array.from({ length: this.cols }, (_, col) => received[col * this.rows + row] ?? 0);      const flips = BlockInterleaver.differences(word, codewords[row] ?? []);      rows.push(word);      // ▸ put the stream back into the block by column and take each row out      this.tracer?.emit("deinterleave", { row, received: [...word], flips });    }    return rows;  }  /** Every row through the SECDED decoder; each verdict and whether the data survived. */  correct(words: readonly (readonly number[])[], codewords: readonly (readonly number[])[], data: readonly (readonly number[])[], phase: InterleavePhase): CodewordOutcome[] {    return words.map((word, row) => {      const { verdict, corrected, decoded } = this.code.decode(word);      const flips = BlockInterleaver.differences(word, codewords[row] ?? []);      const intact = decoded.every((bit, i) => bit === ((data[row]?.[i] ?? 0) & 1));      // ▸ every word through the SECDED decoder: one flip fixed, two reported      this.tracer?.emit("correct", { phase, row, verdict, flips, intact });      return { row, received: [...word], verdict, corrected, intact, flips };    });  }  /** How many codewords each sending brought through, side by side. */  compare(plain: PhaseReport, interleaved: PhaseReport, length: number): void {    // ▸ how many words came through plainly, and how many interleaved    this.tracer?.emit("compare", { plain: plain.survived, interleaved: interleaved.survived, total: this.rows, length });  }  /**   * Encode the data, send it plainly under the burst, then send it   * interleaved under the same burst, and compare what survived.   */  run(data: readonly (readonly number[])[], start: number, length: number): InterleaverResult {    const codewords = this.encode(data);    const normalized = data.map((row) => row.map((bit) => bit & 1));    const plainStream = codewords.flat();    const plainReceived = this.burst(plainStream, start, length, "plain");    const plainWords = codewords.map((_, row) => plainReceived.slice(row * this.cols, (row + 1) * this.cols));    const plainOutcomes = this.correct(plainWords, codewords, normalized, "plain");    const plain: PhaseReport = { stream: plainStream, received: plainReceived, outcomes: plainOutcomes, survived: plainOutcomes.filter((o) => o.intact).length };    const grid = this.write(codewords);    const stream = this.read(grid);    const received = this.burst(stream, start, length, "interleaved");    const words = this.deinterleave(received, codewords);    const outcomes = this.correct(words, codewords, normalized, "interleaved");    const interleaved: PhaseReport = { stream, received, outcomes, survived: outcomes.filter((o) => o.intact).length };    this.compare(plain, interleaved, length);    return { rows: this.rows, cols: this.cols, data: normalized, codewords, burst: { start, length }, plain, interleaved, total: this.rows };  }  /** Positions where two words differ. */  private static differences(a: readonly number[], b: readonly number[]): number {    let count = 0;    for (let i = 0; i < Math.max(a.length, b.length); i++) if ((a[i] ?? 0) !== (b[i] ?? 0)) count += 1;    return count;  }}

plain =: 3 of 4
interleaved =: 4 of 4
length =: 4

Done: 3 of 4 words survived plainly and 4 of 4 interleaved. A block 4 deep turns any burst of up to 4 bits into one flip per word; a longer burst lands two on some row.

import type { Tracer } from "../trace";import { EXTENDED_LENGTH, ExtendedHammingCode, type SecdedVerdict } from "./extended-hamming-code";/** A block of this many codewords is the most the stage draws legibly. */export const MAX_INTERLEAVE_ROWS = 8;/** Each row of the block is one SECDED word, eight bits wide. */export const INTERLEAVE_COLS = EXTENDED_LENGTH;/** The two sendings compared: the codewords one after another, or the block read out column by column. */export type InterleavePhase = "plain" | "interleaved";export interface CodewordOutcome { row: number; /** The eight bits this codeword's decoder was handed. */ received: number[]; verdict: SecdedVerdict; corrected: number[]; /** The decoded data matches what was sent. */ intact: boolean; /** How many of the row's bits the burst inverted. */ flips: number;}export interface PhaseReport { /** The bits in the order they were sent. */ stream: number[]; /** The same bits after the burst. */ received: number[]; outcomes: CodewordOutcome[]; /** Codewords whose data came through intact. */ survived: number;}export interface InterleaverResult { rows: number; cols: number; data: number[][]; codewords: number[][]; burst: { start: number; length: number }; plain: PhaseReport; interleaved: PhaseReport; /** Codewords in the block, the denominator of both survived counts. */ total: number;}/** * A block interleaver over SECDED codewords. Noise on a real channel * comes in bursts, a scratch or a fade that wrecks many bits in a row, * and a code built for one flip per word loses every word the burst * lands on. Write the codewords into a block one per row, read the * block out column by column, and the sent order holds one bit of each * row before it returns to the first: a burst of up to `rows` bits now * touches every word once instead of one word `rows` times, and each * word corrects its single flip. The receiver writes the stream back * in by column and reads the rows out, the transpose undone. The cost * is latency, since nothing can be decoded until the whole block has * arrived, and a burst longer than the depth still puts two flips in * some row. The same bits sent plainly, codeword after codeword, are * run first so the two sendings can be compared. * * Time: O(rows * cols) per phase. Space: O(rows * cols). */export class BlockInterleaver { /** The corrector of every row, run without a tracer: this file emits every event itself. */ private readonly code = new ExtendedHammingCode(); readonly cols = INTERLEAVE_COLS; constructor( readonly rows = 4, private readonly tracer?: Tracer, ) { if (!Number.isInteger(rows) || rows < 1 || rows > MAX_INTERLEAVE_ROWS) throw new RangeError(`rows must be 1 to ${MAX_INTERLEAVE_ROWS}, got ${rows}`); } /** One SECDED codeword per row of data, quietly. */ encode(data: readonly (readonly number[])[]): number[][] { if (data.length !== this.rows) throw new RangeError(`expected ${this.rows} data rows, got ${data.length}`); return data.map((nibble) => this.code.encode(nibble)); } /** The codewords written into the block, one per row. */ write(codewords: readonly (readonly number[])[]): number[][] { const grid: number[][] = []; codewords.forEach((codeword, row) => { grid.push([...codeword]); // ▸ one codeword into each row of the block this.tracer?.emit("write", { row, codeword: [...codeword] }); }); return grid; } /** The block read out column by column: stream index s holds grid[s mod rows][s div rows]. */ read(grid: readonly (readonly number[])[]): number[] { const stream: number[] = []; for (let col = 0; col < this.cols; col++) { const bits = grid.map((row) => row[col] ?? 0); stream.push(...bits); // ▸ send the block a column at a time: one bit from every row this.tracer?.emit("read", { col, bits, stream: [...stream] }); } return stream; } /** The stream with `length` consecutive bits from `start` inverted, clamped to the stream; 0 bits is no burst. */ burst(stream: readonly number[], start: number, length: number, phase: InterleavePhase): number[] { const received = [...stream]; const from = Math.max(0, start); const to = Math.min(stream.length, from + Math.max(0, length)); for (let s = from; s < to; s++) received[s] = 1 - received[s]!; for (let streamIndex = from; streamIndex < to; streamIndex++) received[streamIndex] = 1 - received[streamIndex]!; const hit = Math.max(0, to - from); const bitsHit = Math.max(0, to - from); // ▸ the noise inverts a run of consecutive bits of whatever was sent this.tracer?.emit("burst", { phase, start, length, hit, received: [...received] }); this.tracer?.emit("burst", { phase, start, length, bitsHit, received: [...received] }); return received; } /** The received stream written back in by column and read out by row: the transpose undone. */ deinterleave(received: readonly number[], codewords: readonly (readonly number[])[]): number[][] { const rows: number[][] = []; for (let row = 0; row < this.rows; row++) { const word = Array.from({ length: this.cols }, (_, col) => received[col * this.rows + row] ?? 0); const flips = BlockInterleaver.differences(word, codewords[row] ?? []); rows.push(word); // ▸ put the stream back into the block by column and take each row out this.tracer?.emit("deinterleave", { row, received: [...word], flips }); } return rows; } /** Every row through the SECDED decoder; each verdict and whether the data survived. */ correct(words: readonly (readonly number[])[], codewords: readonly (readonly number[])[], data: readonly (readonly number[])[], phase: InterleavePhase): CodewordOutcome[] { return words.map((word, row) => { const { verdict, corrected, decoded } = this.code.decode(word); const flips = BlockInterleaver.differences(word, codewords[row] ?? []); const intact = decoded.every((bit, i) => bit === ((data[row]?.[i] ?? 0) & 1)); // ▸ every word through the SECDED decoder: one flip fixed, two reported this.tracer?.emit("correct", { phase, row, verdict, flips, intact }); return { row, received: [...word], verdict, corrected, intact, flips }; }); } /** How many codewords each sending brought through, side by side. */ compare(plain: PhaseReport, interleaved: PhaseReport, length: number): void { // ▸ how many words came through plainly, and how many interleaved this.tracer?.emit("compare", { plain: plain.survived, interleaved: interleaved.survived, total: this.rows, length }); } /** * Encode the data, send it plainly under the burst, then send it * interleaved under the same burst, and compare what survived. */ run(data: readonly (readonly number[])[], start: number, length: number): InterleaverResult { const codewords = this.encode(data); const normalized = data.map((row) => row.map((bit) => bit & 1)); const plainStream = codewords.flat(); const plainReceived = this.burst(plainStream, start, length, "plain"); const plainWords = codewords.map((_, row) => plainReceived.slice(row * this.cols, (row + 1) * this.cols)); const plainOutcomes = this.correct(plainWords, codewords, normalized, "plain"); const plain: PhaseReport = { stream: plainStream, received: plainReceived, outcomes: plainOutcomes, survived: plainOutcomes.filter((o) => o.intact).length }; const grid = this.write(codewords); const stream = this.read(grid); const received = this.burst(stream, start, length, "interleaved"); const words = this.deinterleave(received, codewords); const outcomes = this.correct(words, codewords, normalized, "interleaved"); const interleaved: PhaseReport = { stream, received, outcomes, survived: outcomes.filter((o) => o.intact).length }; this.compare(plain, interleaved, length); return { rows: this.rows, cols: this.cols, data: normalized, codewords, burst: { start, length }, plain, interleaved, total: this.rows }; } /** Positions where two words differ. */ private static differences(a: readonly number[], b: readonly number[]): number { let count = 0; for (let i = 0; i < Math.max(a.length, b.length); i++) if ((a[i] ?? 0) !== (b[i] ?? 0)) count += 1; return count; }}