# Error-correcting code (ECC)

## Description

A code is a subset of a set or alphabet, 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}\).

## Protection

A code corrects errors associated with a noise channel if it is possible to recover any codeword after its coordinates have been changed after going through the channel. More technically, an error-correcting code \((u,\mathcal{E})\) is an encoder function \(u:[1\cdots K]\to[1\cdots N]\) with a set of correctable errors \(E:[1\cdots N]\to [1\cdots M]\) with the following property: there exists a decoder function \(d:[1\cdots M]\to [1\cdots K]\) such that for all \(E\in\cal{E}\) and states \(x\in[1\cdots K]\), \(d(E(e(x)))=x\) [1].

## Decoding

Capacity-achieving Guessing Random Additive Noise Decoding (GRAND) [2].

## Notes

The modern theory of error-correcting codes is rooted in the foundational work of C. Shannon [3], but error-correcting codes have been used prior to that work [4].

## Parent

## Children

- Binary code
- Distributed-storage code
- Galois-field \(q\)-ary code
- Generalized concatenated code
- Group-based code
- Identifiable parent property (IPP) code
- Lattice-based code — Error-correcting codes are defined for a finite alphabet, so only finite lattice-based codes are children.
- Linear code
- Locally testable code (LTC)
- Matrix-based code
- Parallel concatenated code
- Quasi-cyclic code
- Random code
- Ring code
- Spherical code
- Weighed-covering code

## References

- [1]
- D. Gottesman. Surviving as a quantum computer in a classical world
- [2]
- K. R. Duffy, J. Li, and M. Medard, “Capacity-Achieving Guessing Random Additive Noise Decoding”, IEEE Transactions on Information Theory 65, 4023 (2019). DOI; 1802.07010
- [3]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948). DOI
- [4]
- A. Barg, “At the Dawn of the Theory of Codes”, The Mathematical Intelligencer 15, 20 (1993). DOI

## Page edit log

- Victor V. Albert (2022-03-22) — most recent
- Victor V. Albert (2021-11-24)

## Zoo code information

## 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.