Raptor code: Difference between revisions

Revision as of 19:51, 21 December 2020

Latest revision as of 14:34, 25 December 2024

(17 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Fountain code class}}

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

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

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

{{Citation style|date=January 2021}}

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 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 source block of data consisting of a number ''k'' of equal size source symbols into a potentially limitless sequence of encoding symbols 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 code|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. AnSome exampleexamples of a systematic Raptor 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 defined in [[IETF]] RFC 5053.

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

== RaptorQ 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 (see Recovery probability and overhead section below for more details), supports up to 56,403 source symbols, and can support an essentially unlimited number of encoding symbols. There are several implementations of RaptorQ available, including a basic implementation [https://github.com/lorinder/TvRQ TvRq] suitable for testing interoperability, a version developed by the [https://openrq-team.github.io/openrq/ OpenRQ project], a [https://github.com/LucaFulchir/libRaptorQ libRaptorQ version], a [https://github.com/cberner/raptorq RUST implementation of RaptorQ], and a [https://www.bitripple.com/rq high performance commercial-grade implementation of RaptorQ] offered by [https://www.bitripple.com BitRipple].

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 A/331|title=ATSC Candidate Standard: Signaling, Delivery, Synchronization, and Error Protection] within(A/331) |id=ATSC 3.0S33-174r6 (see|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.

== Next Gen TV (ATSC 3.0) incorporates the RaptorQ code ==

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 [https://www.atsc.org/wp-content/uploads/2016/01/A331S33-174r6-Signaling-Delivery-Sync-FEC.pdf A/331: Signaling, Delivery, Synchronization, and Error Protection] within ATSC 3.0 (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 52 ⟶ 53:

* 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 ==

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. These statements mirror the [https://www.qualcomm.com/documents/qualcomm-dash-licensing-commitment/ licensing commitment Qualcomm, Inc. has made] with respect to the

[[Dynamic Adaptive Streaming over HTTP|MPEG DASH standard]]. The MPEG DASH standard has been deployed by a wide variety of companies, including [https://dashif.org/members/ DASH Industry Forum member companies].

== See also ==

* [[Erasure code]]

* [[Fountain codes]]

* [[LT code]]

* [[Fountain codes]]

* [[Michael Luby]]

* [[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/

3. Information about an efficient software implementation of the RaptorQ code specified in [[IETF]] RFC 6330 (the most advanced fountain code),

can be found at [https://www.bitripple.com/rq this webpage of BitRipple].

== References ==

* {{cite journal | author = Amin Shokrollahi and Michael Luby | title=Raptor Codes| journal=Foundations and Trends in Communications and Information Theory |volume=6| issue=3–4| pages=213–322 | year=2011| publisher = Now Publishers | doi = 10.1561/0100000060 }}

* Shokrollahi, Amin, "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)

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

* [http://www.3gpp.org 3GPP] (The 3rd Generation Partnership Project)

Line 84 ⟶ 78:

* [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

== Further reading ==

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

* {{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=6330] "IPR" Search Result for RFC 6330, with statements by some patent owners

* [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]]