Fountain code

A code for erasure channels — where a packet either arrives intact or does not arrive at all — that has no rate. The encoder is a fountain producing an endless stream of drops; a receiver holds a bucket under it and can reconstruct a K-packet file from any K′ drops, with K′ about 5% larger than K. Which drops they are does not matter.

Sourced from information-theory-inference-learning-algorithms, held in ../machine-learning-wiki (see the provenance note on information-theory).

The problem it replaces

Internet transfer is a q-ary erasure channel: files are chopped into packets and each is received correctly or lost. The standard answer is retransmission driven by a feedback channel — acknowledgements, or requests to resend. Shannon's objection, as MacKay puts it, is that the capacity of the forward channel is (1−f)l bits whether or not there is feedback, so the feedback is pure overhead.

It gets worse on broadcast. One sender, many receivers, each losing a different random fraction: any packet missed by any receiver must be resent, and nearly every receiver already had it. The retransmissions are almost entirely redundant.

The classical erasure code, Reed–Solomon, has the ideal property — any K of N symbols recover the file — and two disqualifying limits: cost of order K(N−K)log₂N packet operations confines it to small parameters, and the rate K/N must be chosen before transmission. Guess the erasure rate too low and there is no way to extend the code afterwards.

LT codes

Invented by Michael Luby in 1998 at Digital Fountain — MacKay notes it as "the first company whose business is based on sparse-graph codes." Each encoded packet is built in two steps:

1. Draw a degree d from a degree distribution ρ(d).
2. Pick d source packets uniformly at random and XOR them together.

That is the whole encoder. The receiver needs to know each packet's degree and neighbours, which travels as a 32-bit key in the header or comes from a shared pseudo-random seed. The construction is an irregular low-density generator-matrix code, and decoding is message passing on the erasure channel — the same sum–product structure as low-density-parity-check-code with every message either fully known or fully unknown, which reduces to repeatedly solving degree-one equations and substituting back.

Costs: with probability 1−δ, encoding and decoding are both about K ln(K/δ) packet operations, with overhead K′ − K of order √K (ln(K/δ))².

Why "rateless" is the point

The number of encoded packets is potentially unlimited and is decided during transmission rather than in advance. Whatever the channel's erasure statistics turn out to be, the sender keeps producing drops until receivers have enough. Luby calls the codes universal because they are near-optimal for every erasure channel simultaneously, which is a different kind of universality from Lempel–Ziv's in source-coding-theorem: there the algorithm adapts to any source, here the code adapts to any erasure rate.

The degree distribution is where the design work sits — too many low-degree packets and the decoder stalls with nothing to substitute; too few and it never gets started.

Where this is used across the hub

• ../platform-ops-wiki and ../embedded-iot-wiki — packet-level erasure coding is a production technique in both domains (multicast distribution, lossy radio links) and neither spoke holds a page on it.
• ../cryptography-wiki — Reed–Solomon appears there as construction material inside proof systems; here it is the baseline that fountain codes were built to escape. Same code, opposite use.

Related

coding-theory · low-density-parity-check-code · error-correcting-code · noisy-channel-coding-theorem · information-theory · information-theory-inference-learning-algorithms · mathematics · synthesis