## 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–4], moderate [5–7] and large [8–11] deviation analysis. Sometimes the difference from the asymptotic rate at finite block length can be characterized by the channel dispersion [4,12].

## Notes

See Ref. [13] for a list of open problems in coding theory.See Refs. [14,15] for reviews of coding theory.

## 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. In other words, classical codewords are elements of an alphabet, while what codewords are functions on the alphabet. 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 [16].
- Random code

## Cousin

- Quantum error-correcting code (QECC) — Quantum information cannot be copied using a linear process [17], so one cannot send several copies of a quantum state through a channel as can be done for classical information. Error-correction conditions can similarly be formulated for classical codes [18; Sec. 3], although they are not as widely as used as those for quantum codes.

## 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]
- S. H. Hassani, K. Alishahi, and R. L. Urbanke, “Finite-Length Scaling for Polar Codes”, IEEE Transactions on Information Theory 60, 5875 (2014) DOI
- [13]
- S. Dougherty, J.-L. Kim, and P. Solé, “Open Problems in Coding Theory”, Noncommutative Rings and Their Applications 79 (2015) DOI
- [14]
- A. R. Calderbank, “The art of signaling: fifty years of coding theory”, IEEE Transactions on Information Theory 44, 2561 (1998) DOI
- [15]
- D. J. Costello Jr. and G. D. Forney Jr, “Channel Coding: The Road to Channel Capacity”, (2006) arXiv:cs/0611112
- [16]
- 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
- [17]
- W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned”, Nature 299, 802 (1982) DOI
- [18]
- B. Yoshida, “Decoding the Entanglement Structure of Monitored Quantum Circuits”, (2021) arXiv:2109.08691

## 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/edit/main/codes/classical/ecc.yml.