Introduction

Imagine downloading a large file over a lossy network. Traditional error correction asks the sender to retransmit exactly the missing pieces — but what if the network drops packets at random and the sender doesn't know which ones arrived?

Fountain codes take a completely different approach. Starting from k source blocks, the encoder generates a potentially unlimited stream of encoded packets, each formed by XORing a random subset of the source blocks. The receiver doesn't care which packets arrive — it just needs any set of roughly k + ε of them, and it can solve a system of XOR equations to recover all k original blocks exactly.

The name says it all: the encoder is a fountain that never stops pouring. Tune in for a second, a minute, or an hour — as long as you collect enough drops, you reconstruct the entire original. No retransmissions, no coordination about what was lost.

This idea, developed rigorously by Michael Luby with LT codes (2002) and later refined into Raptor codes (Shokrollahi, 2006), is now inside every modern video-streaming and satellite-broadcast standard you use.

Try It: Drop Packets, Recover the File

Below is a simplified fountain code over 8 source blocks (labeled A–H). The encoder produces a stream of encoded packets, each the XOR of 2–4 randomly chosen source blocks. Drag the loss rate slider to simulate a noisy channel, then press Start stream to watch packets arrive and the decoder attempt recovery.

<div class="fc-wrap">
  <div class="controls">
    <label>Loss rate: <span id="lossVal">30%</span>
      <input type="range" id="lossSlider" min="0" max="80" value="30" step="5">
    </label>
    <button id="startBtn" type="button">Start stream</button>
    <button id="resetBtn" type="button" class="ghost">Reset</button>
  </div>
  <div class="panels">
    <div class="panel">
      <div class="panel-title">Source blocks</div>
      <div id="source" class="blocks"></div>
    </div>
    <div class="panel">
      <div class="panel-title">Encoded packets received</div>
      <div id="received" class="packets"></div>
    </div>
    <div class="panel">
      <div class="panel-title">Decoded blocks</div>
      <div id="decoded" class="blocks"></div>
    </div>
  </div>
  <div id="status" class="status">Set a loss rate and press Start stream.</div>
  <div id="log" class="log"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.fc-wrap { padding: .2rem; }
