[ Pobierz całość w formacie PDF ]
of any f " L(D), and, in fact, f(Pi) " Fq for any f " L(D) and any
Pi " P.
Definition 6.3. Let X, P, and D be as above. Then the algebraic
geometric code associated to X, P, and D is
C(X, P, D) := {(f(P1), . . . , f(Pn)) | f " L(D)} ‚" Fn.
q
In other words, the algebraic geometric code C(X, P, D) is the
image of the evaluation map
: L(D) ’! Fn
q
f ’! (f(P1), . . . , f(Pn))
6. Algebraic Geometry Codes 39
Since L(D) is a vector space over Fq and the evaluation map
is a linear transformation, we see that C(X, P, D) is a linear code.
Further, its length is obviously n = #P. What about the dimension?
Clearly, it s at most dim L(D), and it s exactly dim L(D) if and only
if is one-to-one. This is true if and only if the kernel of is trivial
(Exercise A.23). So suppose (f) = 0. Then f(P1) = · · · = f(Pn) =
0, so the coefficient of each Pi in the divisor div(f) is at least 1. Since
no Pi is in suppD, we have that div(f) + D - P1 - · · · - Pn e" 0, which
means that f " L(D - P1 - · · · - Pn). If we add a hypothesis that
deg D
its associated space of rational functions is {0} by Exercise 5.13. This
means f = 0, so dim C = dim L(D). In fact, we have the following
theorem:
Theorem 6.4. Let X be a nonsingular, projective plane curve of
genus g, defined over the field Fq. Let P ‚" X(Fq) be a set of n
distinct Fq-rational points on X, and let D be a divisor on X sat-
isfying 2g - 2
C := C(X, P, D) is linear of length n, dimension k := deg D + 1 - g,
and minimum distance d, where d e" n - deg D.
Proof. We ve already shown that C is linear of length n and dimen-
sion dim L(D), since deg D
exactly the statement of the Riemann-Roch Theorem, since deg D >
2g - 2. To get the lower bound on the minimum distance of C,
we use an argument similar to the one we used to compute k. Let
(f) = (f(P1), . . . , f(Pn)) " C be a codeword of minimum nonzero
weight d. Then exactly d coordinates of (f) are nonzero, so without
loss of generality, we may assume f(Pd+1) = · · · = f(Pn) = 0. As
before, this means that the divisor div(f) + D - Pd+1 - · · · - Pn is
effective, and by Exercise 5.13, the divisor D - Pd+1 - · · · - Pn must
have nonnegative degree. In other words, we have deg D-(n-d) e" 0,
or d e" n - deg D as desired.
Let C = C(X, P, D) be an algebraic geometric code and let
f1, f2, . . . , fk be a basis for the vector space L(D) over Fq. Under
the conditions of the theorem, we know that dim C = k, and so we
know that (f1), (f2), . . . , (fk) is a basis for C. This means that
40 6. Algebraic Geometry Codes
the matrix
ëø öø
f1(P1) f1(P2) . . . f1(Pn)
ìøf2(P1) f2(P2) . . . f2(Pn)÷ø
ìø ÷ø
ìø
. . .
.. . ÷ø
. .
íø øø
.
. . .
fk(P1) fk(P2) . . . fk(Pn)
is a generator matrix for C.
Exercise 6.5. Let E be the projective plane curve defined by the
2
equation Y Z + Y Z2 = X3 + XZ2 + Z3 over the field F2. (This is the
same curve we studied in Exercise 5.15.) Let P = E(F8) \ {P "}. Let
C be the algebraic geometric code C = C(E, P, 5P "), defined over
F8.
a) What do the theoretical results say about the parameters of C?
b) Find a generator matrix for C.
c) Determine the exact parameters of C.
Exercise 6.6. Recall that an MDS code is a code which meets the
Singleton Bound (Theorem 2.1). Show that every algebraic geometric
code defined from the projective line is MDS.
Exercise 6.7. (adapted from [S]) Let ± = (±1, . . . , ±n), where the
±i are distinct elements of Fq, let v = (v1, . . . , vn) where the vi are
nonzero (not necessarily distinct) elements of Fq, and let k be a fixed
integer, 1 d" k d" n. The Generalized Reed-Solomon code is defined to
be
GRSk(±, v) := {v1f(±1), . . . , vnf(±n) | f " Lk-1}.
Here, as before, Lk-1 denotes the k-dimensional Fq-vector space of
polynomials over Fq of degree at most k - 1.
a) Find values for ± and v so that GRSk(±, v) = RS(k, q).
b) Show that there is a polynomial u = u(z) " Fq[z] satisfying
u(±i) = vi for i = 1, . . . , n.
c) Find div(u).
d) Show that there is a set P ‚" P1(Fq) and a divisor D on P1 such
that GRSk(±, v) = C(P1, P, D).
Chapter 7
Good Codes from
Algebraic Geometry
Now that we understand Goppa s construction of algebraic geomet-
ric codes, let s investigate the result of Tsfasman, Vladut, and Zink.
Recall that in 1982, just after Goppa ([Go]) announced his construc-
tion in 1977, Tsfasman, Vladut, and Zink ([TVZ]) proved that there
was a sequence of algebraic geometric codes which had parameters
[ Pobierz całość w formacie PDF ]