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

冯饶界任意单点代数几何码的快速译码方法

• 批准号: 06650412
• 负责人: SAKATA Shojiro
• 金额: $ 0.96万
• 依托单位: University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 1995
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-06650412/
• 关键词: algebraic-geometric (AG) codes; codes defined on algebraic curves; error-correcting codes having good performance; fast decoding algorithm; Sakata algorithm; finite field; algebraic algorithms; multidimensional Berlekamp-Massey algorithm

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

我们建立了一种对任意单点代数几何（AG）码的快速解码算法，该算法在任意代数曲线上定义，直到Feng-Rao设计的距离。对于码长 n，我们的方法分别具有 O (n^<7/>) 阶和小于 O (n^3) 阶的计算复杂度来解码在 Hermitian 平面曲线和任何高维代数曲线上定义的单点 AG 码，而基本的 Feng-Rao 方法的复杂度为 O (n^3) 阶。就效率而言，out方法是所有已知的单点AG码解码方法中最好的。这些结果部分在 1994 年 IEEE Int. 会议上发表。症状。通知。理论，1994 年 IEEE Int。研讨会通知。理论以及其他一些会议。部分内容发表于Finite Fields and Their Applications, Vol.1,1995，主要部分将发表在即将出版的IEEE Trans特刊上。通知。理论。我们理论的细节发表在《Bullet》杂志上。 U … 更多 nv.Elect。 -《通讯》，第 8 卷，1995 年。在进行上述理论工作的同时，我们做了一些计算机实验。我们为我们的解码方法实现了一个软件系统（C 程序），并将其应用于埃尔米特平面曲线及其三维扩展上定义的两种代码，我们研究了该方法的实际效率。通过对多种随机误差模式的模拟结果表明，有限域上的运算次数和实际计算时间都与理论计算复杂度非常相似，这为我们的理论提供了额外的证据，并为将来的实际应用提供了指导。此外，还确保我们的方法在某些情况下可以解码超出设计的距离。另一方面，我们在 Bullet 中发表了一篇论文，其中包含对更广泛的 AG 代码类别的一般评论。日本社会工业应用数学，第 4 卷，1994 年。此外，我们还继续研究并行处理器架构，用于我们的方法的硬件实现以及快速错误和擦除解码，作为当前研究的扩展。该研究的一些结果已在 AAECC-11 会议和 1995 年 IEEE Int.Symp.Inform.Theory 以及其他一些会议上发表。较少的

项目成果

阪田省二郎: "代数幾何符号について" 応用数理. 4. 46-64 (1994)

Shojiro Sakata：“关于代数几何代码”《应用数学》4. 46-64 (1994)。

S.Sakata,et al.: "Generalized Berlekamp-Massey Decoding of Algebraic Geometry Codes up to Half the Feng-Rao Bound" Proc.1994 IEEE Int.Symp.Inform.Theory. 153 (1994)

S.Sakata 等人：“代数几何代码的广义 Berlekamp-Massey 解码高达 Feng-Rao Bound 的一半”Proc.1994 IEEE Int.Symp.Inform.Theory。

S.Sakata: "Generalized Berlekamp-Massey Decoding of Algebraic Geometry Codes up to Half the Feng-Rao Bound" IEEE Transactions on Information Theory. 41. 1762-1768 (1995)

S.Sakata：“代数几何代码的广义 Berlekamp-Massey 解码高达 Feng-Rao Bound 的一半”IEEE 信息论汇刊。

S.Sakata: "nD Shift Register Synthesis on Convex cones and Cylinders and Fast Decoding of General One-Point AG Codes" Proc.1994 IEEE Int.Workshop Inform.Theory. 87-88 (1994)

S.Sakata：“凸锥体和圆柱体上的 nD 移位寄存器综合以及通用单点 AG 代码的快速解码”Proc.1994 IEEE Int.Workshop Inform.Theory。

S.Sakata: "A Fast Decoding Method of AG Codes from Miura-Kamiya Curves C_<ab> up to Half the Feng-Rao Bound" Finite Fields and Their Applications. 1. 83-101 (1995)

S.Sakata：“从 Miura-Kamiya 曲线 C_<ab> 到 Feng-Rao 界限一半的 AG 代码的快速解码方法”有限域及其应用。