World Library  
Flag as Inappropriate
Email this Article

Fountain code

Article Id: WHEBN0003410547
Reproduction Date:

Title: Fountain code  
Author: World Heritage Encyclopedia
Language: English
Subject: Forward error correction, Amin Shokrollahi, Systematic code, Michael Luby, Michael Mitzenmacher
Collection: Capacity-Approaching Codes, Coding Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Fountain code

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.

Contents

  • Applications 1
  • Fountain codes in standards 2
  • Fountain codes for data storage 3
  • See also 4
  • Notes 5
  • References 6

Applications

Fountain codes are flexibly applicable at a fixed code rate, or where a fixed code rate cannot be determined a priori, and where efficient encoding and decoding of large amounts of data is required.

One example is that of a data carousel, where some large file is continuously broadcast to a set of receivers.[1] Using a fixed-rate erasure code, a receiver missing a source symbol (due to a transmission error) faces the coupon collector's problem: it must successfully receive an encoding symbol which it does not already have. This problem becomes much more apparent when using a traditional short-length erasure code, as the file must be split into several blocks, each being separately encoded: the receiver must now collect the required number of missing encoding symbols for each block. Using a fountain code, it suffices for a receiver to retrieve any subset of encoding symbols of size slightly larger than the set of source symbols. (In practice, the broadcast is typically scheduled for a fixed period of time by an operator based on characteristics of the network and receivers and desired delivery reliability, and thus the fountain code is used at a code rate that is determined dynamically at the time when the file is scheduled to be broadcast.)

Another application is that of hybrid ARQ in reliable multicast scenarios: parity information that is requested by a receiver can potentially be useful for all receivers in the multicast group.

Fountain codes in standards

Raptor codes are the most efficient fountain codes at this time,[2] 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.[3] 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%.[4] 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.[5] 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.

Fountain codes for data storage

Erasure codes are used in data storage applications due to massive savings on the number of storage units for a given level of redundancy and reliability. The requirements of erasure code design for data storage, particularly for distributed storage applications, might be quite different relative to communication or data streaming scenarios. One of the requirements of coding for data storage systems is the systematic form, i.e., the original message symbols are part of the coded symbols. Systematic form enables reading off the message symbols without decoding from a storage unit. In addition, since the bandwidth and communication load between storage nodes can be a bottleneck, codes that allow minimum communication are very beneficial particularly when a node fails and a system reconstruction is needed to achieve the initial level of redundancy. In that respect, fountain codes are expected to allow efficient repair process in case of a failure: When a single encoded symbol is lost, it should not require too much communication and computation among other encoded symbols in order to resurrect the lost symbol. In fact, repair latency might sometimes be more important than storage space savings. Repairable fountain codes[6] are projected to address fountain code design objectives for storage systems. A detailed survey about fountain codes and their applications can be found at.[7]

See also

Notes

  1. ^ J. Byers,  
  2. ^ "Qualcomm Raptor Technology - Forward Error Correction". 
  3. ^ (Shokrollahi 2006)
  4. ^ 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 ( 
  5. ^ (Luby et al. 2010)
  6. ^ M. Asteris and A. G. Dimakis, (2012). Repairable Fountain Codes", In Proc. of 2012 IEEE International Symposium on Information Theory""" (PDF). 
  7. ^ Suayb S. Arslan, (2014). "Incremental Redundancy, Fountain Codes and Advanced Topics" (PDF). 

References

  •  
  • .  
  • P. Maymounkov (November 2002). "Online Codes" (PDF). (Technical Report). 
  •  
  •  .
  • .  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.