Tornado code[13] 

Description

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

Rate

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

Encoding

Linear-time encoder.

Decoding

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.

Parents

Cousins

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

References

[1]
J. W. Byers et al., “A digital fountain approach to reliable distribution of bulk data”, ACM SIGCOMM Computer Communication Review 28, 56 (1998) DOI
[2]
M. G. Luby et al., “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 et al., “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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: tornado

Cite as:
“Tornado code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/tornado
BibTeX:
@incollection{eczoo_tornado, title={Tornado code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/tornado} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/tornado

Cite as:

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

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