Jump to content

Fountain code

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Mark@digitalfountain.com (talk | contribs) at 21:32, 13 December 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Fountain codes are a class of Erasure code 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.

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.


Examples of fountain codes

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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Fountain_code&oldid=31242323"