Raptor (RAPid TORnado) code

Raptor (RAPid TORnado) code[1,2]

Description

Raptor codes are concatenated erasure codes with two layers: an outer pre-code and a Luby-Transform (LT) inner code. The pre-code is a linear binary erasure code, which is applied first to the input to create some redundant data. The LT code is then applied to the intermediate symbols from the pre-code to generate final output symbols to be transmitted.

The parameters for a Raptor code are \( (k, C, \Omega(x)) \), with \(C\) being the pre-code with dimension \( k \), and \( \Omega(x) \) being the degree distribution for the LT code.

The times to encode and decode source blocks are both linear. The space requirement is \(1/R \), where \(R\) is the rate of the pre-code. Raptor codes with the simplest output distribution (LT code) are called pre-code-only (PCO).

Protection

As a type of fountain code, a Raptor code is designed to correct erasures. The error probability of Raptor codes is measured in terms of its overhead, which is how many additional symbols are received above the dimension of the input \(k\). This relationship can vary widely depending on the input pre-code and degree distribution. For a well-designed degree distribution, the error probability of a Raptor code is directly related to the error probability of the pre-code's decoder. In other words, if there is a linear time decoder for the pre-code that has subexponentially small error probability, then the Raptor code's error probability will decrease exponentially with increasing overhead (past the \(n-k\) overhead symbols necessary for the pre-code).

Decoding

Raptor codes can be decoded using inactivation decoding [3], a combination of belief-propogation and Gaussian elimination decoding.

Realizations

Two versions of Raptor codes have been standardized by IETF: R10 and the more recent RaptorQ. RaptorQ is used in mobile multimedia broadcasts as specified in ETSI technical specifications. It is also used in the mobile Next Gen TV standard.Raptor codes are useful in scenarios where erasure (i.e. weak signal or noisy channel) is common, such as in military or disaster scenarios.

Notes

There is an open source RaptorQ implementation in Java and Rust.

Parent

Fountain code

Child

Luby transform (LT) code — Raptor codes using a trivial pre-code are LT codes. Typically, Raptor codes have constant-sized more overhead but are faster to decode.

Cousin

Tornado code — Tornado codes, which can be used as a pre-code for raptor codes, also use a multi-layer approach where redundant symbols are created by one code for another code to use as input.

References

[1]: A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006) DOI
[2]: Petar Maymounkov, Online codes, Technical report, New York University, 2002.
[3]: F. Lazaro, G. Liva, and G. Bauch, “Inactivation Decoding of LT and Raptor Codes: Analysis and Code Design”, IEEE Transactions on Communications 1 (2017) arXiv:1706.05814 DOI

Page edit log

Victor V. Albert (2022-05-25) — most recent
Thomas Wrona (2022-04-11)

Cite as:

“Raptor (RAPid TORnado) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/raptor

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/fountain/raptor.yml.