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
F
q
. Such codes were introduced by Valerii Denisovich Goppa. In particular cases, they can have interesting extremal properties. They should not be confused with Binary Goppa codes that are used, for instance, in the McEliece cryptosystem.
Traditionally, an AG-code is constructed from a non-singular projective curve X over a finite field
F
q
by using a number of fixed distinct
F
q
-rational points on
X
:
P
:=
{
P
1
,
⋯
,
P
n
}
⊂
X
(
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
. Thus
P
∩
supp
(
G
)
=
∅
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.
The function code (or dual code) with respect to a curve X, a divisor
G
and the set
P
is constructed as follows.
Let
D
=
P
1
+
⋯
+
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
)
,
⋯
,
f
(
P
n
)
)
:
f
∈
L
(
G
)
}
⊂
F
q
n
For a fixed basis
f
1
,
⋯
,
f
k
for L(G) over
F
q
, the corresponding Goppa code in
F
q
n
is spanned over
F
q
by the vectors
(
f
i
(
P
1
)
,
⋯
,
f
i
(
P
n
)
)
Therefore,
[
f
1
(
P
1
)
⋯
f
1
(
P
n
)
⋯
f
k
(
P
1
)
⋯
f
k
(
P
n
)
]
is a generator matrix for
C
(
D
,
G
)
.
Equivalently, it is defined as the image of
{
α
:
L
(
G
)
→
F
n
f
↦
(
f
(
P
1
)
,
⋯
,
f
(
P
n
)
)
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 A. The dimension of the Goppa code
C
(
D
,
G
)
is
k
=
l
(
G
)
−
l
(
G
−
D
)
.
Proof. Since
C
(
D
,
G
)
≅
L
(
G
)
/
ker
(
α
)
,
we must show that
ker
(
α
)
=
L
(
G
−
D
)
.
Let
f
∈
ker
(
α
)
then
f
(
P
1
)
=
⋯
=
f
(
P
n
)
=
0
so
d
i
v
(
f
)
>
D
. Thus,
f
∈
L
(
G
−
D
)
.
Conversely, suppose
f
∈
L
(
G
−
D
)
,
then
d
i
v
(
f
)
>
D
since
P
i
<
G
,
i
=
1
,
…
,
n
.
(G doesn't “fix” the problems with the
−
D
, so f must do that instead.) It follows that
f
(
P
1
)
=
⋯
=
f
(
P
n
)
=
0.
Proposition B. The minimal distance between two code words is
d
⩾
n
−
deg
(
G
)
.
Proof. Suppose the Hamming weight of
α
(
f
)
is d. That means that for
n
−
d
indices
i
1
,
⋯
,
i
n
−
d
we have
f
(
P
i
k
)
=
0
for
k
∈
{
1
,
⋯
,
n
−
d
}
.
Then
f
∈
L
(
G
−
P
i
1
−
⋯
−
P
i
n
−
d
)
, and
d
i
v
(
f
)
+
G
−
P
i
1
−
⋯
−
P
i
n
−
d
>
0
.
Taking degrees on both sides and noting that
deg
(
d
i
v
(
f
)
)
=
0
,
we get
deg
(
G
)
−
(
n
−
d
)
⩾
0.
so
d
≥
n
−
deg
(
G
)
.
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.
