[Jump to code hierarchy]

Finite-dimensional error-correcting code (ECC)[1]

Description

An error-correcting code defined over a finite alphabet.

Protection

A code corrects errors associated with a noise channel if it is possible to recover any codeword after its coordinates have been altered during transmission through the channel.

More technically, an error-correcting code can be specified by an encoder \(e:[1\cdots K]\to\Sigma^n\) together with a set \(\mathcal{E}\) of correctable errors \(E:\Sigma^n\to Y\) such that there exists a decoder \(d:Y\to[1\cdots K]\) satisfying \(d(E(e(x)))=x\) for all \(E\in\mathcal{E}\) and messages \(x\in[1\cdots K]\) [2].

Finite ECCs can also be defined by axiomatically defining their encoding functions [3].

Decoding

Capacity-achieving Guessing Random Additive Noise Decoding (GRAND) [4] (see also [5]).

Notes

The modern theory of error-correcting codes is rooted in the foundational work of C. Shannon [1], but error-correcting codes have been used prior to that work [6].Boolean networks, designed to model gene regulatory networks, generically develop error-correcting codes when they are evolved to perform computations [7].

Cousin

Member of code lists

Primary Hierarchy

Classical Domain
Error-correcting code (ECC)
Parents
Error-correcting code (ECC)
Finite-dimensional error-correcting code (ECC)
Children
Matrix-based codeArray MDS array STC MSRD MRD Constant-weight Combinatorial design Self-dual additive Linear \(q\)-ary Gray Evaluation Self-dual linear Cyclic QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible AG OA Perfect Nearly perfect Perfect binary GRM MDS GRS Balanced
Ring codeSelf-dual additive AG OA Perfect Balanced Constant-weight Combinatorial design Nearly perfect Perfect binary Linear code over \(\mathbb{Z}_q\) Linear \(q\)-ary MDS Gray Evaluation GRS Cyclic GRM QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible Self-dual linear

References

[1]
C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI
[2]
D. Gottesman. Surviving as a quantum computer in a classical world (2024) URL
[3]
A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
[4]
K. R. Duffy, J. Li, and M. Medard, “Capacity-Achieving Guessing Random Additive Noise Decoding”, IEEE Transactions on Information Theory 65, 4023 (2019) arXiv:1802.07010 DOI
[5]
K. R. Duffy, J. Li, and M. Medard, “Guessing noise, not code-words”, 2018 IEEE International Symposium on Information Theory (ISIT) 671 (2018) DOI
[6]
A. Barg, “At the Dawn of the Theory of Codes”, The Mathematical Intelligencer 15, 20 (1993) DOI
[7]
T. McCourt, I. R. Fiete, and I. L. Chuang, “Noisy dynamical systems evolve error correcting codes and modularity”, (2023) arXiv:2303.14448
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: ecc_finite

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

Cite as:

“Finite-dimensional error-correcting code (ECC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ecc_finite

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