[Jump to code hierarchy]

Error-correcting code (ECC)

Root code for the Classical Domain
Codes for communication over classical channels

Description

Code designed for transmission of classical information through classical channels.

A code is a subset of a set or alphabet \(\Sigma\), with each element called a codeword. An error-correcting code consists of \(K\) codewords over an alphabet with \(N\) elements such that it is possible to recover the codewords from errors \(E\) from some error set \(\mathcal{E}\). The table below lists the most common alphabets, along with names of the corresponding codewords of a block code, i.e., a code on \(n\) copies of the alphabet.

alphabet \(\Sigma\)

codewords

\(\mathbb{Z}_{2}=\mathbb{F}_2\)

bitstrings

\(\mathbb{F}_q\)

\(q\)-ary strings

\(\mathbb{Z}_{q}\)

\(q\)-ary strings over \(\mathbb{Z}_{q}\)

\(\mathbb{R}\)

sphere packings

\(G\)

group elements

\(G/H\)

cosets

Table I: Table listing the most common alphabets used in ECCs. Here, \(\mathbb{F}_q\) is a finite field, \(G\) is a group, and \(H\) is a subgroup of \(G\).

Finite-field alphabet

Finite fields: The most common and useful [1] alphabets used in block codes are Galois or finite fields \(\mathbb{F}_q\), which are sets of \(q\) elements closed under addition and multiplication. They are finite analogues of the real or complex numbers, and a unique field exists for every power \(q=p^m\) of a prime \(p\). The prime-field case reduces to \(\mathbb{Z}_p\), a group under addition that is promoted to a field by defining multiplication modulo \(p\); the case \(p=2\) yields the binary field \(\mathbb{Z}_2\). Every finite field comes with a 0 element (additive identity), a 1 element (multiplicative identity), and additive (multiplicative) inverses for all (nonzero) elements. An element whose powers exhaust all nonzero field elements is called primitive. Fields come with a trace operation, the field trace, which maps elements \(\gamma \in \mathbb{F}_q\) to elements of \(\mathbb{F}_p\) as \begin{align} tr(\gamma)=\sum_{k=0}^{m-1}\gamma^{p^{k}}~.\tag*{$(1)$} \end{align}The field trace can be thought of as an averaging over the field’s Galois group, which is the cyclic group generated by \(\gamma\to\gamma^p\) [2; pg. 113]. Fields also come with a field norm, \begin{align} N(\gamma)=\prod_{k=0}^{m-1}\gamma^{p^{k}}=\gamma^{(p^{m}-1)/(p-1)}~.\tag*{$(2)$} \end{align}In the case of the complex numbers, analogues of the field trace and field norm are the real part and norm squared of a complex number, respectively.

Any field \(\mathbb{F}_{q=p^m}\) can be thought of as an \(m\)-dimensional vector space over \(\mathbb{F}_p\) a.k.a. the \(m\)th extension of \(\mathbb{F}_p\) (similar to the complex numbers being an extension of the reals). Conversely, \(\mathbb{F}_p\) is an example of a subfield of \(\mathbb{F}_q\). Certain field elements are chosen to be the basis of \(\mathbb{F}_q\) over \(\mathbb{F}_p\), and all other elements are expressed as linear combinations of these basis elements. More generally, elements of fields such as \(\mathbb{F}_{p^{ml}}\) can be written as \(m\)-dimensional vectors over \(\mathbb{F}_{p^l}\) or \((m\times l)\)-dimensional matrices over \(\mathbb{F}_p\). This idea is used to convert between ordinary block codes and matrix-based codes such as disk array codes and rank-metric codes. The field norm and field trace can likewise be defined for fields \(\mathbb{F}_{q^m}\) that are extensions of \(\mathbb{F}_q\) for non-prime \(q\).

