Algebraic-geometry (AG) code

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

Description

Binary or \(q\)-ary code or subcode 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 GV bound and/or are asymptotically good [4–6] (see Ref. [7] 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 [8]. Nonlinear AG codes can outperform this bound.

Notes

See book by Goppa [9].

Parent

Galois-field \(q\)-ary code

Children

Cousins

Maximum distance separable (MDS) code — Near MDS \([n,k,d]_{p^m}\) AG codes exist when \(n,p,m\) satisfy certain relations according to the Tsfasman-Vladut bound [10–12].
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.
Tsfasman-Vladut-Zink (TVZ) code — TVZ codes exceed the GV bound [4].
Qubit CSS code — Algebraic geometry codes can be plugged into the CSS construction to yield asymptotically good quantum codes [13,14]. However, such codes are not QLDPC.
EA Galois-qudit stabilizer code — Certain AG codes can be used to construct EA Galois-qudit stabilizer codes [15].

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]: M. A. Tsfasman, S. G. Vlădutx, and Th. Zink, “Modular curves, Shimura curves, and Goppa codes, better than Varshamov‐Gilbert bound”, Mathematische Nachrichten 109, 21 (1982) DOI
[5]: 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
[6]: 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
[7]: T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[8]: 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
[9]: V. D. Goppa, Geometry and Codes (Springer Netherlands, 1988) DOI
[10]: M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[11]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[12]: I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
[13]: A. Ashikhmin, S. Litsyn, and M. Tsfasman, “Asymptotically good quantum codes”, Physical Review A 63, (2001) arXiv:quant-ph/0006061 DOI
[14]: R. Matsumoto, “Improvement of Ashikhmin-Litsyn-Tsfasman bound for quantum codes”, IEEE Transactions on Information Theory 48, 2122 (2002) arXiv:quant-ph/0107129 DOI
[15]: L. Sok, “On linear codes with one-dimensional Euclidean hull and their applications to EAQECCs”, (2021) arXiv:2101.06461

Page edit log

Alexander Barg (2024-07-23) — most recent
Victor V. Albert (2024-07-23)
Victor V. Albert (2022-08-09)
Victor V. Albert (2022-03-21)

Cite as:

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

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