Effective Construction of Algebraic Geometry Codes

Goppa's construction of linear codes using algebraic geometry, the so-called geometric Goppa or AG codes, was a major breakthrough in the history of coding theory. In particular, it was the first (and only) construction leading to a family of codes with parameters above the Gilbert-Varshamov bound [41].

There exist several (essentially equivalent) ways to construct AG codes starting from a smooth projective curve ${\widetilde{C}}$ defined over a finite field $\mathbf{F}$. Mainly, we should like to mention the L-, resp. the $\Omega$-construction.

Given rational points $Q_1,\dots,Q_n\in {\widetilde{C}}$ and a rational divisor $G$ on ${\widetilde{C}}$ having disjoint support with the divisor $D=Q_1+\ldots+Q_n$, the AG code $C_L(G,D,{\widetilde{C}})$, resp. $C_{\Omega}(G,D,{\widetilde{C}})$, is the image of the $\mathbf{F}$-linear map

$$_D : \,\mathcal{L}(G)\longrightarrow \mathbf{F}^n, \;\quad f\longmapsto \bigl(f(Q_1),\dots,f(Q_n)\bigr)\,,\,$$

$$_D : \Omega(G\!\!\:-\!\!\:D)\longrightarrow \mathbf{F}^n, \quad \omega \longmapsto \bigl( _{Q_1}\!(\omega),\dots, _{Q_n}\!(\omega)\bigr)\,.$$

In practice, there are two main difficulties when looking for an effective method to compute the generator matrices of such codes: Given a plane (singular) model $C$ of ${\widetilde{C}}$, how to compute the places of $C$ and how to compute a basis for the linear system $\mathcal{L}(G)$ (cf. below), resp. for the vector space of rational one-forms

$$\Omega(G\!\!\:-\!\!\:D)=\bigl\{\omega\in \Omega(X)^\ast\, \big\vert\,(\omega)+G-D\geq 0\bigr\}\cup \{0\}\,.$$

One possible solution, making use of blowing-up theory (to compute the places of $C$) and of the (classical) Brill-Noether algorithm (for the computation of a basis of $\mathcal{L}(G)$) is presented in [28,19]. In the following, we should like to point to the modified approach of Campillo and Farrán [3], using Hamburger-Noether expansions instead of blowing-up theory, and to present in some detail the resulting algorithm as implemented in the computer algebra system SINGULAR [17].