Goppa code

From Wikipedia, the free encyclopedia

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 V. D. Goppa. In particular cases, they can have interesting extremal properties.

Traditionally, an AG-code can be constructed from a non-singular projective curve X by using a number of fixed rational points

P₁, P₂, ..., P_n

of X defined over $\mathbb{F}_q$ , and let G be a divisor on X with a support that consists of only rational points and that is disjoint from the $P i$ 's. 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

1 Function Code
2 Residue Code
3 Applications
4 External links

[edit] Function Code

The function code (or dual code) with respect to a curve X, a divisor G and the $P i$ 's is constructed as follows.

For a fixed basis

f₁, f₂, ..., 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

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

Equivalently, it is defined as the image of

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

where f is defined by $f \longmapsto (f(P_1), \dots ,f(P_n))$ .

Let $D = P_1 + P_2 + \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 \geq n - \deg(G)$ .

Proof

Since

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

we must show that

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

Suppose $f \in \ker(\alpha)$ . Then $f(P_i)=0, i=1, \dots ,n$ , so $div(f) > D$ . Thus, $f \in L(G-D)$ . Conversely, suppose $f \in L(G-D)$ . Then

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_i)=0, i=1, \dots ,n$ .

To show that $d \geq n - \deg(G)$ , suppose the Hamming weight of $α(f)$ is d. That means that $f (P i) = 0$ for $n - d$ $P i$ s, say $P_{i_1}, \dots ,P_{i_{n-d}}$ . Then $f \in L(G-P_{i_1} - \dots - P_{i_{n-d}})$ , and