Fountain code

In Coding Theory and Communication Theory, fountain codes (also known as rateless erasure 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.

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 $gamma$ defined by

$K\text{'}=(1+gamma)K$

is non trivial. With the short $K\text{'}$, both LT and raptor codes using the sparse bipartite graph (BP) algorithm never achieve an overhead $gamma$ of less than 0.10. The raptor and online codes have an advantage (over what? Most likely: pure LT code) if and only if 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 online code is going to recover most of the input symbols, say more than 95%, then pre-encoding is not necessary, because transmitting a few tens of dense encoding symbols can cover up all the input symbols with an extremely high probability (called the union bound). The dense encoding symbols also contribute to the remaining matrix of $H$ having its full column rank. Thus, the unrecovered symbols can be solved by Gaussian elimination over the remaining graph. The check equations of dense encoding symbols can be communicated to receivers by applying the same random degree generators of the sender.

An accessible exposition of fountain codes can be found in the final chapter of David MacKay's free online textbook, Information Theory, Inference, and Learning Algorithms

See also

• Raptor codes
• LT codes
• Online codes

References

• M. Luby, "LT Codes," In Proc. IEEE Symposium on the Foundations of Computer Science (FOCS), 2002, pp. 271-280.
• A. Shokrollahi, "Raptor Codes", IEEE Transactions on Information Theory, 52(6), pp. 2551-2567, 2006. PDF
• David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1