Wikipedia Forever Our shared knowledge. Our shared treasure. Help us protect it.
Wikipedia Forever Our shared knowledge. Our shared treasure. Help us protect it.

Fountain code

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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