Efficient Decoding Method of Some Algebraic Geometry Codes

近年来，利用代数几何和俄罗斯编码理论家V.D.的思想，发现了一系列纠错性能好、编码速率高的纠错码。哥帕这些码是由有限域上的代数曲线导出的一类代数码，称为代数几何码。欧洲和日本的一些研究人员最近提出了一些代数几何码的译码方法。这些解码方法中的大多数的计算复杂度是n^3或更大的数量级，其中n是码长。另一方面，一些研究者应用我们的二维Berlekamp-Massey算法给出了一种快速算法。我们提出的2DBerlekamp-Massey算法解决了（1D）Berlekamp-Massey算法所处理的问题的2D版本，即能够产生给定的有限2D阵列的2D线性反馈移位寄存器的综合。这两种算法在原理上具有相同的计算复杂度n^2的数量级，其中n是在这种情况下给定的一维或二维数组的大小。在研究的过程中，我们通过阐明算法的一些新的方面和给出算法的一些新的版本，揭示了我们的算法在其他几种代数几何码译码中的更多应用，表明我们的方法可以有效地应用于其他编码理论家刚刚发现的几种新的代数几何码的译码。我们的解码方法的计算复杂度小于以前的方法。此外，我们还给出了我们算法的几个推广，以便将它们应用于其它一些尚未构造但有可能被发明的码的译码。

Recently a sequence of error-correcting codes that have good error-correction performance and high coding rate have been discovered using algebraic geometry and ideas of a russian coding theorist V. D. Goppa. These codes are a class of algebraic codes which are derived from algebraic curves over finite fields and are called algebraic geometry codes. Several investigators in Europe as well as in Japna have proposed decoding methods for some algebraic geometry codes quite recently. The computational complexties in most of these decoding methods are of the order of n^3 or more, where n is the code length. On the other hand, some investigators gave a fast algorithm by applying our 2D Berlekamp-Massey algorithm. The 2D Berlekamp-Massey algorithm which we proposed before solves th e 2D version of the problem treated by the (1D) Berlekamp-Massey algorithm, that is synthesis of 2D linear feedback shift register capable of generating a given finite 2D array. Both these algorithms in principle have the same computational complexity of the order of n^2, where n is the size of the given 1D or 2D array in this case. In the progression of this research we have revealed some more applications of our algorithm to decode several other algebraic geometry codes by making clear some novel aspects of the algorithm and by giving some new versions of it. We have shown that our methods can be applied to decode efficiently several new algebraic geometry codes which just have been discovered by other coding theorists. The computational complexities of our decoding methods are less than those of the previous methods. Furthermore, we have given several extensions of our algorithm to apply them to decode some other codes which have not been constructed yet but have the possibility of being invented.