yawiki.org entry for Goppa code

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

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 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_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

    Goppa code
        Function Code
        Residue Code
        Applications

top

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_q

, the corresponding Goppa code in

mathbb_q^n

is spanned over

mathbb_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^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

mathrm(f) > D

. Thus,

f in
L(G-D)

. Conversely, suppose

f in L(G-D)

. Then

$mathrm(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

alpha(f)

is d. That means that

f(P_i)=0

for

n-d

P_i

s, say

P_, dots ,P_

. Then

f in L(G-P_ - dots
- P_)

, and

$mathrm(f)+G-P_ - dots - P_> 0$ .

Taking degrees on both sides and noting that

$deg(mathrm(f))=0$ ,

we get

$deg(G)-(n-d) geq 0$ ,

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

top

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.

top

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

$choose$

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

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Goppa code". link