ALGEBRAIC-GEOMETRIC CODES AND MULTIDIMENSIONAL CYCLIC CODES - A UNIFIED THEORY AND ALGORITHMS FOR DECODING USING GROBNER BASES

In this paper, it is proved that any algebraic-geometric code can be e xpressed as a cross section of an extended multidimensional cyclic cod e. Both algebraic-geometric codes and multidimensional cyclic codes ar e described by a unified theory of linear block codes defined over poi nt sets: algebraic-geometric codes are defined over the points of an a lgebraic curve, and an m-dinensional cyclic code is defined over the p oints in m-dimensional space, The power of the unified theory is in it s description of decoding techniques using Grobner bases, In order to fit an algebraic-geometric code into this theory, a change of coordina tes must be applied to the curve over which the code is defined so tha t the curve is in special position, For curves in special position, al l computations can be performed with polynomials, rather than rational functions, and this also makes it possible to take advantage of the t heory of Grobner bases, Next, a transform is defined for algebraic-geo metric codes which generalizes the discrete Fourier transform, The tra nsform is also related to a Grobner basis, and is useful in setting up the decoding problem. In the decoding problem, a key step is finding a Grobner basis for an error locator ideal, For algebraic-geometric co des, multidimensional cyclic codes, and indeed, any cross section of a n extended multidimensional cyclic code, Sakata's algorithm can be use d to find linear recursion relations which hold on the syndrome array, In this general context, we give a self-contained and simplified pres entation of Sakata's algorithm, and present a general framework for de coding algorithms for this family of codes, in which the use of Sakata 's algorithm is supplemented by a procedure for extending the syndrome array.