algebraic geometry code

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;{{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}} however, this is no longer the standard term used in coding theory literature. This is due to the fact that Goppa codes are a distinct class of codes which were also constructed by Goppa in the early 1970s.{{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}}{{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}}{{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}}

These codes attracted interest in the coding theory community because they have the ability to surpass the Gilbert–Varshamov bound; at the time this was discovered, the Gilbert–Varshamov bound had not been broken in the 30 years since its discovery.{{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}} This was demonstrated by Tfasman, Vladut, and Zink in the same year as the code construction was published, in their paper "Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound".{{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}} The name of this paper may be one source of confusion affecting references to algebraic geometry codes throughout 1980s and 1990s coding theory literature.

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.

Algebraic geometry codes are a generalization of Reed–Solomon codes. Constructed by Irving Reed and Gustave Solomon in 1960, Reed–Solomon codes use univariate polynomials to form codewords, by evaluating polynomials of sufficiently small degree at the points in a finite field $\backslash mathbb\{F\}\_q$.{{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}}

Formally, Reed–Solomon codes are defined in the following way. Let $\backslash mathbb\{F\}\_q=\backslash \{\backslash alpha\_1,\; \backslash dots,\; \backslash alpha\_q\backslash \}$. Set positive integers $k\; \backslash leq\; n\; \backslash leq\; q$. Let

Goppa observed that $\backslash mathbb\{F\}\_q$ can be considered as an affine line, with corresponding projective line $\backslash mathbb\{P\}^1\_\{\backslash mathbb\{F\}\_q\}$. Then, the polynomials in

With this idea in mind, Goppa looked toward the Riemann–Roch theorem. The elements of a Riemann–Roch space are exactly those functions with pole order restricted below a given threshold,{{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}} with the restriction being encoded in the coefficients of a corresponding divisor. Evaluating those functions at the rational points on an algebraic curve $X$ over $\backslash mathbb\{F\}\_q$ (that is, the points in $\backslash mathbb\{F\}\_q^2$ on the curve $X$) 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 fields, the definitions of the codes are often given in the language of algebraic function fields over finite fields.{{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}} 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.

Formally, algebraic geometry codes are defined in the following way. Let $F\; /\; \backslash mathbb\{F\}\_q$ be an algebraic function field, $D\; =\; P\_1\; +\; \backslash dots\; +\; P\_n$ be the sum of $n$ distinct places of $F\; /\; \backslash mathbb\{F\}\_q$ of degree one, and $G$ be a divisor with disjoint support from $D$. The algebraic geometry code $C\_\{\backslash mathcal\{L\}\}(D,G)$ associated with divisors $D$ and $G$ is defined as $$C\_\{\backslash mathcal\{L\}\}(D,G)\; :=\; \backslash lbrace\; (f(P\_1),\backslash dots,f(P\_n))\; :\; f\; \backslash in\; \backslash mathcal\{L\}(G)\; \backslash rbrace\; \backslash subseteq\; \backslash mathbb\{F\}\_q^n.$$More information on these codes may be found in both introductory texts as well as advanced texts on coding theory.{{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}}

One can see that

$RS(q,n,k)\; =\; \backslash mathcal\{C\}\_\backslash mathcal\{L\}(D,(k-1)P\_\backslash infty)$

where $P\_\backslash infty$ is the point at infinity on the projective line $\backslash mathbb\{P\}^1\_\{\backslash mathbb\{F\}\_q\}$ and $D\; =\; P\_1\; +\; \backslash dots\; +\; P\_q$ is the sum of the other $\backslash mathbb\{F\}\_q$-rational points.

The Hermitian curve is given by the equation$$x^\{q+1\}\; =\; y^q\; +\; y$$considered over the field $\backslash mathbb\{F\}\_\{q^2\}$. This curve is of particular importance because it meets the Hasse–Weil bound with equality, and thus has the maximal number of affine points over $\backslash mathbb\{F\}\_\{q^2\}$.{{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}} With respect to algebraic geometry codes, this means that Hermitian codes are long relative to the alphabet they are defined over.{{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}}

The Riemann–Roch space of the Hermitian function field is given in the following statement. For the Hermitian function field $\backslash mathbb\{F\}\_\{q^2\}(x,y)$ given by $x^\{q+1\}\; =\; y^q\; +\; y$ and for $m\; \backslash in\; \backslash mathbb\{Z\}^+$, the Riemann–Roch space $\backslash mathcal\{L\}(mP\_\backslash infty)$ is$$\backslash mathcal\{L\}(mP\_\backslash infty)\; =\; \backslash left\backslash langle\; x^a\; y^b\; :\; 0\; \backslash leq\; b\; \backslash leq\; q-1,\; aq\; +\; b(q+1)\; \backslash leq\; m\; \backslash right\backslash rangle\; ,$$where $P\_\backslash infty$ is the point at infinity on $\backslash mathcal\{H\}\_q(\backslash mathbb\{F\}\_\{q^2\})$.

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

Let $P\_\backslash infty$ be the point at infinity on $\backslash mathcal\{H\}\_q(\backslash mathbb\{F\}\_\{q^2\})$, and $$D\; =\; P\_1\; +\; \backslash cdots\; +\; P\_n$$be a divisor supported by the $n\; :=\; q^3$ distinct $\backslash mathbb\{F\}\_\{q^2\}$-rational points on $\backslash mathcal\{H\}\_q$ other than $P\_\backslash infty$.

The one-point Hermitian code $C(D,mP\_\backslash infty)$ is

$C(D,mP\_\backslash infty)\; :=\; \backslash left\backslash lbrace\; (f(P\_1),\backslash dots,f(P\_n))\; :\; f\; \backslash in\; \backslash mathcal\{L\}(mP\_\backslash infty)\; \backslash right\backslash rbrace\; \backslash subseteq\; \backslash mathbb\{F\}\_\{q^2\}^n.$

{{Reflist}}

Category:Coding theory

Category:Algebraic curves

Category:Finite fields

Category:Articles containing proofs