Jump to content

Fountain code

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 218.248.42.146 (talk) at 09:55, 14 September 2012 (→Applications). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In coding 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 ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term fountain or rateless refers to the fact that these codes do not exhibit a fixed code rate.

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 were the first practical realization of fountain codes. Raptor codes and Online codes were subsequently introduced, and achieve linear time encoding and decoding complexity through a pre-coding stage of the input symbols.

Fountain codes in standards

Raptor codes are the most efficient fountain codes at this time,[1] having very efficient linear time encoding and decoding algorithms, and requiring only a small constant number of XOR operations per generated symbol for both encoding and decoding.[2] IETF RFC 5053 specifies in detail a systematic Raptor code, which has been adopted into multiple standards beyond the IETF, such as within the 3GPP MBMS standard for broadcast file delivery and streaming services, the DVB-H IPDC standard for delivering IP services over DVB networks, and DVB-IPTV for delivering commercial TV services over an IP network. This code can be used with up to 8,192 source symbols in a source block, and a total of up to 65,536 encoded symbols generated for a source block. This code has an average relative reception overhead of 0.2% when applied to source blocks with 1,000 source symbols, and has a relative reception overhead of less than 2% with probability 99.9999%.[3] The relative reception overhead is defined as the extra encoding data required beyond the length of the source data to recover the original source data, measured as a percentage of the size of the source data. For example, if the relative 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.

A more advanced Raptor code with greater flexibility and improved reception overhead, called RaptorQ, has been introduced into the IETF.[4] This code can be used with up to 56,403 source symbols in a source block, and a total of up to 16,777,216 encoded symbols generated for a source block. This code is able to recover a source block from any set of encoded symbols equal to the number of source symbols in the source block with high probability, and in rare cases from slightly more than the number of source symbols in the source block.

See also

Notes

  1. ^ "Qualcomm Raptor Technology - Forward Error Correction".
  2. ^ (Shokrollahi 2006)
  3. ^ T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba (March 2008). Furht, B.; Ahson, S. (eds.). "Application Layer Forward Error Correction for Mobile Multimedia Broadcasting". Handbook of Mobile Broadcasting: DVB-H, DMB, ISDB-T and Media FLO. CRC Press.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  4. ^ (Luby et al. 2010)

References

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