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
- Victor V. Albert (2022-05-26) — most recent
- Thomas Wrona (2022-05-02)
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.