###
A Low-Complexity Algorithm for the Construction of Algebraic Geometric
Codes better than the Gilbert-Varshamov Bound

Date: Dec 2000.
Communication
Science Institute,

Dept.
of Electrical Engineering -- Systems,

University of
Southern California

CA 90089-2565, USA.

####
ABSTRACT

The quest for algebraic construction of error correcting code has been
outstanding for coding theorists ever since the work of Shannon. For a
code of length *N*, with dimension *k* and minimum distance *d*
over a alphabet of fixed size *Q*, its performance is evaluated in
terms of the parameters $\delta$ and *R*, where $\delta$ is the relative
minimum distance distance *d/N* and *R* is the code rate *k/N*.
One of the main goals in coding theory is to construct codes with large
relative minimum distance and code ratesimultaneously, while keeping the
size of alphabet small. The work of Gilbert and Varshamov proves that there
exist sequences of codes with increasing length such that the parameters
$\delta$ and *R* asymptotically lie on the Gilbert-Varshamov (G-V)
bound. Nevertheless the description of the code is not explicit. It was
later shown that the class of alternant codes and concatenated codes also
meet the G-V bound. Again, no explicit description of them (in terms of
generator matrix or parity-check matrix) is handy. Question as to whether
one can improve the G-V bound and whether an efficient algorithm for constructing
codes meeting the G-V bound exists, remained open.
A breakthrough occurred in the early 80's when Goppa discovered a link
between algebraic geometry and coding theory. Using algebraic curves over
finite fields, Goppa defined a large family of codes, known as algebraic
geometric (AG) codes. For alphabet size larger than or equal to 49, the
asymptotic performance of the AG codes can improve upon the G-V bound.
This improvement was later realized by Tsfasman, Vladut and Zink (T-V-Z)
in 1982 by showing the existence of modular curves with some asymptotically
optimal properties. However the definition of the modular curves is not
explicit. The algorithm for constructing AG codes based on modular curves
by T-V-Z has complexity *O(N*^{30}). The complexity is of
course too high for practical purpose.

Another major step for efficient AG code construction is due to Garcia
and Stichtenoth in 1995--96. With input from Feng and Pallikaan, they succeeded
in writing down explicit equations describing two families (the G-S families)
of asymptotically optimal algebraic curves defined over finite field of
size *Q=q*^{2}.

In this dissertation, an algorithm using the power series approach is
presented for constructing generator matrices of AG codes from the second
family of algebraic curves studied by Garcia and Stichtenoth. We estimate
the complexity of the algorithm for even *q* larger than or equal
to 4. The complexity is less than *((N log*_{q}(N))^{3}
operations over *GF(q*^{2}). The complexities for other
values of *q* is differ by a constant. We thus have, for the first
time, a low-complexity algorithm constructing codes better than the G-V
bound. By concatenating the AG codes with binary codes of short length,
we can construct binary codes with good asymptotic parameters that exceed
the Zyablov bound, with complexity *(N log*_{q}(N))^{3}.

In practice we want to keep the size of the alphabet small, say *q*^{2}=64
or *q*^{2}=256, in order to ease the decoding process. As
the length of code increases exponentially as we go from one curve to the
next in the G-S family, for tolerable decoding delay, only the first few
codes obtained are of practical interest. The bases for the first three
codes from the second G-S family, for any *q* that is a power of prime,
are provided in the last chapter.

The dissertation in Postscript format is available at

http://commsci.usc.edu/~kshum/thesis.ps