Tornado code

Tornado code[1–3]

Linear binary code that is a precursor to fountain codes and whose encoding and decoding operations involve only XOR gates [4; Sec. 30.2].

Come arbitrarily close to the capacity of the binary erasure channel.

Linear-time encoder.

Linear-time peeling decoder [3]. This decoder either terminates when it has removed a given erasure pattern or when it is stuck in a stopping set.

Fountain code — Tornado codes, the precursor to fountain codes, are much slower to encode and decode in the low-rate regime applicable to scalable data transmission [5,6].
Low-density parity-check (LDPC) code — Tornado codes are similar to LDPC codes, but they use a highly irregular weight distribution for the underlying graphs [6].
Raptor (RAPid 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.

[1]: J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “A digital fountain approach to reliable distribution of bulk data”, ACM SIGCOMM Computer Communication Review 28, 56 (1998) DOI
[2]: M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, and V. Stemann, “Practical loss-resilient codes”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC ’97 150 (1997) DOI
[3]: M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001) DOI
[4]: I. F. Blake, "Coding for Erasures and Fountain Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[5]: Joshi, G., Rhim, J. B., Sun, J., & Wang, D. (2010). Fountain codes. In Global telecommunications conference (GLOBECOM 2010) (pp. 7–12). IEEE.
[6]: A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006) DOI

Page edit log

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