Introduction

Every time you stream a video, send a message, or store a file, the data crosses a channel that can flip bits at random. Error-correcting codes add carefully chosen redundancy so that the receiver can recover the original message despite the noise. The question is: how fast can you do that recovery?

Classical codes such as Reed-Solomon are excellent but their decoders run in O(nlog⁡n)O(n \log n) or O(n2)O(n^{2}) time. For a long time it was an open problem whether codes with constant rate and constant relative distance — properties needed for them to be practically useful — could also be decoded in linear time O(n)O(n).

In 1996, Michael Sipser and Daniel Spielman answered the question with a surprise: build your code on top of an expander graph — a sparse graph where every small set of vertices has many neighbors outside it — and a simple greedy decoder called bit-flipping runs in O(n)O(n) time and corrects a constant fraction of errors. The key insight is purely graph-theoretic: expansion forces every corrupted bit to be the minority vote in many of its check equations, making it easy to identify and correct it.

Today expander codes are a cornerstone of modern coding theory, with relatives powering every LDPC-based standard from Wi-Fi to 5G.

Flip Bits, Fix Errors

The demo below shows a small expander-code codeword (8 bits). Each bit on the left is connected to two check nodes on the right. A check node is satisfied when the XOR (parity) of its connected bits is zero; otherwise it is unsatisfied (shown in red).

<!-- Expander codes demo HTML layout. -->
<p class="hint">Each circle (bit) connects to 3 square check nodes. A check node shows <b>&#x2713;</b> (green) when the XOR of its bits is 0, or <b>&#x2717;</b> (red) otherwise. Corrupt one bit, then decode using the bit-flipping algorithm.</p>
<div class="layout">
  <div class="col" id="bit-col"><!-- Bit column (left side, circles) --></div>
  <svg id="edges-svg" class="edges-svg" aria-hidden="true"></svg>
  <div class="col" id="check-col"><!-- Check column (right side, squares) --></div>
</div>
<div class="status" id="status">Codeword is valid. Click Corrupt to introduce an error.</div>
<div class="btns">
  <button id="corrupt" type="button">Corrupt (1 bit)</button>
  <button id="decode" type="button">Decode (bit-flip)</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span class="legend-ok">&#x25CF; satisfied check</span>
  <span class="legend-err">&#x25CF; failed check / corrupt bit</span>
  <span class="legend-flip">&#x25CF; bit being flipped</span>
</div>