.controls { display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; margin-bottom: .7rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 100px; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.panels { display: grid; grid-template-columns: 1fr 1.4fr 1fr; gap: .6rem; }
.panel { background: #f4f7fa; border-radius: 8px; padding: .5rem; min-height: 140px; }
.panel-title { font-size: .75rem; font-weight: 700; color: #5a7088; text-transform: uppercase;
               letter-spacing: .04em; margin-bottom: .4rem; }
.blocks { display: flex; flex-wrap: wrap; gap: 4px; }
.block { width: 36px; height: 36px; border-radius: 6px; display: flex; align-items: center;
         justify-content: center; font: 700 13px ui-monospace, monospace;
         background: #c9d8e8; color: #1d3557; border: 1px solid #adc0d4;
         transition: background .3s, color .3s; }
.block.decoded { background: #1d3557; color: #fff; border-color: #1d3557; }
.packets { display: flex; flex-direction: column; gap: 3px; max-height: 200px; overflow-y: auto; }
.pkt { font: 12px ui-monospace, monospace; padding: 2px 5px; border-radius: 4px;
       background: #dde8f4; color: #1d3557; white-space: nowrap; overflow: hidden;
       text-overflow: ellipsis; animation: fadein .25s; }
.pkt.dropped { background: #f5d0d0; color: #922; text-decoration: line-through; }
@keyframes fadein { from { opacity: 0; transform: translateY(4px); } to { opacity: 1; } }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0 .2rem; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.partial { color: #b06000; }
.status.bad { color: #c92f3c; }
.log { font-size: .8rem; color: #555; min-height: 1.2em; }
@media (max-width: 420px) { .panels { grid-template-columns: 1fr; } }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fountain code demo over GF(2) (XOR arithmetic).
// Source: k=8 blocks, each a single "symbol" A..H.
// Encoder: each packet XORs a random subset of 2-4 source blocks.
// Decoder: Gaussian elimination over GF(2) once enough packets arrive.

const K = 8;
const LABELS = 'ABCDEFGH'.split('');
// Each source block has a numeric value (index+1) used for display only;
// algebra is over GF(2) so XOR of values is just bitwise XOR of index bits.
// We track which source blocks each packet covers as a bitmask.

let lossRate = 0.30;
let streamTimer = null;
let packets = []; // { mask, dropped }
let decodedMask = 0;
let running = false;
let totalSent = 0, totalReceived = 0;

// --- UI refs ---
const lossSlider = document.getElementById('lossSlider');
const lossVal = document.getElementById('lossVal');
const startBtn = document.getElementById('startBtn');
const resetBtn = document.getElementById('resetBtn');
const statusEl = document.getElementById('status');
const logEl = document.getElementById('log');

// --- Render source blocks ---
function renderSource() {
  const el = document.getElementById('source');
  el.innerHTML = '';
  LABELS.forEach(l => {
    const d = document.createElement('div');
    d.className = 'block';
    d.textContent = l;
    el.appendChild(d);
  });
}

// --- Render decoded blocks ---
function renderDecoded(mask) {
  const el = document.getElementById('decoded');
  el.innerHTML = '';
  LABELS.forEach((l, i) => {
    const d = document.createElement('div');
    d.className = 'block' + ((mask >> i) & 1 ? ' decoded' : '');
    d.textContent = l;
    el.appendChild(d);
  });
}

// --- Generate a random encoded packet mask (2-4 source blocks) ---
function randomMask() {
  const degree = 2 + Math.floor(Math.random() * 3); // 2, 3, or 4
  const indices = [];
  while (indices.length < degree) {
    const r = Math.floor(Math.random() * K);
    if (!indices.includes(r)) indices.push(r);
  }
  let mask = 0;
  indices.forEach(i => mask |= (1 << i));
  return { mask, indices };
}

// --- Label for a packet given its mask ---
function maskLabel(mask) {
  return LABELS.filter((_, i) => (mask >> i) & 1).join(' ⊕ ');
}

// --- Gaussian elimination over GF(2) to recover source blocks ---
// Returns bitmask of recovered source blocks, or 0 if underdetermined.
function gaussianElim(receivedPackets) {
  // Build augmented matrix: each row = [equation bitmask | rhs bit per source block]
  // We model: for source block vector s (K bits), each packet is a dot product over GF(2).
  // For simplicity, each source block i has "value" i (just its index identity).
  // We want to find which source blocks are individually recoverable.

  // Represent each received packet as a row in GF(2) matrix (K columns).
  const rows = receivedPackets.map(p => p.mask); // K-bit row
  // The "value" of a packet (XOR of the source labels it covers) is just the mask itself
  // conceptually. We do Gaussian elimination to find the row echelon form and count how many source variables are determined.

  let pivots = []; // pivot column for each row
  let matrix = rows.map(r => r); // copy
  let rhs = rows.map(r => r);    // we track which source block each row resolves to

  let row = 0;
  for (let col = 0; col < K && row < matrix.length; col++) {
    // Find pivot
    let pivotRow = -1;
    for (let r = row; r < matrix.length; r++) {
      if ((matrix[r] >> col) & 1) { pivotRow = r; break; }
    }
    if (pivotRow === -1) continue;
    // Swap
    [matrix[row], matrix[pivotRow]] = [matrix[pivotRow], matrix[row]];
    [rhs[row], rhs[pivotRow]] = [rhs[pivotRow], rhs[row]];
    pivots.push(col);
    // Eliminate
    for (let r = 0; r < matrix.length; r++) {
      if (r !== row && ((matrix[r] >> col) & 1)) {
        matrix[r] ^= matrix[row];
        rhs[r] ^= rhs[row];
      }
    }
    row++;
  }

  // Pivot columns = decoded source block indices
  let decoded = 0;
  pivots.forEach(col => decoded |= (1 << col));
  return decoded;
}

// --- Stream step: emit one packet ---
function emitPacket() {
  const { mask, indices } = randomMask();
  const dropped = Math.random() < lossRate;
  totalSent++;
  const pkt = { mask, dropped };

  // Add to received display
  const recvEl = document.getElementById('received');
  const d = document.createElement('div');
  d.className = 'pkt' + (dropped ? ' dropped' : '');
  d.textContent = (dropped ? '✗ ' : '✓ ') + maskLabel(mask);
  recvEl.appendChild(d);
  recvEl.scrollTop = recvEl.scrollHeight;

  if (!dropped) {
    totalReceived++;
    packets.push(pkt);
    // Try to decode
    decodedMask = gaussianElim(packets.filter(p => !p.dropped));
    renderDecoded(decodedMask);
    const numDecoded = Integer.bitCount(decodedMask);
    if (decodedMask === (1 << K) - 1) {
      // All K blocks recovered
      clearInterval(streamTimer);
      running = false;
      startBtn.textContent = 'Start stream';
      setStatus(fmt('All %K% blocks recovered! (%totalReceived% packets received, %v% dropped)', { K: K, totalReceived: totalReceived, v: totalSent - totalReceived }), 'ok');
      logEl.textContent = fmt('Decoded using %length% packets after %totalSent% sent.', { length: packets.filter(p=>!p.dropped).length, totalSent: totalSent });
    } else {
      setStatus(fmt('Decoded %countBits% / %K% blocks so far...', { countBits: countBits(decodedMask), K: K }), 'partial');
    }
  } else {
    setStatus(fmt('Decoded %countBits% / %K% blocks so far...', { countBits: countBits(decodedMask), K: K }), countBits(decodedMask) === K ? 'ok' : 'partial');
  }

  // Safety: stop after 80 packets
  if (totalSent >= 80 && running) {
    clearInterval(streamTimer);
    running = false;
    startBtn.textContent = 'Start stream';
    if (decodedMask !== (1 << K) - 1) {
      setStatus(fmt('Stopped. Recovered %countBits% / %K% blocks. Try a lower loss rate.', { countBits: countBits(decodedMask), K: K }), 'bad');
    }
  }
}

function countBits(n) {
  let c = 0; while (n) { c += n & 1; n >>>= 1; } return c;
}

// Polyfill Integer.bitCount as countBits
const Integer = { bitCount: countBits };

function setStatus(t, cls) {
  statusEl.textContent = t;
  statusEl.className = 'status ' + (cls || '');
}

function resetAll() {
  if (streamTimer) { clearInterval(streamTimer); streamTimer = null; }
  running = false;
  packets = [];
  decodedMask = 0;
  totalSent = 0;
  totalReceived = 0;
  startBtn.textContent = 'Start stream';
  document.getElementById('received').innerHTML = '';
  renderSource();
  renderDecoded(0);
  setStatus('Set a loss rate and press Start stream.', '');
  logEl.textContent = '';
}

lossSlider.addEventListener('input', () => {
  lossRate = lossSlider.value / 100;
  lossVal.textContent = lossSlider.value + '%';
});

startBtn.addEventListener('click', () => {
  if (running) {
    clearInterval(streamTimer);
    running = false;
    startBtn.textContent = 'Start stream';
    setStatus('Paused.', '');
    return;
  }
  if (decodedMask === (1 << K) - 1) resetAll();
  running = true;
  startBtn.textContent = 'Pause';
  setStatus('Streaming...', '');
  streamTimer = setInterval(emitPacket, 220);
});

resetBtn.addEventListener('click', resetAll);

// Init
renderSource();
renderDecoded(0);
Result
Console

Notice the threshold: below about 8–10 received packets, recovery is impossible. Once you cross it, Gaussian elimination over GF(2) solves the XOR system instantly. The decoder never asks "which packet did I miss?" — any sufficient subset does the job. Compare this to a traditional scheme that would need to retransmit exactly the lost packets.

The Real Complexity

The central question is: how many extra packets beyond k does the receiver actually need?

  • Reed–Solomon codes (the classical alternative) require knowing which symbols are erased. They recover from exactly k received symbols, but the decoder must know the positions of losses — impractical for broadcast.
  • Naive random linear codes over GF(2) work without knowing loss positions, but encoding and decoding cost O(k2)O(k^{2}) operations — prohibitive for large files.
  • LT codes (Luby, 2002) introduced the soliton degree distribution — a carefully chosen probability over how many source blocks each encoded packet XORs together. With this distribution, a receiver needs only k(1 + ε) packets to decode with high probability, and decoding runs in O(klog⁡k)O(k \log k) expected time via a peeling process (repeatedly finding packets that cover exactly one unknown block).
  • Raptor codes (Shokrollahi, 2006) add a pre-coding step that reduces the required overhead further and achieve O(k)O(k) encoding and decoding time — the theoretically optimal order.
  • The information-theoretic limit is exactly k received packets. Raptor codes come within a tiny constant factor of this limit.

Unlike compression, fountain codes do not reduce the data size — they distribute redundancy across an unlimited stream so that any sufficient window decodes perfectly. The problem is not NP-hard or undecidable; it is solved, with practical codes that nearly match the theoretical bound. The cleverness is entirely in the degree distribution design and the linear-algebra structure of GF(2).

Where It Matters

Any time the channel drops packets unpredictably and retransmission is impossible or expensive, fountain codes shine:

  • Broadcast and multicast: a satellite broadcasting a film to millions of receivers cannot retransmit individually to each one that missed a packet. Raptor codes (standardized in DVB-H and DVB-IPTV) let every receiver independently decode once it has collected enough of the stream.
  • Mobile streaming (5G eMBMS): 5G multicast uses Raptor codes so that a tower can broadcast video to thousands of devices simultaneously, regardless of individual signal quality.
  • File distribution (IPTV, DASH): content delivery networks use fountain-like codes so that any CDN mirror can serve any part of the stream without the client needing to coordinate which segments it got from which server.
  • Deep-space communication: NASA's CCSDS erasure-coding standard uses fountain-code ideas because round-trip light delays make retransmission impractical — the probe must keep transmitting and whatever Earth receives must suffice.
  • Disaster-relief networks: when infrastructure is down and only one-way broadcast is available (radio, satellite), fountain codes let first responders broadcast maps, firmware updates, or instructions and have each receiver reconstruct from whatever it catches.

The same XOR-over-GF(2) algebra also underlies LDPC codes and appears in the analysis of random graph structures used throughout networking.

Conclusion

Fountain codes embody a beautiful shift in perspective: instead of asking "what was lost and how do we get it back?", they ask "what if we just never stop sending, and let the receiver take whatever it can catch?"

That shift — from targeted retransmission to universal recovery — turned out to be theoretically near-optimal and practically fast. LT codes showed the soliton distribution makes it work; Raptor codes made it linear-time. Today every DVB-H broadcast and 5G multicast session quietly relies on this idea.

The next time a satellite video call stays crystal-clear through a rainstorm, there's a good chance that a fountain of XOR packets — and a little elegant algebra — is keeping it flowing.

Share this article

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

Comments

Loading comments...

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