Introduction

Imagine you need to send data reliably over a noisy channel. Shannon's 1948 theorem tells you there is a hard limit — the channel capacity CC — beyond which no code can guarantee reliability. Below that limit, in principle, perfect reliability is achievable.

LDPC codes (Low-Density Parity-Check codes) are among the closest things engineers have to that ideal. Invented by Gallager in 1960 and rediscovered in the 1990s, they are decoded by belief propagation (BP): messages flow back and forth on a sparse factor graph until every bit is resolved. In practice LDPC codes are remarkably close to capacity — but not quite there. Their BP decoder has a threshold εBP<εMAP\varepsilon^{\text{BP}} < \varepsilon^{\text{MAP}}: noise above the BP threshold defeats belief propagation even though MAP decoding could still succeed.

The gap between εBP\varepsilon^{\text{BP}} and εMAP\varepsilon^{\text{MAP}} was a long-standing puzzle. In 2011 Kudekar, Richardson, and Urbanke closed it with a beautiful idea: take a long chain of identical LDPC blocks, couple neighboring blocks so they share a few check nodes, then pin the two ends of the chain with known (error-free) bits. The result is a spatially coupled ensemble whose BP threshold rises all the way to the MAP threshold — and, because the MAP threshold equals Shannon capacity for the right base codes, the chain achieves capacity with belief propagation. This phenomenon is called threshold saturation.

The intuition is geometric: pinning the ends creates a region where decoding succeeds easily. That success propagates inward like a wave, melting the frozen interior one slice at a time — until the entire chain is decoded.

Watch the Decoding Wave

The demo below models a chain of L = 10 coupled blocks. Each block has an erasure probability ε\varepsilon (the noise level). The two boundary blocks (positions 0 and L-1) start fully decoded — they represent the pinned ends.

Set the noise level and click Step to advance the wave one position, or Decode all to watch it sweep the whole chain.

<!-- Chain of L coupled LDPC blocks; boundary blocks are pinned (decoded from the start) -->
<div class="controls">
  <label>
    <span>Noise ε:</span>
    <input type="range" id="noiseSlider" min="0.30" max="0.55" step="0.01" value="0.45">
    <span id="noiseVal">0.45</span>
  </label>
  <div class="btns">
    <button id="btnStep" type="button">Step</button>
    <button id="btnAll" type="button">Decode all</button>
    <button id="btnReset" type="button" class="ghost">Reset</button>
  </div>
</div>
<div class="chain-wrap">
  <div id="chain" class="chain"></div>
</div>
<div id="status" class="status"></div>
<div class="legend">
  <span class="leg-item"><span class="leg-box decoded"></span> Decoded</span>
  <span class="leg-item"><span class="leg-box decoding"></span> Decoding</span>
  <span class="leg-item"><span class="leg-box stuck"></span> Stuck</span>
  <span class="leg-item"><span class="leg-box undecoded"></span> Undecoded</span>
</div>

