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

摘要

One of the main goals in coding theory is to construct codes with large relative minimum distance and code rate simultaneously. The work of Gilbert and Varshamov proves that for fixed alphabet size, there exists sequence of codes with increasing length N such that the code parameters asymptotically lie on the Gilbert-Varshamov (G-V) bound. Nevertheless the description of the code is not explicit. 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 Tsfasman, Vladut and Zink used Goppa's construction of algebraic geometric (AG) code, with modular curves with some asymptotically optimal properties. When the alphabet size larger than or equal to 49, the asymptotic performance of the AG codes can improve upon the G-V bound. However the definition of the modular curves is not explicit.; Another major step for efficient AG code construction is due to Garcia and Stichenoth 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 q2.; 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). We thus have 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, in low polynomial complexity O( N logq(N))3).; In practice we want to keep the size of the alphabet small, say q2 = 64 or q2 = 256. As the code length increases exponentially as we go from one curve to the next in the G-S family, only the first few codes obtained are of practical interest. The bases for the first three codes for any q are provided.