A low complexity algorithm for the construction of algebraic geometric codes better than the Gilbert-Varshamov bound

Abstract

Tsfasman, Vladut, and Zink (1982) showed the existence of curves such that the algebraic geometric (AG) codes constructed on these curves using Goppa's algorithm have performance exceeding that of the Gilbert-Varshamov (G-V) bound. Garcia and Stichtenoth (1996) (G-S) building on ideas of Feng and Pellikaan, showed that the curves of Tsfasman et al. could be replaced by curves having an explicit and simple description. We present here the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of G-S. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF(q/sup 2/), is upper bounded by [nlog/sub q/(n)]/sup 3/ where n is the code length and q/sup 2/ is the size of the code symbol alphabet. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the binary G-V bound.