Raptor code: Difference between revisions

Revision as of 18:45, 2 March 2019

Revision as of 19:04, 2 March 2019

Line 1:

{{about|error correction codes|codebases named Raptorraptor|raptor (disambiguation)}}

In [[computer science]], '''raptorRaptor codes''' ('''''rap'''id '''tor'''nado'';<ref>{{cite speech|author=Amin Shokrollahi|title=The Development of Raptor Codes|event=Invited talk at the [[Kungliga Tekniska högskolan]]|date=31 January 2011|url=http://bambuser.com/v/1372056|accessdate=24 February 2012}}</ref> see [[Tornado codes]]) are the first known class 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 are a significant theoretical and practical improvement over [[LT codes]], which were the first practical class of [[fountain codes]].

Raptor codes, as with fountain codes in general, encode a given messagesource consistingblock of adata numberconsisting of symbols,a number ''k'', of equal size symbols into a potentially limitless sequence of [[encoding symbol]]s such that knowledgereception of any ''k'' or more encoding symbols allows the messagesource block to be recovered with some non-zero probability. The probability that the messagesource block can be recovered increases with the number of encoding symbols received above ''k'' becoming very close to 1, once the number of received encoding symbols is only very slightly larger than ''k''. For example, with the latest generation of Raptor codes, the [http://tools.ietf.org/html/rfc6330 RaptorQ] codes, the chance of decoding failure when ''k'' encoding symbols have been received is less than 1%, and the chance of decoding failure when ''k+2'' encoding symbols have been received is less than one in a million. (See ''Recovery probability and overhead'' section below for more discussion on this.) A symbol can be any size, from a single byte to hundreds or thousands of bytes.

Raptor codes may be systematic or non-systematic. In the systematic case, the symbols of the original messagesource block, i.e. the source symbols, are included within the set of encoding symbols. An example of a systematic raptorRaptor 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 standard]]s for IP datacast to handheld devices (see external links). The Raptor codes in these standards is defined also in [[IETF]] RFC 5053. The most advanced version of a practical Raptor code is RaptorQ defined in [[IETF]] RFC 6330.

Information about availability of an efficient software implementation of the

Line 11:

[https://www.codornices.info/ website for the Codornices project at ICSI ].

[[Online codes]] are another example of a non-systematic raptorfountain code.

== Overview ==

Line 23:

This distribution, as well as the mechanism for generating pseudo-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 raptorRaptor codes, the source data to be encoded is used as the input to the pre-coding stage.

In the case of systematic raptorRaptor 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 pseudo-random

processes which generate the first ''k'' output symbols generate an operation which is invertible.

== Decoding ==

Two approaches are possible for decoding raptorRaptor 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]].

Line 36:

== Computational complexity ==

Raptor codes require ''O(1symbol size)'' time to generate an encoding symbol. Decoding a messagesource of lengthblock ''k'' source symbols utilizing a combination of a belief propagation decoding algorithm and Gaussian elimination decoding requires ''O(k*symbol size)'' time for the appropriate choice of inner/outer codes.

== Recovery probability and overhead ==