Fast Decodicng Method of Any One-Point Algebraic-Geometric Codes up to the Feng-Rao Bound

本文建立了在Feng-Rao设计距离内，对任意代数曲线上定义的任意一点代数几何码的快速译码算法。对于码长n，我们的方法解码在厄米平面曲线和任何高维代数曲线上定义的单点AG码的计算复杂度分别为O阶（n^<7/>）和小于O阶（n^3），而基本的Feng-Rao方法的复杂度为O阶（n^3）。在所有已知的单点AG码译码方法中，out方法在效率方面是最好的。这些结果部分发表在1994年的IEEE国际期刊上。计算机协会。通知。理论，发表于1994年IEEE国际会议。机车间传递信息。理论，以及其他一些会议。部分内容发表在有限域及其应用1995年第1卷上，主要部分将发表在即将出版的IEEE Trans特刊上。通知。理论。我们理论的细节发表在《子弹》杂志上。更多的选择。通讯。, 1995年Vol.8。在进行上述理论工作的同时，我们进行了一些计算机实验。我们为我们的解码方法实现了一个软件系统（c程序），并将其应用于定义在厄米平面曲线及其三维扩展上的两种代码，我们研究了我们的方法的实际效率。对多种随机误差模式的仿真结果表明，有限域上的算法数和实际计算时间都有与理论计算复杂度相当相似的趋势，这为我们的理论提供了额外的证据，并为今后的实际应用提供了指导。此外，在某些情况下，我们的方法可以超过设计的解码距离。另一方面，我们发表了一篇论文，其中包含对Bullet中更广泛的AG代码类的一般回顾。Jap.Soc.Ind.Appl.Math。, 1994年第1辑。此外，我们已经着手研究并行处理器架构的硬件实现我们的方法和快速错误和擦除解码作为本研究的扩展。该研究的一些结果在aaec -11会议和1995年IEEE国际会议上发表。理论，在其他一些会议上。少

We have established a fast decoding algorithm of any one-point algebraic-geometric (AG) code, which is defined on an arbitrary algebraic curve, up to the Feng-Rao designed distance. For the codelength n, our method has computational complexity of order O (n^<7/>) and of order less than O (n^3) to decode a one-point AG code defined on a Hermitian plane curve and on any algebraic curve of higher dimension, respectively, while the fundamental Feng-Rao method has complexity of order O (n^3). In regard to efficiency, out method is the best among all the known decoding methods of any one-point AG code. These results were presented in part at the 1994 IEEE Int. Symp. Inform. Theory, at the 1994 IEEE Int. Worshop Inform. Theory, and at some other conferences. The contents were published partially in Finite Fields and Their Applications, Vol.1,1995, and the main part will appear in the forthcoming Special Issue of IEEE Trans. Inform. Theory. The details of our theory were published in Bullet. U … More nv.Elect. -Comm., Vol.8,1995. In parallel to the above theoretical work, we made some computer experiment. We implemented a software system (C-program) for our decoding method, and by applying it to two kinds of codes defined on a Hermitian plane curve and on its three-dimensional extension, we investigated the actual efficiency of our method. As a result of simulation on many random error-patterns, it was shown that both the number of arithmetics over the finite field and the actual computing time have a tendency quite similar to the theoretical computational complexity, which gives an additional evidence to our theory and a guideline for practical use in future. Furthermore, it was made sure that our method can decode beyond the designed distance in some cases. On the other hand, we published a paper containing a general review on a broader class of AG codes in Bullet. Jap.Soc.Ind.Appl.Math., Vol.4,1994. In addition, we have proceeded to investigate parallel processor architecture for hardware implementation of our method and fast error-and-erasure decoding as extensions of the present research. Some results of the research were presented at the AAECC-11 Conference and at the 1995 IEEE Int.Symp.Inform.Theory, and in some other conferences. Less