Goppa 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{𝔽}}_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.

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{𝔽}}_q$ by using a number of fixed distinct ${\mathbb{𝔽}}_q$-rational points on $\mathbf{𝐗}$:

${𝒫}:=\{P_1,\dots ,P_n\}\subset \mathbf{𝐗}({\mathbb{𝔽}}_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., ${𝒫}\cap \mathrm{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 ${𝒫}$ 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)=\{(f(P_1),\dots ,f(P_n)):f\in L(G)\}\subset {\mathbb{𝔽}}_q^n$

For a fixed basis $f_1,\dots ,f_k$ for L(G) over ${\mathbb{𝔽}}_q$, the corresponding Goppa code in ${\mathbb{𝔽}}_q^n$ is spanned over ${\mathbb{𝔽}}_q$ by the vectors

$(f_i(P_1),\dots ,f_i(P_n))$

Therefore,

$\left[\begin{array}{ccc}{f}_1(P_1)& \cdots & f_1(P_n)\\ ⋮& & ⋮\\ f_k(P_1)& \cdots & f_k(P_n)\end{array}\right]$

is a generator matrix for $C(D,G).$

Equivalently, it is defined as the image of

$\{\begin{array}{l}\alpha :L(G)\to {\mathbb{𝔽}}^n\\ f\mapsto (f(P_1),\dots ,f(P_n))\end{array}$

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 $\mathrm{div}(f)>D$. Thus, $f\in L(G-D).$ Conversely, suppose $f\in L(G-D),$ then $\mathrm{div}(f)>D$ since

$P_i<G,i=1,\dots ,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⩾n-\mathrm{deg}(G).$

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

$\mathrm{div}(f)+G-P_{i_1}-\cdots -P_{i_{n-d}}>0.$

Taking degrees on both sides and noting that

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

we get

$\mathrm{deg}(G)-(n-d)⩾0.$

so

$d\ge n-\mathrm{deg}(G).$

Residue code

The residue code can be defined as the dual of the function code, or as the residue of some functions at the $P_i$'s.

References

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

External links

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