Error-correcting code (ECC)
Description
Code designed for transmission of classical information through classical channels in a robust way.
Rate
The Shannon channel capacity (the maximum of the mutual information over input and output distributions) is the highest rate of information transmission through a classical (i.e., non-quantum) channel with arbitrarily small error rate [1]. Corrections to the capacity and tradeoff between decoding error, code rate and code length are determined using small [2][3][4], moderate [5][6][7] and large [8][9][10][11] deviation analysis.
Parent
- Operator-algebra error-correcting code — Any ECC can be embedded into a quantum Hilbert space, and thus passed through a quantum channel, by associating elements of the alphabet with basis vectors in a Hilbert space over the complex numbers. For example, a bit of information can be embedded into a two-dimensional vector space by associating the two bit values with two basis vectors for the space.
Children
- Group-alphabet code
- Block code
- Generalized concatenated code
- Parallel concatenated code
- Finite-dimensional error-correcting code (ECC)
- Group-orbit code — Not all codes are group-orbit codes, and more generally one can classify codewords into orbits of the automorphism group [12].
- Random code
Cousin
References
- [1]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI
- [2]
- V. Strassen, “Asymptotische Absch¨atzungen in Shannons Informationstheorie,” Trans. Third Prague Conference on Information Theory, Prague, 689–723, (1962)
- [3]
- M. Hayashi, “Information Spectrum Approach to Second-Order Coding Rate in Channel Coding”, IEEE Transactions on Information Theory 55, 4947 (2009) arXiv:0801.2242 DOI
- [4]
- Y. Polyanskiy, H. V. Poor, and S. Verdu, “Channel Coding Rate in the Finite Blocklength Regime”, IEEE Transactions on Information Theory 56, 2307 (2010) DOI
- [5]
- Y. Altug and A. B. Wagner, “Moderate Deviations in Channel Coding”, (2012) arXiv:1208.1924
- [6]
- Y. Polyanskiy and S. Verdu, “Channel dispersion and moderate deviations limits for memoryless channels”, 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2010) DOI
- [7]
- C. T. Chubb, V. Y. F. Tan, and M. Tomamichel, “Moderate Deviation Analysis for Classical Communication over Quantum Channels”, Communications in Mathematical Physics 355, 1283 (2017) arXiv:1701.03114 DOI
- [8]
- R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
- [9]
- I. Csiszár and J. Körner, Information Theory (Cambridge University Press, 2011) DOI
- [10]
- S. Arimoto, “On the converse to the coding theorem for discrete memoryless channels (Corresp.)”, IEEE Transactions on Information Theory 19, 357 (1973) DOI
- [11]
- G. Dueck and J. Korner, “Reliability function of a discrete memoryless channel at rates above capacity (Corresp.)”, IEEE Transactions on Information Theory 25, 82 (1979) DOI
- [12]
- J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
Page edit log
- Victor V. Albert (2022-11-06) — most recent
Cite as:
“Error-correcting code (ECC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ecc
Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/ecc.yml.