Fountain code

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'=(1+gamma)K

is non trivial. With the short K', 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, " [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html 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. [http://ieeexplore.ieee.org/iel5/18/34354/01638543.pdf?isnumber=34354&prod=JNL&arnumber=1638543&arSt=2551&ared=2567&arAuthor=Shokrollahi%2C+A. PDF]
* David J. C. MacKay. " [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms] " Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • fountain code — noun A rateless erasure code …   Wiktionary

  • Fountain — Fountain, CO U.S. city in Colorado Population (2000): 15197 Housing Units (2000): 5219 Land area (2000): 13.997070 sq. miles (36.252243 sq. km) Water area (2000): 0.014924 sq. miles (0.038652 sq. km) Total area (2000): 14.011994 sq. miles… …   StarDict's U.S. Gazetteer Places

  • Fountain City — Fountain City, IN U.S. town in Indiana Population (2000): 735 Housing Units (2000): 309 Land area (2000): 0.262926 sq. miles (0.680974 sq. km) Water area (2000): 0.000000 sq. miles (0.000000 sq. km) Total area (2000): 0.262926 sq. miles (0.680974 …   StarDict's U.S. Gazetteer Places

  • Fountain Hill — Fountain Hill, AR U.S. town in Arkansas Population (2000): 159 Housing Units (2000): 77 Land area (2000): 0.586615 sq. miles (1.519325 sq. km) Water area (2000): 0.000000 sq. miles (0.000000 sq. km) Total area (2000): 0.586615 sq. miles (1.519325 …   StarDict's U.S. Gazetteer Places

  • Fountain Valley, California — Fountain Valley Pour les articles homonymes, voir Fountain. Fountain Valley Pays  …   Wikipédia en Français

  • Fountain Valley (Californie) — Fountain Valley Pour les articles homonymes, voir Fountain. Fountain Valley Pays  …   Wikipédia en Français

  • Fountain City, IN — U.S. town in Indiana Population (2000): 735 Housing Units (2000): 309 Land area (2000): 0.262926 sq. miles (0.680974 sq. km) Water area (2000): 0.000000 sq. miles (0.000000 sq. km) Total area (2000): 0.262926 sq. miles (0.680974 sq. km) FIPS code …   StarDict's U.S. Gazetteer Places

  • Fountain City, WI — U.S. city in Wisconsin Population (2000): 983 Housing Units (2000): 470 Land area (2000): 4.455255 sq. miles (11.539057 sq. km) Water area (2000): 1.116949 sq. miles (2.892884 sq. km) Total area (2000): 5.572204 sq. miles (14.431941 sq. km) FIPS… …   StarDict's U.S. Gazetteer Places

  • Fountain Green — Fountain Green, UT U.S. city in Utah Population (2000): 945 Housing Units (2000): 311 Land area (2000): 1.405912 sq. miles (3.641295 sq. km) Water area (2000): 0.000000 sq. miles (0.000000 sq. km) Total area (2000): 1.405912 sq. miles (3.641295… …   StarDict's U.S. Gazetteer Places

  • Fountain Green, UT — U.S. city in Utah Population (2000): 945 Housing Units (2000): 311 Land area (2000): 1.405912 sq. miles (3.641295 sq. km) Water area (2000): 0.000000 sq. miles (0.000000 sq. km) Total area (2000): 1.405912 sq. miles (3.641295 sq. km) FIPS code:… …   StarDict's U.S. Gazetteer Places

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”