Algebraic-geometry (AG) code

Algebraic-geometry (AG) code[1][2][3]

Description

Binary or \(q\)-ary code constructed from an algebraic curve of some genus over a finite field via the evaluation construction, the residue construction, or more general constructions that yield nonlinear codes. Linear AG codes from the first two constructions are also called geometric Goppa codes.

In alternative conventions (not used here), AG codes are restricted to be linear and/or include evaluation codes defined using algebraic varieties more general than curves.

Rate

Several sequences of linear AG codes beat the Gilbert-Varshamov bound and/or are asymptotically good [4][5] (see Ref. [6] for details). The rate of any linear AG code satisfies \begin{align} \frac{k}{n} \geq 1 - \frac{d}{n} - \frac{1}{\sqrt{q}-1}~, \tag*{(1)}\end{align} which comes from the Drinfeld-Vladut bound [7]. Nonlinear AG codes can outperform this bound.

Notes

See book by Goppa [8].

Parent

Galois-field \(q\)-ary code

Children

Cousins

Maximum distance separable (MDS) code — Near MDS \([n,k,d]_{GF(p^m)}\) AG codes exist when \(n,p,m\) satisfy certain relations according to the Tsfasman-Vladut bound [9][10].
Evaluation code — Evaluation codes on varieties can also be considered AG codes since they use algebraic geometry in quantifying code bounds. However, early AG constructions all used only one-dimensional varieties, i.e., algebraic curves.

References

[1]: V. D. Goppa, “Codes Associated with Divisors”, Probl. Peredachi Inf., 13:1 (1977), 33–39; Problems Inform. Transmission, 13:1 (1977), 22–27
[2]: V. D. Goppa, “Codes on algebraic curves”, Dokl. Akad. Nauk SSSR, 259:6 (1981), 1289–1290
[3]: V. D. Goppa, “Algebraico-geometric codes”, Izv. Akad. Nauk SSSR Ser. Mat., 46:4 (1982), 762–781; Izv. Math., 21:1 (1983), 75–91
[4]: A. Garcia and H. Stichtenoth, “A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound”, Inventiones Mathematicae 121, 211 (1995) DOI
[5]: A. Garcia and H. Stichtenoth, “On the Asymptotic Behaviour of Some Towers of Function Fields over Finite Fields”, Journal of Number Theory 61, 248 (1996) DOI
[6]: T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[7]: S. G. Vlăduţ, V. G. Drinfeld, “Number of points of an algebraic curve”, Funktsional. Anal. i Prilozhen., 17:1 (1983), 68–69; Funct. Anal. Appl., 17:1 (1983), 53–54
[8]: V. D. Goppa, Geometry and Codes (Springer Netherlands, 1988) DOI
[9]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[10]: I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI

Page edit log

Victor V. Albert (2022-08-09) — most recent
Victor V. Albert (2022-03-21)

Cite as:

“Algebraic-geometry (AG) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ag

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/ag/ag.yml.