An example of a field is the quaternary Galois field \(\mathbb{F}_4 = \{0,1,\omega, \omega^2=\bar{\omega}\}\) with \(p=m=2\). In this case, \(\omega\) can be interpreted as a third root of unity, but more formally it is defined as a solution to the polynomial equation \(1+x+x^2=0\). Field elements can be represented as two-dimensional vectors with binary elements, \(\mathbb{F}_4=\mathbb{F}_2^2\), using the basis \(1\cong(1,0)\) and \(\omega\cong(0,1)\): \begin{align} 0&\leftrightarrow(0,0)\cong0\cdot1+0\cdot\omega\tag*{$(3)$}\\1&\leftrightarrow(0,1)\cong0\cdot1+1\cdot\omega\tag*{$(4)$}\\\omega&\leftrightarrow(1,1)\cong1\cdot1+1\cdot\omega\tag*{$(5)$}\\\bar{\omega}&\leftrightarrow(1,0)\cong1\cdot1+0\cdot\omega~.\tag*{$(6)$} \end{align}In this way, the field elements form the Klein four group \(\mathbb{Z}_2\times\mathbb{Z}_2\) under addition. One can check that the trace operation, \(tr(\gamma) = \gamma + \gamma^2\), outputs either 0 or 1 for any element \(\gamma\in \mathbb{F}_4\).

Rate

The Shannon channel capacity (the maximum of the mutual information over input distributions) is the highest rate of information transmission through a classical (i.e., non-quantum) channel with arbitrarily small error rate [3]. The fault-tolerant capacity is the capacity for the more general case where the encoding and decoding maps are also assumed to undergo noise [4].

Corrections to the capacity and tradeoff between decoding error, code rate and code length are determined using small [5–7], moderate [8–10] and large [11–14] deviation analysis. Sometimes the difference from the asymptotic rate at finite block length can be characterized by the channel dispersion [7,15]. Doeblin coefficients [16] for classical channels have been studied [17].

Notes

See Ref. [18] for a list of open problems in coding theory.See Refs. [19,20] for reviews of coding theory.Classical systems such as RAM [21], HPC systems [22–24], and data centers [25] suffer from noise.

Cousins

  • Two-point homogeneous-space code— ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [26,27].
  • \(t\)-design— ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [26,27].
  • Quantum error-correcting code (QECC)— Quantum information cannot be copied using a linear process [28], so one cannot send several copies of a quantum state through a channel as can be done for classical information. The Knill-Laflamme conditions can similarly be formulated for classical codes [29; Sec. 3], although they are not as widely used as those for quantum codes.

Member of code lists

Primary Hierarchy

Classical Domain
Parents
Classical-quantum (c-q) 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 quantum codewords are functions on the alphabet. Classical codes can be unified with quantum codes using various algebraic frameworks [30,31].
Error-correcting code (ECC)
Children
Homogeneous-space codeModulation scheme Lattice Array MDS array STC MSRD Self-dual additive Linear \(q\)-ary Self-dual linear QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible AG Evaluation OA Perfect GRM Balanced MRD Polytope Polyhedron Lattice-shell Spherical design Constant-weight Combinatorial design Nearly perfect Perfect binary Linear code over \(\mathbb{Z}_q\) Gray Universally optimal Sharp configuration MDS GRS
Block codeModulation scheme Polytope Polyhedron Lattice-shell Spherical design Lattice STC FP Distributed-storage Array MDS array MSRD MRD LRC LCC LDC LTC Editing Small-distance block Skew-cyclic Constacyclic Cyclic Self-dual additive Linear \(q\)-ary Self-dual linear QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible AG Evaluation OA Perfect GRM MDS GRS Balanced Linear code over \(\mathbb{Z}_q\) Constant-weight Combinatorial design Gray Nearly perfect Perfect binary
Generalized concatenated code (GCC)Concatenated
Parallel concatenated codeTanner \(q\)-ary LDPC
Finite-dimensional error-correcting code (ECC)STC FP Distributed-storage Array MDS array MSRD MRD LRC LCC LDC LTC Editing Small-distance block Self-dual additive AG OA Perfect Balanced Constant-weight Combinatorial design Nearly perfect Perfect binary Linear code over \(\mathbb{Z}_q\) Linear \(q\)-ary Evaluation Gray GRM QR MDS GRS Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible Self-dual linear
Group-orbit codeLattice Self-dual additive Linear \(q\)-ary Evaluation GRM QR MDS GRS Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible Self-dual linear Linear code over \(\mathbb{Z}_q\) Gray Polytope Polyhedron
Not all codes are group-orbit codes, and more generally one can classify codewords into orbits of the automorphism group [32].
Random code
Convolutional code

