Raptor code: Difference between revisions

Revision as of 18:45, 2 March 2019

Latest revision as of 14:34, 25 December 2024

(43 intermediate revisions by 19 users not shown)

Line 1:

{{Short description|Fountain code class}}

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

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]].

{{More citations needed|date=June 2024}}

{{Citation style|date=January 2021}}

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 codescode]]s) 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 source symbols into a potentially limitless sequence of [[encoding symbol]]ssymbols 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. A symbol can be any size, from a single byte to hundreds or thousands of bytes.

Raptor codes may be [[systematic code|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. AnSome exampleexamples of a systematic raptorRaptor code is the code defineduse by the [[3rd Generation Partnership Project]] for use in [[mobile cellular wireless]] broadcastbroadcasting and multicastmulticasting, and also used by [[DVB-H standard]]s for IP datacast to handheld devices (see external links).{{cn|date=June 2024}} The Raptor codes used 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 63305053.

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

Information about availability of an efficient software implementation of the

the RaptorQ code specified in [[IETF]] RFC 6330 (the most advanced fountain code),

can be found at the

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

== RaptorQ code ==

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

The most advanced version of Raptor is the RaptorQ code defined in [[IETF]] RFC 6330. The RaptorQ code is a systematic code, can be implemented in a way to achieve linear time encoding and decoding performance, has near-optimal recovery properties, supports up to 56,403 source symbols, and can support an essentially unlimited number of encoding symbols.

The RaptorQ code defined in [[IETF]] RFC 6330 is specified as a part of the Next Gen TV ([[ATSC 3.0]]) standard to enable high quality broadcast video streaming (robust mobile TV) and efficient and reliable broadcast file delivery (datacasting). In particular, the RaptorQ code is specified in A/331 within ATSC 3.0.<ref>{{cite report |date=22 March 2017 |url=https://www.atsc.org/wp-content/uploads/2016/01/A331S33-174r6-Signaling-Delivery-Sync-FEC.pdf |title=ATSC Candidate Standard: Signaling, Delivery, Synchronization, and Error Protection (A/331) |id=ATSC S33-174r6 |publisher=Advanced Television Systems Committee}}</ref> See [[List of ATSC standards]] for a list of the ATSC 3.0 standard parts. Next Gen TV (ATSC 3.0) goes well-beyond traditional TV to provide a Broadcast internet enabling general data delivery services.

== Overview ==

Line 17 ⟶ 21:

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.

Line 23 ⟶ 27:

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 ⟶ 40:

== Computational complexity ==

Raptor codes require ''O(1symbol size)'' time to generate an encoding symbol. Decodingfrom a messagesource ofblock, lengthand require ''kO(source block size)'' utilizingtime a combinationto ofrecover a beliefsource propagationblock decodingfrom algorithmat and Gaussian elimination decoding requiresleast ''O(k)'' time for the appropriate choice of inner/outerencoding codessymbols.

== Recovery probability and overhead ==

Line 44 ⟶ 48:

(Based on elementary information theory considerations, complete recovery of a source block with ''k'' source symbols is not possible if less than ''k'' encoding symbols are received.)

The recovery probability is the probability that the source block is completely recovered upon receiving a given number of random encoding symbols generated from the source block.

The RaptorQ code specified in [[IETF]] RFC 6330 has the following trade-off between recovery probability and recovery overhead:

* Greater than 99% recovery probability with overhead of 0 symbols (recovery from ''k'' received encoding symbols).

* Greater than 99.99% recovery probability with overhead of 1 symbol (recovery from ''k+1'' received encoding symbols).

* Greater than 99.9999% recovery probability with overhead of 2 symbols (recovery from ''k+2'' received encoding symbols).

These statements hold for the entire range of ''k'' supported in [[IETF]] RFC 6330, i.e., ''k''=1,...,56403. See [[IETF]] RFC 6330 for more details.<ref name="RFC 6330"/>

== Legal status ==

There are multiple patents on Raptor code technology. Qualcomm, Inc. has published an [https://datatracker.ietf.org/ipr/1957/ IPR statement for the Raptor code] specified in [[IETF]] RFC 5053, and an [https://datatracker.ietf.org/ipr/2554/ IPR statement for the more advanced RaptorQ code] specified in [[IETF]] RFC 6330,. bothThese of whichstatements mirror the [https://www.qualcomm.com/documents/qualcomm-dash-licensing-commitment/ licensing commitment Qualcomm, Inc. has made] with respect to the

[https://en.wikipedia.org/wiki/Dynamic_Adaptive_Streaming_over_HTTP[Dynamic Adaptive Streaming over HTTP|MPEG DASH standard],]. whichThe MPEG DASH standard has been deployed by a wide variety of companies, see for example the [https://dashif.org/members/ list ofincluding DASH Industry Forum member companies].

== See also ==

* [[Erasure code]]

* [[LT code]]

* [[Fountain codes]]

* [[MichaelLT Lubycode]]

* [[Tornado codes]]

== Notes ==

{{reflist}}|refs=

<ref name="RFC 6330">{{cite report |vauthors=Luby M, Shokrollahi A, Watson M, Stockhammer T, Minder L |date=August 2011 |title=Request for Comments: 6330. RaptorQ Forward Error Correction Scheme for Object Delivery |url=http://tools.ietf.org/html/rfc6330 |issn=2070-1721}}</ref>

}}

2. The Open Source Implementation of Raptor Code RFC5053 can be found here : https://code.google.com/p/raptor-code-rfc/

== References ==

* [[ATSC 3.0]] (Advanced Television Standards Committee 3.0)

* 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] (requires login)

* [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://tools.ietf.org/html/rfc5053 RFC5053] Raptor Forward Error Correction Scheme for Object Delivery

* [http://www.dvb-h-online.org/technology.htm DVB-H IP Datacasting specifications]

* [http://tools.ietf.org/html/rfc6330 RFC6330] RaptorQ Forward Error Correction Scheme for Object Delivery

* [https://datatracker.ietf.org/ipr/search/?option=rfc_search&rfc_search=5053] "IPR" Search Result for RFC 5053, with statements by some patent owners

* [https://datatracker.ietf.org/ipr/search/?option=rfc_search&rfc_search=6330] "IPR" Search Result for RFC 6330, with statements by some patent owners

== Further reading ==

* {{cite journal |last=Shokrollahi |first=Amin |title=Raptor Codes |journal=IEEE Transactions on Information Theory |volume=52 |pages=2551-2567 |date=June 2006 |doi=10.1109/TIT.2006.874390 |url=https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1638543 |url-access=subscription}}

* [https://datatracker.ietf.org/ipr/search/?option=rfc_search&rfc_search=5053] "IPR" Search Result for RFC 5053], with statements by some patent owners

* [https://datatracker.ietf.org/ipr/search/?option=rfc_search&rfc_search=6330] "IPR" Search Result for RFC 6330], with statements by some patent owners

[[Category:Coding theory]]