Goppa code

Traditionally, an AG-code is constructed from a non-singular projective curve X over a finite field ${\displaystyle \mathbb {F} _{q}}$ by using a number of fixed distinct ${\displaystyle \mathbb {F} _{q}}$-rational points on ${\displaystyle \mathbf {X} }$:

${\displaystyle {\mathcal {P}}:=\{P_{1},\ldots ,P_{n}\}\subset \mathbf {X} (\mathbb {F} _{q}).}$

Let ${\displaystyle G}$ be a divisor on X, with a support that consists of only rational points and that is disjoint from the ${\displaystyle P_{i}}$. Thus ${\displaystyle {\mathcal {P}}\cap \operatorname {supp} (G)=\varnothing }$

By the Riemann–Roch theorem, there is a unique finite-dimensional vector space, ${\displaystyle L(G)}$, with respect to the divisor ${\displaystyle G}$. The vector space is a subspace of the function field of X.

There are two main types of AG-codes that can be constructed using the above information.

The function code (or dual code) with respect to a curve X, a divisor ${\displaystyle G}$ and the set ${\displaystyle {\mathcal {P}}}$ is constructed as follows.

Let ${\displaystyle D=P_{1}+\cdots +P_{n}}$, be a divisor, with the ${\displaystyle P_{i}}$ defined as above. We usually denote a Goppa code by C(D,G). We now know all we need to define the Goppa code:

${\displaystyle C(D,G)=\left\{\left(f(P_{1}),\ldots ,f(P_{n})\right)\$ :\ f\in L(G)\right\}\subset \mathbb {F} _{q}^{n}}

For a fixed basis ${\displaystyle f_{1},\ldots ,f_{k}}$ for L(G) over ${\displaystyle \mathbb {F} _{q}}$, the corresponding Goppa code in ${\displaystyle \mathbb {F} _{q}^{n}}$ is spanned over ${\displaystyle \mathbb {F} _{q}}$ by the vectors

${\displaystyle \left(f_{i}(P_{1}),\ldots ,f_{i}(P_{n})\right)}$

Therefore,

${\displaystyle {\begin{bmatrix}f_{1}(P_{1})&\cdots &f_{1}(P_{n})\\\vdots &&\vdots \\f_{k}(P_{1})&\cdots &f_{k}(P_{n})\end{bmatrix}}}$

is a generator matrix for ${\displaystyle C(D,G).}$

Equivalently, it is defined as the image of

${\displaystyle {\begin{cases}\alpha :L(G)\to \mathbb {F} ^{n}\\f\mapsto (f(P_{1}),\ldots ,f(P_{n}))\end{cases}}}$

The following shows how the parameters of the code relate to classical parameters of linear systems of divisors D on C (cf. Riemann–Roch theorem for more). The notation ℓ(D) means the dimension of L(D).

Proposition A. The dimension of the Goppa code ${\displaystyle C(D,G)}$ is ${\displaystyle k=\ell (G)-\ell (G-D).}$

Proof. Since ${\displaystyle C(D,G)\cong L(G)/\ker(\alpha ),}$ we must show that

${\displaystyle \ker(\alpha )=L(G-D).}$

Let ${\displaystyle f\in \ker(\alpha )}$ then ${\displaystyle f(P_{1})=\cdots =f(P_{n})=0}$ so ${\displaystyle \operatorname {div} (f)>D}$. Thus, ${\displaystyle f\in L(G-D).}$ Conversely, suppose ${\displaystyle f\in L(G-D),}$ then ${\displaystyle \operatorname {div} (f)>D}$ since

${\displaystyle P_{i}<G,\quad i=1,\ldots ,n.}$

(G doesn't “fix” the problems with the ${\displaystyle -D}$, so f must do that instead.) It follows that ${\displaystyle f(P_{1})=\cdots =f(P_{n})=0.}$

Proposition B. The minimal distance between two code words is ${\displaystyle d\geqslant n-\deg(G).}$

Proof. Suppose the Hamming weight of ${\displaystyle \alpha (f)}$ is d. That means that for ${\displaystyle n-d}$ indices ${\displaystyle i_{1},\ldots ,i_{n-d}}$ we have${\displaystyle f(P_{i_{k}})=0}$ for ${\displaystyle k\in \{1,\ldots ,n-d\}.}$ Then ${\displaystyle f\in L(G-P_{i_{1}}-\cdots -P_{i_{n-d}})}$, and

${\displaystyle \operatorname {div} (f)+G-P_{i_{1}}-\cdots -P_{i_{n-d}}>0.}$

Taking degrees on both sides and noting that

${\displaystyle \deg(\operatorname {div} (f))=0,}$

we get

${\displaystyle \deg(G)-(n-d)\geqslant 0.}$

so

${\displaystyle d\geq n-\deg(G).}$

The residue code can be defined as the dual of the function code, or as the residue of some functions at the ${\displaystyle P_{i}}$'s.

• Key One Chung, Goppa Codes, December 2004, Department of Mathematics, Iowa State University.

• An undergraduate thesis on Algebraic Geometric Coding Theory
• Goppa Codes by Key One Chung