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

Author: Kenneth Shum

Advisor: P. V. Kumar

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(N30). 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=q2.

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 logq(N))3 operations over GF(q2).  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 logq(N))3.

In practice we want to keep the size of the alphabet small, say q2=64 or q2=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