Fountain Codes

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.

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_label}}: <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">{{panel_source}}</div>
      <div id="source" class="blocks"></div>
    </div>
    <div class="panel">
      <div class="panel-title">{{panel_received}}</div>
      <div id="received" class="packets"></div>
    </div>
    <div class="panel">
      <div class="panel-title">{{panel_decoded}}</div>
      <div id="decoded" class="blocks"></div>
    </div>
  </div>
  <div id="status" class="status">{{status_initial}}</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; } }

// Code not found

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 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(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(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)$ 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).

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.

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.