Efficient List Decoding of Codes from Algebraic Curves

点击翻译按钮获取中文摘要

The objective of this research is to develop an efficient algorithm for list decoding of algebraic geometric (AG) codes or codes from algebraic curves. An algebraic list decoding method has been introduced recently by M. Sudan. It consists of two major procedures, where the first is to find an interpolation polynomial having a set of zeros specified by the pair of the received word and the information positions, and the second is to factorize the interpolation polynomial. This Sudan algorithm (Sudan-1) has been improved to another version (Sudan-2) by Guruswami and Sudan, where Sudan-1 can work only for coding rate less than 1/3, but the latter even for larger coding rate. As an outcome of our research, we have given efficient methods of finding the interpolation polynomials for both Sudan-1 and Sudan-2 list decoding algorithms of RS codes, and published a paper (in Japanese) treating these subjects in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Scien … More ces, Vol.J83-A, No.11, 2000. Therein, based on the observation that the problem of finding the interpolation polynomial is reduced to finding the Grobner basis of a polynomial ideal having the specified zeros, we have given the efficient interpolation methods by applying the BMS algorithm which we invented before for fast realization of the conventional bounded-distance decoding of AG codes. Furthermore, we have made clear that the BMS algorithm can be adapted naturally to fast Sudan-1 interpolation for AG codes, the result of which we presented in the IEEE 2000 International Symposium on Information Theory, in Sorrento, Italy, June 25-30, 2000. On the other hand, it was difficult to adapt the BMS algorithm to fast Sudan-2 interpolation for AG codes, because this problem, do1 not have such a nice structure as the previous. But, we have given a solution to it by using a different formulation based on the defining arrays of a polynomial ideal. We presented the result in the international ' conference AAECC-14, Melbourne, Australia, November 26-30, 2001, and published in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: Proc. AAECC-14 (Eds. S. Boztas, I.E. Shparlinski), Springer Verlag, 2001. Less