/* SC-LDPC chain visualization — bar height encodes erasure fraction */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; padding: 10px; }
.controls { display: flex; flex-direction: column; gap: 8px; margin-bottom: 12px; }
.controls label { display: flex; align-items: center; gap: 8px; font-size: .9rem; }
.controls input[type=range] { flex: 1; max-width: 200px; }
.btns { display: flex; gap: 6px; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.chain-wrap { overflow-x: auto; padding-bottom: 4px; }
.chain { display: flex; gap: 4px; align-items: flex-end; min-width: max-content; margin: 0 auto; }
.block { display: flex; flex-direction: column; align-items: center; gap: 3px; width: 50px; }
.block-rect { width: 44px; border-radius: 7px; transition: background .35s, height .35s; }
.block-label { font-size: .7rem; color: #666; }
/* Block state color coding */
.decoded  { background: #2a9d5c; }
.decoding { background: #e9c46a; }
.stuck    { background: #e63946; }
.undecoded{ background: #c9ccd1; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.5em; margin: 8px 0 6px; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info{ color: #1d3557; }
.legend { display: flex; gap: 10px; flex-wrap: wrap; font-size: .78rem; color: #555; margin-top: 4px; }
.leg-item { display: flex; align-items: center; gap: 4px; }
.leg-box { display: inline-block; width: 14px; height: 14px; border-radius: 3px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Spatially-Coupled LDPC demo: a chain of L=10 blocks.
// Boundary blocks (0 and L-1) are pinned (zero erasure).
// Each step propagates decoding inward using effective erasure from neighbors.

const L = 10;              // number of blocks in the chain
const BP_THRESHOLD = 0.48; // BP threshold of the base LDPC ensemble
const MAP_THRESHOLD = 0.50;// MAP threshold = Shannon capacity limit
const BAR_MAX = 80;        // max bar height in pixels (fully decoded)
const BAR_MIN = 16;        // min bar height in pixels (high erasure)

let noise = 0.45;
// each block has a state:
// "undecoded" | "decoding" | "decoded" | "stuck"
let blockState = [];
// effective erasure fraction per block
let erasure = [];
let running = false;

function initChain() {
  // start all interior blocks undecoded with erasure = noise
  blockState = Array(L).fill('undecoded');
  erasure = Array(L).fill(noise);
  // pin the two boundary blocks — they represent the seed of the decoding wave
  blockState[0] = 'decoded';
  blockState[L - 1] = 'decoded';
  erasure[0] = 0;
  erasure[L - 1] = 0;
  running = false;
  renderChain();
  setStatus('', '');
}

function renderChain() {
  const chain = document.getElementById('chain');
  chain.innerHTML = '';
  for (let i = 0; i < L; i++) {
    const wrap = document.createElement('div');
    wrap.className = 'block';
    const rect = document.createElement('div');
    // bar height proportional to decoded fraction (1 - erasure)
    const h = Math.round(BAR_MIN + (1 - erasure[i]) * (BAR_MAX - BAR_MIN));
    rect.className = 'block-rect ' + blockState[i];
    rect.style.height = h + 'px';
    rect.title = fmt('Block %i% | ε=%v% | %v2%', { i: i, v: erasure[i].toFixed(3), v2: blockState[i] });
    const lbl = document.createElement('div');
    lbl.className = 'block-label';
    lbl.textContent = i === 0 || i === L - 1 ? 'pin' : i;
    wrap.appendChild(rect);
    wrap.appendChild(lbl);
    chain.appendChild(wrap);
  }
}

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

// compute the effective erasure of block i under spatial coupling
function coupledErasure(i) {
  if (blockState[i] === 'decoded') return 0;
  // borrow information from left and right neighbors
  const left  = i > 0     ? erasure[i - 1] : 0;
  const right = i < L - 1 ? erasure[i + 1] : 0;
  // weighted average — coupling strength 0.3 per neighbor
  return (erasure[i] + 0.3 * left + 0.3 * right) / 1.6;
}

// advance the wave by one iteration across all interior blocks
function stepWave() {
  let changed = false;
  const newState = [...blockState];
  const newErasure = [...erasure];

  for (let i = 1; i < L - 1; i++) {
    if (blockState[i] === 'decoded') continue;
    const eff = coupledErasure(i);
    if (eff < BP_THRESHOLD) {
      // effective erasure is below BP threshold: block can decode
      newState[i] = 'decoding';
      newErasure[i] = Math.max(0, eff * 0.25);
      changed = true;
    } else if (eff >= MAP_THRESHOLD) {
      newState[i] = 'stuck';
    }
  }
  // promote decoding blocks to decoded once erasure is negligible
  for (let i = 1; i < L - 1; i++) {
    if (newState[i] === 'decoding' && newErasure[i] < 0.05) {
      newState[i] = 'decoded';
    }
  }
  blockState = newState;
  erasure = newErasure;
  renderChain();
  return changed;
}

function allDecoded() {
  return blockState.every(s => s === 'decoded');
}
function anyStuck() {
  return blockState.some(s => s === 'stuck');
}

function decodeAll() {
  let iter = 0;
  const maxIter = 60;
  running = true;
  document.getElementById('btnStep').disabled = true;
  document.getElementById('btnAll').disabled = true;

  function tick() {
    if (!running || iter >= maxIter) {
      running = false;
      document.getElementById('btnStep').disabled = false;
      document.getElementById('btnAll').disabled = false;
      if (allDecoded()) {
        setStatus('Wave decoded all blocks — threshold saturation achieved!', 'ok');
      } else if (anyStuck()) {
        setStatus('Wave stopped: noise above MAP threshold, some blocks stuck.', 'bad');
      } else {
        setStatus('Wave stalled — no further progress.', 'info');
      }
      return;
    }
    const changed = stepWave();
    iter++;
    if (allDecoded()) {
      renderChain();
      running = false;
      document.getElementById('btnStep').disabled = false;
      document.getElementById('btnAll').disabled = false;
      setStatus('Wave decoded all blocks — threshold saturation achieved!', 'ok');
      console.log('Decoded in', iter, 'iterations');
      return;
    }
    if (!changed || anyStuck()) {
      running = false;
      document.getElementById('btnStep').disabled = false;
      document.getElementById('btnAll').disabled = false;
      setStatus(anyStuck() ? 'Wave stopped: noise above MAP threshold, some blocks stuck.' : 'Wave stalled — no further progress.', 'bad');
      console.log('Wave failed after', iter);
      return;
    }
    setTimeout(tick, 120);
  }
  tick();
}

// wire up UI controls
document.getElementById('noiseSlider').addEventListener('input', function () {
  noise = parseFloat(this.value);
  document.getElementById('noiseVal').textContent = noise.toFixed(2);
  initChain();
});

document.getElementById('btnStep').addEventListener('click', function () {
  if (allDecoded()) { setStatus('All blocks already decoded.', 'ok'); return; }
  const changed = stepWave();
  if (allDecoded()) setStatus('Wave decoded all blocks — threshold saturation achieved!', 'ok');
  else if (anyStuck()) setStatus('Wave stopped: noise above MAP threshold, some blocks stuck.', 'bad');
  else if (!changed) setStatus('Wave stalled — no further progress.', 'bad');
  else setStatus('Wave is propagating…', 'info');
});

document.getElementById('btnAll').addEventListener('click', decodeAll);
document.getElementById('btnReset').addEventListener('click', initChain);

initChain();
Result
Console

Notice: when the noise is below the BP threshold (roughly ε<0.48\varepsilon < 0.48 for this ensemble), the wave always finishes. When it is above the BP threshold but below the MAP threshold (0.48<ε<0.50.48 < \varepsilon < 0.5), an uncoupled code would fail — but the wave still propagates from the pinned boundary and decodes every block. That is threshold saturation in action.

Threshold Saturation

Threshold saturation is the central theorem. Informally:

Chain LL identical (dv,dc)(d_v, d_c)-regular LDPC blocks, couple adjacent blocks via shared checks, and pin the boundary. The BP threshold of the coupled ensemble equals the MAP threshold of the base code.

Why does the wave work?

  • Pinned boundary. At the two ends, the fraction of erasures (unknown bits) is zero by definition. The BP decoder resolves those blocks instantly.
  • Propagation. A resolved block reduces the effective erasure rate seen by its neighbor. If that reduced rate is below the BP threshold, the neighbor decodes too — and so on inward.
  • Threshold saturation. For any noise level ε<εMAP\varepsilon < \varepsilon^{\text{MAP}}, there exists a chain length LL large enough that the wave always reaches the center. As L→∞L \to \infty, the rate penalty from pinning →0\to 0, so the rate approaches 1−εMAP=C1 - \varepsilon^{\text{MAP}} = C (Shannon capacity).

The formal proof uses density evolution — a recursion tracking the probability distribution of messages on the factor graph — and shows that the spatial gradient injected by the boundary forces the fixed point of the coupled system to match the optimal (MAP) fixed point of the base code.

Spatially coupled codes thus achieve something remarkable: a linear-time belief-propagation decoder that is provably capacity-achieving — a combination that Shannon's theorem promised was possible but that took sixty years to constructively demonstrate.

Where It Matters

The capacity-achieving property of SC-LDPC codes is not just theoretical:

  • 5G NR (New Radio): the LDPC codes standardized for the 5G data channel are designed with spatial-coupling ideas that push them very close to Shannon capacity at all code rates.
  • Optical fiber: ultra-long-haul links operate within fractions of a dB of capacity using SC-LDPC variants, saving enormous amounts of amplifier power.
  • Satellite communications: low-Earth-orbit constellations (Starlink and competitors) use near-capacity codes where every fraction of a dB translates to coverage area.
  • Compressed sensing: spatially coupled measurement matrices provably achieve the information-theoretic limits of sparse recovery — the same wave intuition applies.
  • DNA storage: high-redundancy storage on synthetic DNA uses SC codes to handle the extreme insertion/deletion noise of nanopore sequencers.

Beyond communications, the spatial-coupling idea has spread to statistical physics (as a rigorous model of the random-field Ising model) and constraint satisfaction (giving the first constructive proof that random SAT can be solved near the satisfiability threshold with a local algorithm).

Conclusion

Spatially-coupled codes resolve one of the most elegant open problems in coding theory. Shannon proved in 1948 that reliable communication below capacity is possible; for six decades the gap between what theory allowed and what belief propagation could actually decode remained stubbornly open.

The fix was disarmingly simple: pin the ends of a chain of ordinary LDPC blocks and let physics do the work. The resulting decoding wave is not just an engineering trick — it is a deep structural result showing that local algorithms can achieve global optima when you engineer the right boundary conditions.

The next time you stream video over 5G or browse via a satellite link, there is a quiet wave sweeping through a coupled code chain, resolving bits one slice at a time and delivering data at rates that would have seemed impossible before 2011.

Share this article

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

Comments

Loading comments...

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