# Fountain code

### From Wikipedia, the free encyclopedia

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*.

LT codes are the first practical realization of fountain codes. Raptor codes, are the first fountain codes that achieve linear time encoding and decoding. Also, Online codes are an example of fountain codes that were discovered later.

## [edit] Practical considerations

The most famous and practical fountain code at this time is defined in IETF (Internet Engineering Task Force) RFC 5053,
called the Raptor code. This Raptor code has been adopted into multiple
standards beyond the IETF for both file delivery and streaming
applications, including the 3GPP MBMS standards (Third Generation
Partnership Program Multimedia Broadcast/Multicast Services) for
broadcast file delivery and streaming services, the DVB-H IPDC standard
(Digital Video Broadcast Handheld Internet Protocol Datacast), the
DVB-IPI IPTV standard for delivering commercial TV services over an IP
network, and multiple other standards. This Raptor code has very
efficient linear time encoding and decoding algorithms, and uses a
small constant number of symbol XOR operations per generated symbol for
both encoding and decoding. This Raptor code also has very good
recovery properties. For example, the average reception overhead is
around 0.2% for *k* = 1,000 and the reception overhead is less
than 2% with probability 99.9999%. The reception overhead is defined to
be how much extra encoding data beyond the length of the source data is
needed to recover the original source data, measured as a percentage of
the size of the source data. For example, if the reception overhead is
0.2%, then this means that source data of size 1 Megabyte can be
recovered from 1.002 Megabytes of encoding data.

The Raptor code specified in IETF RFC 5053 is a systematic code, meaning that the source data can be part of the encoded data, and thus the encoded data is a combination of source data and repair data. This is an important property for many practical applications, for example, when deploying coding technology into an already deployed application that has legacy receivers that do not have decoders, a viable solution is to continue to send source data to an existing channel received by legacy receiver and send repair data into a new channel that is ignored by legacy receivers but can be received by receivers enhanced with decoders. The Raptor code has been deployed successfully in a number of interesting commercial and defense applications around the world.

The IETF RFC 5053 provides a complete specification of a Raptor code, which has been used as the recipe for producing multiple interoperable implementations.

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*

## [edit] See also

## [edit] 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