Raptor code

Raptor code

In computer science, raptor codes are one of the first known classes of fountain codes with linear time encoding and decoding. They were invented by Amin Shokrollahi in 2000/2001 and were first published in 2004 as an extended abstract.

Raptor codes encode a given message consisting of a number of symbols, "k", into a potentially limitless sequence of encoding symbols such that knowledge of any "k" or more encoding symbols allows the message to be recovered with some non-zero probability. The probability that the message can be recovered increases with the number of symbols received above "k" becoming very close to 1, once the number of received symbols is only very slightly larger than "k". A symbol can be any size, from a single bit to hundreds or thousands of bytes.

Raptor codes may be systematic or non-systematic. In the systematic case, the symbols of the original message are included within the set of encoding symbols. An example of a systematic raptor code is the code defined by the 3rd Generation Partnership Project for use in mobile cellular wireless broadcast and multicast and also used by DVB-H standards for IP datacast to handheld devices (see external links). Online codes are an example of a non-systematic raptor code.

Overview

Raptor codes are formed by the concatenation of two codes.

A fixed rate erasure code, usually with a fairly high rate, is applied as a 'pre-code' or 'outer code'. This pre-code may itself be a concatenation of multiple codes, for example in the code standardized by 3GPP a high density parity check code derived from the binary Gray sequence is concatenated with a simple regular low density parity check code. Another possibility would be a concatenation of a Hamming code with a low density parity check code.

The inner code takes the result of the pre-coding operation and generates a sequence of encoding symbols. The inner code is a form of LT code. Each encoding symbol is the XOR of a randomly chosen set of symbols from the pre-code output. The number of symbols which are XOR'ed together to form an output symbol is chosen randomly for each output symbol according to a specific probability distribution.

This distribution, as well as the mechanism for generating random numbers for sampling this distribution and for choosing the symbols to be XOR'ed, must be known to both sender and receiver. In one approach, each symbol is accompanied with an identifier which can be used as a seed to a pseudo-random number generator to generate this information, with the same process being followed by both sender and receiver.

In the case of non-systematic raptor codes, the source data to be encoded is used as the input to the pre-coding stage.

In the case of systematic raptor codes, the input to the pre-coding stage is obtained by first applying the inverse of the encoding operation that generates the first "k" output symbols to the source data. Thus, applying the normal encoding operation to the resulting symbols causes the original source symbols to be regenerated as the first "k" output symbols of the code. It is necessary to ensure that the randomprocesses which generate the first "k" output symbols generate an operation which is invertible.

Decoding

Two approaches are possible for decoding raptor codes. In a concatenated approach, the inner code is decoded first, using a belief propagation algorithm, as used for the LT codes. Decoding succeeds if this operation recovers a sufficient number of symbols, such that the outer code can recover the remaining symbols using the decoding algorithm appropriate for that code.

In a combined approach, the relationships between symbols defined by both the inner and outer codes are considered as a single combined set of simultaneous equations which can be solved by the usual means, typically by Gaussian elimination.

Computational complexity

Raptor codes require "O(1)" time to generate an encoding symbol and "O(k)" time to decode a message of length "k".

See also

* Erasure code
* LT code
* Graphical code
* Michael Luby

References

* Amin Shokrollahi, "Raptor Codes," IEEE Transactions on Information Theory, vol. 52, 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]
* [http://www.3gpp.org 3GPP] The 3rd Generation Partnership Project
* [http://www.dvb.org DVB] Digital Video Broadcasting
* [http://www.3gpp.org/ftp/Specs/html-info/26346.htm 3GPP TS26.346] 3GPP Technical Specification for Multimedia Broadcast/Multicast Service: Protocols and Codecs.
* [http://www.dvb-h-online.org/technology.htm DVB-H IP Datacasting specifications]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Raptor FEC codes — Raptor Forward Error Correction Technology Rapator FEC technology is an intelligence property of Digital Fountain and adopted by several industry standards such as 3GPP, 3GPP2, DVB H and Reliable Multicast Transport (RMT) working group within the …   Wikipedia

  • Raptor FEC Technology — is an intelligence property of Digital Fountain and adopted by several industry standards such as 3GPP, 3GPP2, DVB H and Reliable Multicast Transport (RMT) working group within the Internet Engineering Task Force (IETF). DF Raptor FEC is an… …   Wikipedia

  • Raptor weapon — The Raptor precision guided glide bomb family was developed by Denel Aerospace based in South Africa under the code names H 1, H 2 and H 3 from the late 1970s onwards. Raptor 1 The Raptor 1 is a glide bomb launched from an aircraft. Its modular… …   Wikipedia

  • 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… …   Wikipedia

  • LT code — In computer science, LT codes (Luby Transform codes) are the first class of practical fountain codes that are near optimal erasure correcting codes invented by Michael Luby in 1998 and published in 2002. [http://ieeexplore.ieee.org/xpl/freeabs… …   Wikipedia

  • Lockheed Martin F-22 Raptor — Lockheed Martin F 22 Raptor …   Wikipédia en Français

  • F-22 Raptor — Infobox Aircraft name= F 22 Raptor type= Stealth Air superiority fighter national origin = United States manufacturers=Lockheed Martin Aeronautics Boeing Integrated Defense Systems caption= Two F 22 Raptors in column flight formation designer=… …   Wikipedia

  • Lockheed Martin F-22 Raptor — F 22 Raptor Un F 22 Raptor del 27º Escuadrón de Caza de la USAF volando en enero de 2009. Tipo Caza de superioridad aérea furtivo …   Wikipedia Español

  • List of computer technology code names — Following is a list of code names that have been used to identify computer hardware and software products while in development. In some cases, the code name became the completed product s name, but most of these code names are no longer used once …   Wikipedia

  • Erasure code — In information theory, an erasure code is a forward error correction (FEC) code for the binary erasure channel, which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be… …   Wikipedia

Share the article and excerpts

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