nLab error correcting code

Contents

Contents

Idea

In coding theory, an error correcting code is a means to encode data in a way that is robust against errors (noise).

Very broadly, for LL a finite set playing the role of a space of states that is to be saved/communicated/analyzed, an error correcting code for LL is an injection LPL \overset{\;\;\;}{\hookrightarrow} P into a larger set. The idea is that noise/errors move the image of LL within PP, but if PP is large enough and the embedding chosen well enough, then a sufficiently small number of errors stays within a small neighbourhood of LL in PP that allows to retract back to LL.

The simplest example is the repetition code, where the inclusion is the diagonal on the nn-fold Cartesian product

L diag PL××Lnfactors (,,). \array{ L & \overset{diag}{\hookrightarrow} & P \coloneqq \underset{n \; factors}{\underbrace{L \times \cdots \times L}} \\ \ell &\mapsto& (\ell, \cdots, \ell) } \,.

This code “protects against n/21n/2-1 errors” in an evident sense.

Much attention in coding theory is instead on the special class of linear codes, where LL and PP carry the structure of vector spaces (necessarily over a finite field if they are finite sets of relevance in practice) and where the inclusion LPL \hookrightarrow P is a linear map.

Examples

References

General

See also the references at coding theory and linear code.

An observation on classical codes preconceiving aspects of holographic tensor network quantum error correcting codes:

Relation to 2d CFT

Construction of chiral 2d SCFTs from error-correcting codes:

On their elliptic genera

  • Kohki Kawabata, Shinichiro Yahagi, Elliptic genera from classical error-correcting codes [arXiv:2308.12592]

Last revised on December 28, 2023 at 12:12:19. See the history of this page for a list of all contributions to it.