Raptor code: Difference between revisions

Revision as of 20:08, 20 December 2020

Revision as of 20:11, 20 December 2020

Line 2:

In [[computer science]], '''Raptor 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 source block of data consisting of a number ''k'' of equal size source symbols into a potentially limitless sequence of [[encoding symbol]]ssymbols such that reception of any ''k'' or more encoding symbols allows the source block to be recovered with some non-zero probability. The probability that the source 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 source block, i.e. the source symbols, 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 standard]]s for IP datacast to handheld devices (see external links). The Raptor codes in these standards is defined also in [[IETF]] RFC 5053.

Line 20:

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]]s. Each encoding symbol is the [[XOR]] of a pseudo-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 pseudo-randomly for each output symbol according to a specific probability distribution.