# Algebraic geometry code

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Algebraic_geometry_code
> Markdown URL: https://mediated.wiki/source/Algebraic_geometry_code.md
> Source: https://en.wikipedia.org/wiki/Algebraic_geometry_code
> Source revision: 1349698797
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Mathematical linear code}}
'''Algebraic geometry codes''', often abbreviated AG codes, are a type of [linear code](/source/linear_code) that generalize [Reed–Solomon codes](/source/Reed%E2%80%93Solomon_error_correction). The Russian mathematician [V. D. Goppa](/source/Valery_Goppa) constructed these codes for the first time in 1982.<ref>{{Cite journal |last=Goppa |first=Valerii Denisovich |author-link=Valery Goppa |date=1982 |title=Algebraico-geometric codes |url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=1646&option_lang=eng |journal=Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya |volume=46 |issue=4 |pages=726–781 |via=Russian Academy of Sciences, Steklov Mathematical Institute of Russian}}</ref>

== History ==
The name of these codes has evolved since the publication of Goppa's paper describing them. Historically these codes have also been referred to as geometric Goppa codes;<ref name=":0">{{Cite journal |last=Stichtenoth |first=Henning |date=1988 |title=A note on Hermitian codes over GF(q^2) |url=https://ieeexplore.ieee.org/abstract/document/21267 |journal=IEEE Transactions on Information Theory |volume=34 |issue=5 |pages=1345–1348 |via=IEEE}}</ref> however, this is no longer the standard term used in [coding theory](/source/coding_theory) literature. This is due to the fact that [Goppa codes](/source/Binary_Goppa_code) are a distinct class of codes which were also constructed by Goppa in the early 1970s.<ref>{{Cite journal |last=Goppa |first=Valery Denisovich |author-link=Valery Goppa |date=1970 |title=A new class of linear error-correcting codes |url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1748&option_lang=eng |journal=Probl. Inf. Transm. |volume=6 |pages=300–304}}</ref><ref>{{Cite journal |last=Goppa |first=Valerii Denisovich |author-link=Valery Goppa |date=1972 |title=Codes Constructed on the Base of (L,g)-Codes |url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=791&option_lang=eng |journal=Problemy Peredachi Informatsii |volume=8 |issue=2 |pages=107–109 |via=Russian Academy of Sciences, Branch of Informatics, Computer Equipment and}}</ref><ref>{{Cite journal |last=Berlekamp |first=Elwyn |author-link=Elwyn Berlekamp |date=1973 |title=Goppa codes |url=https://ieeexplore.ieee.org/abstract/document/1055088 |journal=IEEE Transactions on Information Theory |volume=19 |issue=5 |pages=590–592 |via=IEEE}}</ref>