References

  1. [1]

    N. Levinson, “Coding Theory: A Counterexample to G. H. Hardy’s Conception of Applied Mathematics”, The American Mathematical Monthly 77, 249 (1970) DOI

  2. [2]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  3. [3]

    C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI

  4. [4]

    M. Christandl and A. Müller-Hermes, “Fault-Tolerant Coding for Quantum Communication”, IEEE Transactions on Information Theory 70, 282 (2024) arXiv:2009.07161 DOI

  5. [5]

    V. Strassen, “Asymptotische Absch¨atzungen in Shannons Informationstheorie”, Trans. Third Prague Conference on Information Theory, Prague, 689–723, (1962)

  6. [6]

    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

  7. [7]

    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

  8. [8]

    Y. Altug and A. B. Wagner, “Moderate Deviations in Channel Coding”, (2012) arXiv:1208.1924

  9. [9]

    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) 1334 (2010) DOI

  10. [10]

    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

  11. [11]

    R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI

  12. [12]

    I. Csiszár and J. Körner, Information Theory (Cambridge University Press, 2011) DOI

  13. [13]

    S. Arimoto, “On the converse to the coding theorem for discrete memoryless channels (Corresp.)”, IEEE Transactions on Information Theory 19, 357 (1973) DOI

  14. [14]

    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

  15. [15]

    S. H. Hassani, K. Alishahi, and R. L. Urbanke, “Finite-Length Scaling for Polar Codes”, IEEE Transactions on Information Theory 60, 5875 (2014) DOI

  16. [16]

    W. Doeblin, “Sur les propriétés asymptotiques de mouvement régis par certains types de chaines simples”, Bulletin mathématique de la Société roumaine des sciences 39(1), 57-115 (1937)

  17. [17]

    A. Makur and J. Singh, “Doeblin Coefficients and Related Measures”, IEEE Transactions on Information Theory 70, 4667 (2024) arXiv:2309.08475 DOI

  18. [18]

    S. Dougherty, J.-L. Kim, and P. Solé, “Open Problems in Coding Theory”, Contemporary Mathematics 79 (2015) DOI

  19. [19]

    A. R. Calderbank, “The art of signaling: fifty years of coding theory”, IEEE Transactions on Information Theory 44, 2561 (1998) DOI

  20. [20]

    D. J. Costello and G. D. Forney, “Channel Coding: The Road to Channel Capacity”, (2006) arXiv:cs/0611112

  21. [21]

    B. Schroeder, E. Pinheiro, and W.-D. Weber, “DRAM errors in the wild”, Communications of the ACM 54, 100 (2011) DOI

  22. [22]

    S. Levy, K. B. Ferreira, N. DeBardeleben, T. Siddiqua, V. Sridharan, and E. Baseman, “Lessons Learned from Memory Errors Observed Over the Lifetime of Cielo”, SC18: International Conference for High Performance Computing, Networking, Storage and Analysis 554 (2018) DOI

  23. [23]

    K. B. Ferreira, S. Levy, J. Hemmert, and K. Pedretti, “Understanding Memory Failures on a Petascale Arm System”, Proceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing 84 (2022) DOI

  24. [24]

    C. Di Martino, Z. Kalbarczyk, R. K. Iyer, F. Baccanico, J. Fullop, and W. Kramer, “Lessons Learned from the Analysis of System Failures at Petascale: The Case of Blue Waters”, 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks 610 (2014) DOI

  25. [25]

    J. Meza, Q. Wu, S. Kumar, and O. Mutlu, “Revisiting Memory Errors in Large-Scale Production Data Centers: Analysis and Modeling of New Trends from the Field”, 2015 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks 415 (2015) DOI

  26. [26]

    P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI

  27. [27]

    R. A. Bailey, Association Schemes (Cambridge University Press, 2004) DOI

  28. [28]

    W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned”, Nature 299, 802 (1982) DOI

  29. [29]

    B. Yoshida, “Decoding the Entanglement Structure of Monitored Quantum Circuits”, (2021) arXiv:2109.08691

  30. [30]

    M. K. Patra and S. L. Braunstein, “An algebraic framework for information theory: Classical Information”, (2009) arXiv:0910.1536

  31. [31]

    G. Kuperberg and N. Weaver, “A von Neumann algebra approach to quantum metrics”, (2010) arXiv:1005.0353

  32. [32]

    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

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: ecc

Cite as:
“Error-correcting code (ECC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/ecc, arXiv:2606.11484
BibTeX:
@incollection{eczoo_ecc,
title={Error-correcting code (ECC)},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
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.), 2026. https://errorcorrectionzoo.org/c/ecc, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/ecc.yml.