THE FOUNTAIN CODE catch any drops from an endless spray — enough of them rebuild the file
A fountain code is rateless: from k source symbols it can spray an unlimited stream of encoded droplets, each an XOR of a random subset. A receiver collects droplets from wherever — any lossy channel, any order — and as soon as it has slightly more than k of them, it can reconstruct the whole file by peeling: a droplet that is the XOR of one still-unknown symbol reveals it, which simplifies other droplets, which reveal more. No feedback, no retransmission, no fixed rate. It is how a single broadcast serves millions of receivers with different losses — each drinks from the fountain until full. The recovery rests on the XOR structure being invertible once enough independent droplets arrive.
THE TECHNIQUE droplets = XORs of subsets; peel to reconstruct once k+ arrive
Three source symbols and a droplet that is the XOR of two of them. The demo loses a symbol and peels it back from the droplet: live demo
HISTORY & CREDIT Byers-Luby-Mitzenmacher 1998 · Luby 2002
“To recover a lost symbol you must have received that symbol.” — a fountain droplet is an XOR mixture; once its other ingredients are known, the missing one peels out. You reconstruct from combinations, not copies. cited
1998 · Byers, Luby, Mitzenmacher & Rege — the “digital fountain” ideal. 2002 · Michael Luby — LT codes, the first practical realization; then Raptor codes. now · broadcast/multicast file delivery, RaptorQ (RFC 6330), data-center storage.
Spray XOR droplets endlessly; a receiver peels the ones it can until the file is whole. Reconstruction from combinations — enough independent mixtures invert. Luby 2002
RECOMMEND FOR I-13 lost symbol peeled from a droplet, computed
On the canonical compiler, a droplet s₁⊕s₃ lets the receiver recover a lost s₃ from the known s₁: 5⊕6=3, then 3⊕5=6:
$ i13 run rec_fountain.i13 # peel s3 = droplet XOR s1
droplet = 3 -- s1 XOR s3 = 5 XOR 6
recovered_s3 = 6 -- droplet XOR s1 recovers the lost symbol
Recommend: the fountain code is reconstruction by peeling an XOR structure, and i13 does the XOR natively (^). It recovers the lost symbol 6 from a droplet s₁⊕s₃=3 and the known s₁=5 — because XOR is its own inverse, a mixture with one unknown yields it. The whole-file recovery generalizes: once enough independent droplets arrive, the linear XOR system is invertible (dart 294's determinant, over GF(2)). i13 enacts the peel; the code's structure — sparse random XORs that stay independent — is what makes the missing symbols recomputable from combinations rather than copies.