Fountain Codes and LT Codes: Rateless Erasure Coding

Why rateless coding matters for lossy channels

Classic erasure codes such as Reed-Solomon fix a rate in advance, encoding k source blocks into n total blocks and guaranteeing recovery as long as any k of the n arrive. This works well when the loss rate is known ahead of time, but it becomes wasteful or insufficient when the channel's behavior is unpredictable, as is common in broadcast and multicast settings where different receivers experience wildly different loss rates simultaneously. A satellite broadcasting a file to millions of set-top boxes cannot tailor a fixed-rate code to every viewer's individual reception quality. Fountain codes sidestep the problem entirely by not fixing a rate: the sender just keeps generating and transmitting new droplets indefinitely, and every receiver, independent of how many packets it individually lost, stops listening on its own once it has accumulated enough droplets to decode. This makes fountain codes a natural fit for broadcast and multicast distribution, peer-to-peer file sharing where different peers hold different subsets of encoded data, and deep space communication where retransmission requests are prohibitively slow.

The robust soliton distribution and droplet degree

The heart of an LT code is the probability distribution used to choose how many source blocks, called the degree, each droplet XORs together. A naive approach might always combine a fixed number of blocks, but this fails badly: too few and decoding stalls because nothing overlaps enough to chain-react, too many and every droplet becomes an opaque combination that cannot be solved until nearly everything else is already known. Luby's key insight was the robust soliton distribution, which deliberately produces a controlled mix of degrees: many droplets of degree one, providing immediate solvable blocks to seed the decoding cascade; a spread of small degrees to keep new source blocks getting covered and integrated; and occasionally a droplet touching a large fraction of the file, which helps ensure every source block is covered by at least one droplet with high probability. This carefully tuned mixture is what allows decoding to succeed with a small constant-factor overhead above the theoretical minimum number of droplets needed, rather than requiring dramatically more droplets than source blocks.

Belief propagation decoding: solving the XOR puzzle

Decoding an LT code is essentially propagating certainty through a bipartite graph connecting droplets to the source blocks they combined. The decoder maintains a pool of received droplets and repeatedly looks for any droplet of degree one, meaning it references exactly one source block that has not yet been recovered; since a degree-one droplet is literally an unencoded copy of that block, it can be read off directly. That newly recovered block is then XORed out of every other droplet that referenced it, which can turn some of those droplets into new degree-one droplets, triggering further recoveries in a chain reaction. This process, known as peeling or belief propagation, continues until either the entire source file has been recovered or the decoder stalls because no degree-one droplet remains among the unsolved ones, meaning more droplets are needed from the stream. The elegance of this approach is its speed: each XOR operation is cheap, and the overall decoding complexity scales roughly linearly with the file size for a well-tuned degree distribution, in contrast to the heavier polynomial arithmetic used by algebraic erasure codes like Reed-Solomon.

Overhead, failure probability, and practical tuning

No fountain code decodes with zero overhead in practice; some small number of droplets beyond the exact k source blocks is typically needed to guarantee the peeling process does not stall, and this overhead is a key design tradeoff. For LT codes with the robust soliton distribution, the expected overhead grows like the square root of k times a logarithmic factor, meaning larger files actually become relatively more efficient, needing a smaller percentage of extra droplets than small files do. If the decoder does stall with a handful of source blocks left unrecovered, the remaining small system of XOR equations can often be solved with a bit of Gaussian elimination as a fallback, trading a little extra computation to guarantee completion even when belief propagation alone gets stuck. Engineers tune the degree distribution's parameters to balance decoding speed against overhead for their specific application, since a distribution skewed toward more overhead generally decodes faster and more reliably with pure peeling, while a leaner distribution saves bandwidth but risks needing the fallback solver more often.

From LT codes to Raptor codes and real deployments

LT codes were a breakthrough, but their decoding complexity, while linear on average, still involves enough droplets and enough graph bookkeeping that later designs pushed further. Raptor codes, developed by Amin Shokrollahi, layer a fixed-rate outer code, typically a simple low-density parity-check style code, on top of an inner LT code with a deliberately weakened degree distribution. This combination achieves genuinely linear-time encoding and decoding with constant, very small overhead independent of file size, a property LT codes alone do not quite achieve. Raptor codes and their standardized variant RaptorQ have since been adopted in real-world protocols including 3GPP multimedia broadcast and multicast services, DVB-H mobile television standards, and IETF specifications for reliable file delivery over lossy networks. The lineage from Luby's original fountain code idea through LT codes to Raptor codes illustrates a common pattern in coding theory: an elegant probabilistic construction gets progressively hardened with an algebraic backbone until it becomes efficient enough for mass deployment.

Frequently asked questions

Try it live

Everything above runs in your browser — open Fountain Codes and LT Codes: Rateless Erasure Coding and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.