/* Expander codes demo styles. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.layout { display: flex; align-items: center; gap: 0; min-height: 320px; position: relative; }
.col { display: flex; flex-direction: column; gap: 6px; z-index: 1; }
#bit-col { margin-right: 6px; }
#check-col { margin-left: 6px; }
.edges-svg { flex: 1; height: 320px; overflow: visible; }
.node { width: 40px; height: 40px; display: flex; align-items: center;
        justify-content: center; font: 700 14px ui-monospace, monospace;
        border: 2px solid #adb1b8; background: #e0e4ea;
        transition: background .25s, border-color .25s; user-select: none; }
.bit-node { border-radius: 50%; }
.check-node { border-radius: 6px; }
.corrupted { background: #e63946; border-color: #c92f3c; color: #fff; }
.flipped-now { background: #ff9f1c; border-color: #e0890f; color: #fff; }
.check-ok { background: #d4edda; border-color: #74c489; color: #0a7d33; font-size: 18px; }
.check-fail { background: #f8d7da; border-color: #e63946; color: #c92f3c; font-size: 18px; }
.edge { stroke: #c8cdd6; stroke-width: 1.4; transition: stroke .25s; }
.edge.active { stroke: #e63946; stroke-width: 2.2; }
.edge.flipping { stroke: #ff9f1c; stroke-width: 2.2; }
.status { font-size: .92rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.legend { display: flex; gap: 1rem; font-size: .78rem; color: #555; flex-wrap: wrap; }
.legend-ok { color: #0a7d33; }
.legend-err { color: #c92f3c; }
.legend-flip { color: #e0890f; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Expander codes demo: Sipser-Spielman bit-flipping decoder.
// Codeword: 10 bits, 5 checks, each bit has degree 3 (connects to 3 checks).
// Decoder: each round flip the bit with the most unsatisfied checks (greedy bit-flip).

// Valid codeword (all 5 check parities = 0).
// H is a (5x10) LDPC parity-check matrix with 3 ones per column and 6 ones per row.
const CODEWORD = [1, 0, 1, 1, 0, 1, 0, 0, 0, 0];
const NUM_BITS = 10;
const NUM_CHECKS = 5;

// Bipartite edge list: [bit_index, check_index]. Each bit has degree 3.
// This sparse regular structure is what makes the code an expander code.
const EDGES = [
  [0,0],[0,1],[0,2],
  [1,0],[1,1],[1,3],
  [2,0],[2,2],[2,4],
  [3,1],[3,2],[3,3],
  [4,1],[4,3],[4,4],
  [5,2],[5,3],[5,4],
  [6,0],[6,2],[6,3],
  [7,0],[7,3],[7,4],
  [8,1],[8,2],[8,4],
  [9,0],[9,1],[9,4]
];

let bits = CODEWORD.slice(); // mutable current state of the 10 bits
let animating = false;

// Returns XOR of all bits in check c. 0 means the check is satisfied.
function checkValue(b, c) {
  let xor = 0;
  EDGES.forEach(([bi, ch]) => { if (ch === c) xor ^= b[bi]; });
  return xor;
}

// Count of unsatisfied checks incident to bit i.
function unsatCount(b, i) {
  let unsat = 0;
  EDGES.forEach(([bit, ch]) => { if (bit === i && checkValue(b, ch) !== 0) unsat++; });
  return unsat;
}

// Render the board. highlightFlip = bit index currently being flipped, or null.
function render(highlightFlip) {
  const bitCol = document.getElementById('bit-col');
  const checkCol = document.getElementById('check-col');
  const svg = document.getElementById('edges-svg');
  bitCol.innerHTML = '';
  checkCol.innerHTML = '';
  svg.innerHTML = '';

  // Draw bit circles.
  for (let i = 0; i < NUM_BITS; i++) {
    const d = document.createElement('div');
    d.className = 'node bit-node';
    d.id = 'bit-' + i;
    d.textContent = bits[i];
    if (bits[i] !== CODEWORD[i]) d.classList.add('corrupted');
    if (highlightFlip === i) d.classList.add('flipped-now');
    bitCol.appendChild(d);
  }

  // Draw check squares.
  for (let c = 0; c < NUM_CHECKS; c++) {
    const d = document.createElement('div');
    d.className = 'node check-node';
    d.id = 'check-' + c;
    const sat = checkValue(bits, c) === 0;
    d.classList.add(sat ? 'check-ok' : 'check-fail');
    d.textContent = sat ? '✓' : '✗';
    d.title = 'C' + c + ' ' + (sat ? 'satisfied' : 'unsatisfied');
    checkCol.appendChild(d);
  }

  // Draw edges (red=failing check, orange=bit being flipped).
  requestAnimationFrame(() => {
    const svgRect = svg.getBoundingClientRect();
    EDGES.forEach(([b, c]) => {
      const bEl = document.getElementById('bit-' + b);
      const cEl = document.getElementById('check-' + c);
      if (!bEl || !cEl) return;
      const br = bEl.getBoundingClientRect();
      const cr = cEl.getBoundingClientRect();
      const x1 = br.right - svgRect.left;
      const y1 = br.top + br.height / 2 - svgRect.top;
      const x2 = cr.left - svgRect.left;
      const y2 = cr.top + cr.height / 2 - svgRect.top;
      const line = document.createElementNS('http://www.w3.org/2000/svg', 'line');
      line.setAttribute('x1', x1); line.setAttribute('y1', y1);
      line.setAttribute('x2', x2); line.setAttribute('y2', y2);
      const sat = checkValue(bits, c) === 0;
      const isFlipEdge = (highlightFlip === b);
      line.className.baseVal = 'edge' + (isFlipEdge ? ' flipping' : (sat ? '' : ' active'));
      svg.appendChild(line);
    });
  });
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

// Flip exactly 1 random bit to introduce an error.
function corrupt() {
  if (animating) return;
  bits = CODEWORD.slice();
  // Choose a random bit position and flip it.
  const pos = Math.floor(Math.random() * NUM_BITS);
  bits[pos] ^= 1;
  render(null);
  setStatus(fmt('Bit %pos% corrupted. Click Decode to fix it.', { pos: pos }), 'bad');
}

// Run the greedy bit-flipping decoder step by step with animation.
function decode() {
  if (animating) return;
  const allSatAlready = Array.from({length: NUM_CHECKS}, (_, c) => checkValue(bits, c) === 0).every(Boolean);
  if (allSatAlready) { setStatus('Codeword is already valid — nothing to decode.', 'ok'); return; }

  animating = true;
  document.getElementById('corrupt').disabled = true;
  document.getElementById('decode').disabled = true;

  let round = 0;
  const MAX_ROUNDS = 15;

  function step() {
    const allSat = Array.from({length: NUM_CHECKS}, (_, c) => checkValue(bits, c) === 0).every(Boolean);
    if (allSat) {
      render(null);
      setStatus('✓ All checks satisfied — codeword recovered!', 'ok');
      animating = false;
      document.getElementById('corrupt').disabled = false;
      document.getElementById('decode').disabled = false;
      return;
    }
    if (round >= MAX_ROUNDS) {
      setStatus('Max rounds reached. Could not converge.', 'bad');
      animating = false;
      document.getElementById('corrupt').disabled = false;
      document.getElementById('decode').disabled = false;
      return;
    }

    // Greedy rule: flip the bit with the highest number of unsatisfied checks.
    // For a single error, the corrupt bit has all 3 checks unsatisfied; others have at most 1.
    let maxUnsat = 0, bestBit = -1;
    for (let i = 0; i < NUM_BITS; i++) {
      const u = unsatCount(bits, i);
      if (u > maxUnsat) { maxUnsat = u; bestBit = i; }
    }

    if (bestBit < 0 || maxUnsat === 0) {
      setStatus('No bit to flip — decoder stuck.', 'bad');
      animating = false;
      document.getElementById('corrupt').disabled = false;
      document.getElementById('decode').disabled = false;
      return;
    }

    render(bestBit);
    setStatus(fmt('Round %round%%v%: flipping bit %bestBit% (%maxUnsat% unsatisfied checks).', { round: round, v: 1, bestBit: bestBit, maxUnsat: maxUnsat }), 'info');

    setTimeout(() => {
      bits[bestBit] ^= 1;
      round++;
      step();
    }, 700);
  }
  step();
}

document.getElementById('corrupt').addEventListener('click', corrupt);
document.getElementById('decode').addEventListener('click', decode);
document.getElementById('reset').addEventListener('click', () => {
  if (animating) return;
  bits = CODEWORD.slice();
  render(null);
  setStatus('Codeword is valid. Click Corrupt to introduce an error.', '');
});

render(null);
Result
Console

Click Corrupt to flip a few bits at random, then click Decode (bit-flip) to run the Sipser-Spielman decoder. On each step, any bit that is the minority in more than half its check equations gets flipped. Watch how the decoder homes in on the errors — and notice that it always terminates in a small number of rounds, independent of the codeword length.

The Real Complexity

What makes expander codes remarkable is that they achieve three goals simultaneously that were previously thought to require trade-offs:

  • Constant rate. The ratio of message length to codeword length is bounded away from zero: k/n≥R0>0k/n \geq R_{0} > 0. You never drown the message in redundancy.
  • Constant relative distance. Any two distinct codewords differ in at least a constant fraction δ0⋅n\delta_{0} \cdot n of positions, so the code tolerates a constant fraction of errors.
  • Linear-time decoding. The Sipser-Spielman bit-flipping algorithm runs in O(n)O(n) time. The decoder loops: for each bit, count how many of its check equations are unsatisfied; if more than half are unsatisfied, flip the bit. Repeat until all checks pass.

Why does this work? The expansion property guarantees that the set of corrupted bits has many unsatisfied checks, and that each corrupted bit is incident to more unsatisfied checks than satisfied ones — making it the clear flip candidate. A classical result shows that O(n)O(n) rounds suffice and each round takes O(n)O(n) time.

The construction uses a (n,d,λ)(n, d, \lambda)-expander: a dd-regular bipartite graph on nn left vertices and mm right vertices where the second eigenvalue λ\lambda of the adjacency matrix is much smaller than dd. The spectral gap d−λd - \lambda controls expansion: the larger it is, the more aggressively small sets expand into new neighbors, and the more errors the code can correct.

Sipser and Spielman's proof was a landmark because it separated three concerns that classical algebraic codes bundled together: structure (the graph), redundancy (the rate), and noise tolerance (the distance). Expander codes showed these could all be controlled independently by choosing the right graph — a purely combinatorial insight transplanted into information theory. See also information-theoretic limits of compression for how rate constraints arise more broadly.

Where It Matters

Expander codes are the theoretical foundation for the most widely deployed error-correcting codes in existence:

  • Wi-Fi (802.11n/ac/ax): uses LDPC codes — Low-Density Parity-Check codes — which are the modern cousin of expander codes. The same sparse bipartite graph structure, the same iterative decoder, the same linear-time behavior.
  • 5G NR: the data channel uses LDPC codes for exactly the same reasons. Decoding a 5G frame is an expander-code bit-flip decoder at scale, running in hardware at gigabit speeds.
  • Satellite and deep-space links: NASA's Consultative Committee for Space Data Systems mandates LDPC codes for missions that cannot afford retransmission — the data either arrives corrected or is lost forever.
  • Solid-state drives and NAND flash: as flash cells wear out, the raw error rate grows; LDPC decoders running in O(n)O(n) time on dedicated silicon keep the logical bit-error rate below 10−1510^{-15}.
  • Theoretical computer science: expander graphs — the combinatorial object at the heart of expander codes — appear in derandomization, hardness amplification, and the construction of pseudorandom generators. Understanding expansion means understanding much of modern complexity theory.

The story of expander codes is a textbook case of how a single mathematical idea — the expansion property of graphs — can simultaneously solve an open problem in information theory and provide the engineering blueprint for a generation of communication standards.

Conclusion

Expander codes tell a clean story: pick a graph with the right expansion properties, define your code using its parity checks, and a childishly simple decoder — just flip whichever bit loses the majority vote — will fix all the errors in linear time.

The depth lies in the guarantee. Expansion forces every small set of errors to be a minority in its own neighborhood, making each corrupt bit self-identifying. Sipser and Spielman turned that geometric intuition into a proof, and engineers turned that proof into hardware that ships in every smartphone today.

If you want to go deeper, expander codes are the entry point to the vast world of graph-based codes and to the role expander graphs play across all of theoretical computer science — from derandomization to the P vs NP problem itself.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/expander-codes/Content licensed under CC BY-NC 4.0.