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 [24], moderate [57] and large [811] 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

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

Your contribution is welcome!

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

edit on this site

Zoo Code ID: ecc

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

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.