These codes attracted interest in the coding theory community because they have the ability to surpass the [Gilbert–Varshamov bound](/source/Gilbert%E2%80%93Varshamov_bound); at the time this was discovered, the Gilbert–Varshamov bound had not been broken in the 30 years since its discovery.<ref name=":1">{{Cite book |last=Walker |first=Judy L. |title=Codes and Curves |publisher=American Mathematical Society |year=2000 |isbn=0-8218-2628-X |location= |pages=15}}</ref> This was demonstrated by Tfasman, Vladut, and Zink in the same year as the code construction was published, in their paper "[Modular curves](/source/Modular_curve), Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound".<ref>{{Cite journal |last=Tsfasman |first=Michael |last2=Vladut |first2=Serge |last3=Zink |first3=Thomas |author-link3=Thomas Zink |date=1982 |title=Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound |url=https://onlinelibrary.wiley.com/doi/abs/10.1002/mana.19821090103 |journal=Mathematische Nachrichten}}</ref> The name of this paper may be one source of confusion affecting references to algebraic geometry codes throughout 1980s and 1990s coding theory literature.

==Construction==
In this section the construction of algebraic geometry codes is described. The section starts with the ideas behind Reed–Solomon codes, which are used to motivate the construction of algebraic geometry codes.

=== Reed–Solomon codes ===
Algebraic geometry codes are a generalization of [Reed–Solomon codes](/source/Reed%E2%80%93Solomon_error_correction). Constructed by [Irving Reed](/source/Irving_S._Reed) and [Gustave Solomon](/source/Gustave_Solomon) in 1960, Reed–Solomon codes use [univariate](/source/univariate) polynomials to form codewords, by evaluating polynomials of sufficiently small degree at the points in a [finite field](/source/finite_field) <math>\mathbb{F}_q</math>.<ref>{{Cite journal |last=Reed |first=Irving |author-link=Irving S. Reed |last2=Solomon |first2=Gustave |author-link2=Gustave Solomon |date=1960 |title=Polynomial codes over certain finite fields |url=https://epubs.siam.org/doi/abs/10.1137/0108018?journalCode=smjmap.1 |journal=Journal of the Society for Industrial and Applied Mathematics |volume=8 |issue=2 |pages=300–304 |via=SIAM}}</ref>

Formally, Reed–Solomon codes are defined in the following way. Let <math>\mathbb{F}_q=\{\alpha_1, \dots, \alpha_q\}</math>. Set positive integers <math>k \leq n \leq q</math>. Let <math display="block">\mathbb{F}_{q}[x]_{<k} := \left\{ f \in \mathbb{F}_q[x]: \deg f < k \right\}</math>The Reed–Solomon code <math>RS(q,n,k)</math> is the evaluation code<math display="block">RS(q,n,k) = \left\{ \left( f(\alpha_1), f(\alpha_2), \dots, f(\alpha_n) \right) : f \in \mathbb{F}_{q}[x]_{<k} \right\} \subseteq \mathbb{F}_q^{n}.</math>

=== Codes from algebraic curves ===
Goppa observed that <math>\mathbb{F}_q</math> can be considered as an affine line, with corresponding [projective line](/source/projective_line) <math>\mathbb{P}^1_{\mathbb{F}_q}</math>. Then, the polynomials in <math>\mathbb{F}_{q}[x]_{<k}</math> (i.e. the polynomials of degree less than <math>k</math> over <math>\mathbb{F}_q</math>) can be thought of as polynomials with [pole](/source/Zeros_and_poles) allowance no more than <math>k</math> at the [point at infinity](/source/point_at_infinity) in <math>\mathbb{P}^1_{\mathbb{F}_q}</math>.<ref name=":1" />

With this idea in mind, Goppa looked toward the [Riemann–Roch theorem](/source/Riemann%E2%80%93Roch_theorem). The elements of a Riemann–Roch space are exactly those functions with pole order restricted below a given threshold,<ref name=":2">{{Cite journal |last=Hoholdt |first=Tom |last2=van Lint |first2=Jacobus |author-link2=J. H. van Lint |last3=Pellikaan |first3=Ruud |date=1998 |title=Algebraic geometry codes |url=https://www.researchgate.net/profile/R-Pellikaan/publication/293123965_Algebraic_geometry_of_codes_handbook_of_coding_theory/links/56c59cc708ae7fd4625baa21/Algebraic-geometry-of-codes-handbook-of-coding-theory.pdf |journal=Handbook of coding theory |volume=1 |issue=Part 1 |pages=871–961 |via=Elsevier Amsterdam}}</ref> with the restriction being encoded in the coefficients of a corresponding [divisor](/source/Divisor_(algebraic_geometry)). Evaluating those functions at the [rational point](/source/rational_point)s on an algebraic curve <math>X</math> over <math>\mathbb{F}_q</math> (that is, the points in <math>\mathbb{F}_q^2</math> on the curve <math>X</math>) gives a code in the same sense as the Reed-Solomon construction.

However, because the parameters of algebraic geometry codes are connected to [algebraic function field](/source/algebraic_function_field)s, the definitions of the codes are often given in the language of algebraic function fields over finite fields.<ref name=":3">{{Cite book |last=Stichtenoth |first=Henning |title=Algebraic function fields and codes |publisher=Springer Science & Business Media |year=2009 |isbn=978-3-540-76878-4 |edition=2nd |pages=45–65}}</ref> Nevertheless, it is important to remember the connection to algebraic curves, as this provides a more geometrically intuitive method of thinking about AG codes as extensions of Reed-Solomon codes.<ref name=":2" />

Formally, algebraic geometry codes are defined in the following way.<ref name=":3" /> Let <math>F / \mathbb{F}_q</math> be an algebraic function field, <math>D = P_1 + \dots + P_n</math> be the sum of <math>n</math> distinct places of <math>F / \mathbb{F}_q</math> of degree one, and <math>G</math> be a divisor with disjoint [support](/source/Support_(mathematics)) from <math>D</math>. The algebraic geometry code <math>C_{\mathcal{L}}(D,G)</math> associated with divisors <math>D</math> and <math>G</math> is defined as <math display="block">C_{\mathcal{L}}(D,G) := \lbrace (f(P_1),\dots,f(P_n)) : f \in \mathcal{L}(G) \rbrace \subseteq \mathbb{F}_q^n.</math>More information on these codes may be found in both introductory texts<ref name=":1" /> as well as advanced texts on coding theory.<ref name=":3" /><ref>{{Cite book |last=van Lint |first=Jacobus |title=Introduction to coding theory |publisher=Springer |year=1999 |isbn=978-3-642-63653-0 |edition=3rd |pages=148–166}}</ref>

== Decoding ==
Some algebraic geometry codes can be decoded using algorithms based on the Berlekamp–Massey–Sakata algorithm. Shojiro Sakata introduced this algorithm as an extension of the [Berlekamp–Massey algorithm](/source/Berlekamp%E2%80%93Massey_algorithm) to multidimensional arrays.<ref>{{Cite journal |last=Sakata |first=Shojiro |date=February 1990 |title=Extension of the Berlekamp-Massey algorithm to N dimensions |journal=Information and Computation |volume=84 |issue=2 |pages=207–239 |doi=10.1016/0890-5401(90)90039-K}}</ref> In particular, one-point algebraic geometry codes can be decoded efficiently using the Berlekamp–Massey–Sakata algorithm, and later variants have been developed for multipoint codes from algebraic curves.<ref>{{Cite journal |last1=Sakata |first1=Shojiro |last2=Fujisawa |first2=Masaya |date=April 2014 |title=Fast decoding of multipoint codes from algebraic curves |journal=IEEE Transactions on Information Theory |volume=60 |issue=4 |pages=2054–2064 |doi=10.1109/TIT.2014.2300473}}</ref>

== Examples ==

=== Reed-Solomon codes ===
One can see that

<math>RS(q,n,k) = \mathcal{C}_\mathcal{L}(D,(k-1)P_\infty)</math>

where <math>P_\infty</math> is the point at infinity on the projective line <math>\mathbb{P}^1_{\mathbb{F}_q}</math> and <math>D = P_1 + \dots + P_q</math> is the sum of the other <math>\mathbb{F}_q</math>-rational points.

=== One-point Hermitian codes ===
The Hermitian curve is given by the equation<math display="block">x^{q+1} = y^q + y</math>considered over the field <math>\mathbb{F}_{q^2}</math>.<ref name=":0" /> This curve is of particular importance because it meets the [Hasse–Weil bound](/source/Hasse's_theorem_on_elliptic_curves) with equality, and thus has the maximal number of affine points over <math>\mathbb{F}_{q^2}</math>.<ref>{{Cite journal |last=Garcia |first=Arnoldo |author-link=Arnaldo Garcia |last2=Viana |first2=Paulo |date=1986 |title=Weierstrass points on certain non-classical curves |url=https://link.springer.com/article/10.1007/BF01200462 |journal=Archiv der Mathematik |volume=46 |pages=315–322 |via=Springer}}</ref> With respect to algebraic geometry codes, this means that Hermitian codes are long relative to the alphabet they are defined over.<ref>{{Cite journal |last=Tiersma |first=H.J. |date=1987 |title=Remarks on codes from Hermitian curves |url=https://ieeexplore.ieee.org/abstract/document/1057327 |journal=IEEE Transactions on Information Theory |volume=33 |issue=4 |pages=605–609 |via=IEEE}}</ref>

The Riemann–Roch space of the Hermitian [function field](/source/Algebraic_function_field) is given in the following statement.<ref name=":0" /> For the [Hermitian function](/source/Hermitian_function) field <math>\mathbb{F}_{q^2}(x,y)</math> given by <math>x^{q+1} = y^q + y</math> and for <math>m \in \mathbb{Z}^+</math>, the Riemann–Roch space <math>\mathcal{L}(mP_\infty)</math> is<math display="block">\mathcal{L}(mP_\infty) = \left\langle x^a y^b : 0 \leq b \leq q-1, aq + b(q+1) \leq m \right\rangle ,</math>where <math>P_\infty</math> is the point at infinity on <math>\mathcal{H}_q(\mathbb{F}_{q^2})</math>.

With that, the one-point Hermitian code can be defined in the following way. Let <math>\mathcal{H}_q</math> be the Hermitian curve defined over <math>\mathbb{F}_{q^2}</math>.

Let <math>P_\infty</math> be the point at infinity on <math>\mathcal{H}_q(\mathbb{F}_{q^2})</math>, and <math display="block">D = P_1 + \cdots + P_n</math>be a divisor supported by the <math>n := q^3</math> distinct <math>\mathbb{F}_{q^2}</math>-rational points on <math>\mathcal{H}_q</math> other than <math>P_\infty</math>.

The one-point Hermitian code <math>C(D,mP_\infty)</math> is

<math>C(D,mP_\infty) := \left\lbrace (f(P_1),\dots,f(P_n)) : f \in \mathcal{L}(mP_\infty) \right\rbrace \subseteq \mathbb{F}_{q^2}^n.</math>

== References ==
{{Reflist}}

Category:Coding theory
Category:Algebraic curves
Category:Finite fields
Category:Articles containing proofs

---
Adapted from the Wikipedia article [Algebraic geometry code](https://en.wikipedia.org/wiki/Algebraic_geometry_code) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Algebraic_geometry_code?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.