Coding Theory and Algebraic Geometry: an Interplay
One in a series of snapshots of applications of discrete
mathematics to other parts of mathematics.
J. W. P. Hirschfeld
University of Sussex
United Kingdom
The Context
In 1981, Goppa derived a class of linear codes from algebraic curves
over finite fields which (a) are quite general as codes, (b) have
parameters circumscribed by the Riemann-Roch theorem, and (c) have
asymptotic properties which improve the classical Gilbert-Varshamov
bound. The discovery of these codes also gave renewed stimulus to
investigations on the number of rational points on an algebraic curve
for a particular genus as well as to asymptotic values of the ratio of
the number of points to the genus. Manin showed that for small fields
coding theory methods give better results for this ratio than the
Hasse-Weil theorem.
The Problem
The three most important parameters of a linear code over the finite
field 
are the length n which gives the speed of transmission, the
dimension k which gives the number of words in the code, and the
minimum distance d which gives the number of errors that can be
corrected. ``Good'' codes have large information rate 
and
relative distance 
. The relation between R and 
as n gets large is given by the Gilbert-Varshamov bound. Good codes
can be constructed from an algebraic curve of genus g, and
particular examples show that the G-V bound is not best possible. This
brings to the fore the problem of determining the limit 
of
for a sequence of curves. Here coding bounds give better values
than methods of algebraic geometry.
The Construction
Let 
be an algebraic curve defined over 
. Let 
be an ordered set of rational point points
of 
. Let 
with 
for
, be the associated divisor. Let 
with
be an 
-divisor such that 
for
all i,j. Let 
be the space of
functions associated to E; that is, 
consists of functions
which have no pole of order greater than 
at 
for all j. Then the
evaluation map 
at 
is given by
and its image
is an
algebraic geometry code.
The Hasse-Weil theorem says that 
and it is of considerable interest to find curves
satisfying the upper bound. Although it follows from this bound that
, it was shown
by Drinfeld and Vladut that 
; it is also known
that equality holds for square q.
Further Research
What still has to be done is
- to investigate the behaviour of these
codes on different types of curves (the codes are well understood for
curves of genus 0 and 1);
- to find curves with large
numbers of points;
- to find the value of
for different
sequences of curves and, in particular, the value of 
; -
most importantly, to find more efficient
decoding procedures.
For More Information
The IEEE Transactions in Information Theory is the journal where
most articles on this topic can be found.
- J.W.P. Hirschfeld, Review of `` Algebraic Curves over Finite
Fields by O. Moreno, Cambridge University Press, Cambridge, 1991'',
in Bull. Amer. Math. Soc. 27 (1992), 327-332.
- H. Stichtenoth, Algebraic Function Fields and Codes,
Springer-Verlag, Berlin, 1993.
- M.A. Tsfasman and S.G. Vladut, Algebraic-Geometric Codes,
Kluwer, Dordrecht, 1991.
Thu Sep 28 09:58:04 CDT 1995