Algebraic geometry code

In mathematics, an algebraic geometric code (AG-code), otherwise known as a Goppa code, is a general type of linear code constructed by using an algebraic curve $X$ over a finite field $\mathbb {F} _{q}$ . Such codes were introduced by Valerii Denisovich Goppa. In particular cases, they can have interesting extremal properties, making them useful for a variety of error detection and correction problems.^[1]

They should not be confused with binary Goppa codes that are used, for instance, in the McEliece cryptosystem.

Construction

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

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

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

By the Riemann–Roch theorem, there is a unique finite-dimensional vector space, $L(G)$ , with respect to the divisor $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.

Function code

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

Let $D=P_{1}+\cdots +P_{n}$ , be a divisor, with the $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:

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 $f_{1},\ldots ,f_{k}$ for L(G) over $\mathbb {F} _{q}$ , the corresponding Goppa code in $\mathbb {F} _{q}^{n}$ is spanned over $\mathbb {F} _{q}$ by the vectors

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

Therefore,

{\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 $C(D,G).$

Equivalently, it is defined as the image of

{\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

C(D,G)

is

k=\ell (G)-\ell (G-D).

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

\ker(\alpha )=L(G-D).

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

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

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

Proposition B. The minimal distance between two code words is

d\geqslant n-\deg(G).

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