Dept. of Electrical Engineering -- Systems,
University of Southern California
CA 90089-2565, USA.
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.