In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, Raptor codes (''rapid tornado'';
see
Tornado codes) are the first known class of
fountain codes In coding 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 symbols such that the origin ...
with linear time encoding and decoding. They were invented by
Amin Shokrollahi
Amin Shokrollahi (born 1964) is an Iranian mathematician who has worked on a variety of topics including coding theory and algebraic complexity theory. He is best known for his work on iterative decoding of graph based codes for which he receive ...
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 In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT ...
, which were the first practical class of
fountain codes In coding 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 symbols such that the origin ...
.
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 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. Some examples of a systematic Raptor code is the use by the
3rd Generation Partnership Project in
mobile cellular wireless broadcasting and multicasting, and also by
DVB-H standard
DVB-H (Digital Video Broadcasting - Handheld) is one of three prevalent mobile TV formats. It is a technical specification for bringing broadcast services to mobile handsets. DVB-H was formally adopted as ETSI standard EN 302 304 in November 20 ...
s for IP datacast to handheld devices (see external links). The Raptor codes used in these standards is also defined in
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
RFC 5053.
Online codes In computer science, online codes are an example of rateless erasure codes. These codes can encode a message into a number of symbols such that knowledge of any fraction of them allows one to recover the original message (with high probability). ''R ...
are an example of a non-systematic fountain code.
RaptorQ code
The most advanced version of Raptor is the RaptorQ code defined in
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
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.
The RaptorQ code defined in
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
RFC 6330 is specified as a part of the Next Gen TV (
ATSC 3.0
ATSC 3.0 is a major version of the ATSC standards for television broadcasting created by the Advanced Television Systems Committee (ATSC).
The standards are designed to offer support for newer technologies, including HEVC for video channels of u ...
) 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 i
A/331: Signaling, Delivery, Synchronization, and Error Protectionwithin ATSC 3.0 (see
List of ATSC standards
Below are the published ATSC standards for ATSC digital television service, issued by the Advanced Television Systems Committee.
*A/49: Ghost Canceling Reference Signal for NTSC (for adjacent-channel interference or co-channel interference with an ...
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
Raptor codes are formed by the concatenation of two codes.
A fixed rate
erasure code
In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of ''k'' symbols into a longer message (code word) with ''n'' symbols such that the ...
, 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
The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).
For example, the representati ...
is concatenated with a simple regular
low density parity check code
In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC code is constructed using a sparse Tanner graph (subclass of the b ...
. Another possibility would be a concatenation of a
Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...
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 In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT ...
s. Each encoding symbol is the
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
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.
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 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 pseudo-random
processes 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
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
.
Computational complexity
Raptor codes require ''O(symbol size)'' time to generate an encoding symbol from a source block, and require ''O(source block size)'' time to recover a source block from at least ''k'' encoding symbols.
Recovery probability and overhead
The overhead is how many additional encoding symbols beyond the number ''k'' of source symbols in the original source block need to be
received to completely recover the source block.
(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
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
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
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
RFC 6330, i.e., ''k''=1,...,56403. See
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
RFC 6330 for more details.
Legal status
Qualcomm, Inc. has published an IPR statement for the Raptor code specified in
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
RFC 5053, and an IPR statement for the more advanced RaptorQ code specified in
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
RFC 6330. These statements mirror the licensing commitment Qualcomm, Inc. has made with respect to the
MPEG DASH standard. The MPEG DASH standard has been deployed by a wide variety of companies, including DASH Industry Forum member companies.
See also
*
Erasure code
In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of ''k'' symbols into a longer message (code word) with ''n'' symbols such that the ...
*
LT code In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT ...
*
Fountain codes In coding 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 symbols such that the origin ...
*
Tornado codes In coding theory, Tornado codes are a class of erasure codes that support error correction. Tornado codes require a constant C more redundant blocks than the more data-efficient Reed–Solomon erasure codes, but are much faster to generate and can ...
Notes
{{reflist
References
* Shokrollahi, Amin, "Raptor Codes," IEEE Transactions on Information Theory, vol. 52, pp. 2551-2567, 2006
PDF(requires login)
*
ATSC 3.0
ATSC 3.0 is a major version of the ATSC standards for television broadcasting created by the Advanced Television Systems Committee (ATSC).
The standards are designed to offer support for newer technologies, including HEVC for video channels of u ...
(Advanced Television Standards Committee 3.0)
3GPP(The 3rd Generation Partnership Project)
DVB(Digital Video Broadcasting)
3GPP Technical Specification for Multimedia Broadcast/Multicast Service: Protocols and Codecs.
RFC5053Raptor Forward Error Correction Scheme for Object Delivery
RFC6330RaptorQ Forward Error Correction Scheme for Object Delivery
"IPR" Search Result for RFC 5053, with statements by some patent owners
"IPR" Search Result for RFC 6330, with statements by some patent owners
Coding theory