Fountain codes are a class of Erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. In general, an erasure code transforms a message of n blocks, into one with > n blocks such that the original message can be recovered from a subset of those blocks. ...

Fountain codes are also known as rateless erasure codes.

A Fountain code is optimal if the original k source symbols can be recovered from any k encoding symbols. Fountain codes are known that have efficient encoding and decoding algorithms and that allow the recovery of the original k source symbols from any k’ of the encoding symbols with high probability, where k’ is just slightly larger than k.

Practical Considerations

In practical simulations, for relatively short K, say less than 3,000, the overhead γ that is K' = (1 + γ)K is non trivial. With the short K', both LT and Raptor codes by BP algorithm never reach the overhead γ < 0.10. It should be emphasized that the advantage of Raptor and Online codes is valid the BP algorithm over a check matrix H (or triangularization of a check matrix H) can recover most of input symbols. This is a critical drawback of fountain codes. If a Raptor or Onlice code is going to recover most of the input symbols, say more than 95%, then pre-encoding is not necessary because, transimitting a couple of tens of dense encoding symbols can cover up all the input symbols with an extremely high probability (called Union Bound). The extra dense encoding symbols also contributes to the remained matrix of H having its full column rank. And thus, the unrecovered symbols can be solved by Gaussian Elimination via Pivotting Strategy over the remain graph. The check equations of dense encoding symbols can be communicated to receivers by applying the same random degree generators of a sender.

Examples of Fountain Codes

• Raptor codes
• LT codes
• Online codes

Raptor codes, introduced by Amin Shokrallahi, are the first known class of fountain codes with linear time encoding and decoding. ... LT-codes are a class of near optimal rateless erasure correcting codes introduced by Michael Luby. ... Online codes are an example of rateless erasure codes. ...

External links

J. Byers, M. Luby, M: Mitzenmacher and A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Proceedings of ACM Sigcomm '98, Vancouver, Canada, September 1998.