FountainCodes

Fountain codes, also known as fountain codes or rateless erasure codes, are a class of forward error-correcting codes designed to recover a data block from any sufficiently large subset of generated symbols. From a block of k source symbols, the encoder can produce an unlimited stream of encoded symbols; the original k symbols can be reconstructed from any set of encoded symbols whose size is only slightly larger than k, with high probability.

Origins and main variants: The concept was introduced by Michael Luby as LT codes in 2002, the first practical fountain codes. A stronger variant, Raptor codes, combines LT coding with a high-rate precode to achieve linear-time encoding and decoding and very low overhead.

Encoding and decoding: Each encoded symbol is formed by selecting a degree d from a specified distribution, choosing d distinct source symbols uniformly at random, and computing their XOR (mod 2). The decoder collects encoded symbols and applies an iterative peeling (belief-propagation) algorithm: whenever an encoded symbol depends on a single unknown source symbol, that symbol is recovered and the encoding symbols are updated. If enough encoded symbols are received, all source symbols are recovered with high probability.

Distributions and performance; Applications and scope: For LT codes the robust Soliton distribution is commonly used to balance early recoveries and completeness. Raptor codes improve overhead and speed by using a precode, often achieving near-linear complexity and small redundancy. Fountain codes are well suited for unreliable or heterogeneous channels, including multicast and broadcast over lossy networks, streaming and video delivery, peer-to-peer file sharing, and distributed storage. They are valued for their adaptability and efficiency when the channel erasure rate is unknown or variable.