Code de Goppa | Goppa-kode

In mathematics, a Goppa code is a general type of linear code constructed by using an algebraic curve X over a finite field $\backslash mathbb\{F\}\_q$. Such codes were introduced by V. D. Goppa. In particular cases, they can have interesting extremal properties.

In detail, assume that X is non-singular, that a number of points

P₁, P₂, ..., P_n

are fixed among the points of X defined over $\backslash mathbb\{F\}\_q$, and that G is a divisor on X, also defined over F. There is a finite-dimensional subspace L(G) of the function field of X, consisting of the rational functions f on X with zeroes and poles subject to G. This means that G, which is a formal sum of points of X over the algebraic closure of $\backslash mathbb\{F\}\_q$, bounds the divisor made up of the zeroes and poles of f, counted with appropriate multiplicity.

Then, for a fixed basis

f₁, f₂, ..., f_k

for L(G) over $\backslash mathbb\{F\}\_q$, the corresponding Goppa code in $\backslash mathbb\{F\}\_q^n$ is spanned over $\backslash mathbb\{F\}\_q$ by the vectors

(f_i(P₁), f_i(P₂), ..., f_i(P_n)).

Equivalently, it is defined as the image of

$\backslash alpha\; :\; L(G)\; \backslash longrightarrow\; \backslash mathbb\{F\}^n$,

where f is defined by $f\; \backslash longmapsto\; (f(P\_1),\; \backslash dots\; ,f(P\_n))$.

Let $D\; =\; P\_1\; +\; P\_2\; +\; \backslash cdots\; +\; P\_n$ be a divisor, with the $P\_i$ defined as above. We usually denote a Goppa code by C(D,G).

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 l(D) means the dimension of L(D).

Proposition The dimension of the Goppa code C(D,G) is

$k\; =\; l(G)\; -\; l(G-D)$,

and the minimal distance between two code words is

$d\; \backslash geq\; n\; -\; \backslash deg(G)$.

Proof

Since

$C(D,G)\; \backslash cong\; L(G)/\backslash ker(\backslash alpha),$

we must show that

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

Suppose $f\; \backslash in\; \backslash ker(\backslash alpha)$. Then $f(P\_i)=0,\; i=1,\; \backslash dots\; ,n$, so $\backslash mathrm\{div\}(f)\; >\; D$. Thus, $f\; \backslash in\; L(G-D)$. Conversely, suppose $f\; \backslash in\; L(G-D)$. Then

$\backslash mathrm\{div\}(f)>\; D$

since

.

(G doesn't “fix” the problems with the $-D$, so f must do that instead.) It follows that

$f(P\_i)=0,\; i=1,\; \backslash dots\; ,n$.

To show that $d\; \backslash geq\; n\; -\; \backslash deg(G)$, suppose the Hamming weight of $\backslash alpha(f)$ is d. That means that $f(P\_i)=0$ for $n-d$ $P\_i$s, say $P\_\{i\_1\},\; \backslash dots\; ,P\_\{i\_\{n-d\}\}$. Then $f\; \backslash in\; L(G-P\_\{i\_1\}\; -\; \backslash dots\; -\; P\_\{i\_\{n-d\}\})$, and

$\backslash mathrm\{div\}(f)+G-P\_\{i\_1\}\; -\; \backslash dots\; -\; P\_\{i\_\{n-d\}\}>\; 0$.

Taking degrees on both sides and noting that

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

we get

$\backslash deg(G)-(n-d)\; \backslash geq\; 0$,

so

$d\; \backslash geq\; n\; -\; \backslash deg(G)$. Q.E.D.

Applications

In cryptography, Goppa codes are used in the McEliece cryptosystem.

In general, Goppa codes are considered 'good' linear codes, in that they permit the correction of

$\{n^k\}\; \backslash choose\; \{\backslash log\_2\; n\}$

errors. Also their decoding is easy, using the Euclidean algorithm and Berlekamp-Massey algorithm, in particular.

Coding theoryAlgebraic curves