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

给出了定义在任意代数曲线上的任意一点代数几何(AG)码的快速译码算法，译码距离可达冯-饶设计距离。对于码长n，我们的方法对定义在厄米平面曲线和任何高维代数曲线上的单点AG码分别具有O(n^&lt；7/&gt；)和小于O(n^3)阶的计算复杂度，而基本的冯-Rao方法具有O(n^3)阶的计算复杂度。就效率而言，OUT方法是所有已知的任何一点AG码的译码方法中最好的。这些结果部分地在1994年的IEEE国际会议上公布。交响乐。通知我。理论，在1994年IEEE Int.Worshop通知。理论，以及在其他一些会议上。这些内容部分发表在《有限域及其应用》1995年第1卷上，主要内容将出现在即将出版的IEEE学报特刊上。通知我。理论上。我们理论的细节发表在《子弹》杂志上。U…更多的选择。-《通信》，第8卷，1995年。在进行上述理论工作的同时，我们进行了一些计算机实验。我们为我们的译码方法实现了一个软件系统(C程序)，并将它应用于定义在厄米平面曲线上的两种码及其三维扩张上，考察了我们方法的实际效率。对许多随机误差模式的模拟结果表明，无论是有限域上的运算次数还是实际计算时间都有与理论计算复杂度非常接近的趋势，这为我们的理论提供了进一步的证据，并为以后的实际应用提供了指导。此外，在某些情况下，我们的方法还可以实现超出设计距离的译码。另一方面，我们发表了一篇论文，对Bullet中更广泛类别的AG代码进行了一般性综述。《日本社会应用数学》，1994年第4卷。此外，我们还研究了用于硬件实现我们的方法的并行处理器体系结构和作为本研究的扩展的快速纠错和擦除译码。这项研究的一些结果在AAECC-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