Efficient List Decoding of Codes from Algebraic Curves

代数曲线代码的高效列表解码

• 批准号: 12650368
• 负责人: SAKATA Shojiro
• 金额: $ 1.22万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12650368/
• 关键词: list decoding; algebraic geometry codes; codes from curves; RS codes; factorization; interpolation polynomial; Grobner basis; BMS algorithm; BMSアルゴリズム; BMS アルゴリズム

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

本研究的目的是开发一种高效的代数几何码或代数曲线码的列表译码算法。最近，M. Sudan提出了一种代数列表解码方法。它包括两个主要过程，第一个是找到一个插值多项式，该插值多项式具有由接收到的字对和信息位置指定的一组零，第二个是对插值多项式进行因式分解。该算法（Sudan-1）由Guruswami和Sudan改进为另一个版本（Sudan-2），其中Sudan-1只能在编码率低于1/3的情况下工作，而后者甚至可以在更大的编码率下工作。作为我们的研究成果，我们给出了寻找RS码的苏丹-1和苏丹-2列表解码算法的插值多项式的有效方法，并在IEICE Transactions on Fundamentals of Electronics， Communications and Computer science, vol . 83- a, No.11, 2000中发表了一篇关于这些主题的论文（日文）。其中，基于寻找插值多项式的问题被简化为寻找具有指定零的多项式理想的Grobner基的观察，我们给出了利用我们之前发明的BMS算法快速实现传统AG码的有界距离译码的有效插值方法。此外，我们已经清楚地表明，BMS算法可以自然地适应于AG码的快速苏丹1插值，我们在2000年6月25日至30日在意大利索伦托举行的IEEE 2000国际信息理论研讨会上发表了这一结果。另一方面，由于BMS算法不像先前的算法那样具有良好的结构，因此难以适应AG码的快速苏丹-2插值。但是，我们已经给出了它的解通过一个不同的公式基于多项式理想矩阵的定义。我们在2001年11月26-30日于澳大利亚墨尔本举行的AAECC-14国际会议上发表了这一结果，并发表在《应用代数、代数算法和纠错码：Proc. AAECC-14》（主编）上。S. Boztas， I.E. Shparlinski)， bbb出版社，2001。少

项目成果

M.Fujisawa, S.Sakata: "A fast erasure deletion generalized minimum distance decoding for one-point algebraic-geometry codes"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E84-A・10. 2376-2382 (2001)

M.Fujisawa、S.Sakata：“单点代数几何代码的快速擦除删除广义最小距离解码”IEICE 电子、通信和计算机科学基础知识汇刊 E84-A·10 (2001)。

沼上幸夫, 藤澤匡哉, 阪田省二郎: "Reed-Solomon符号のリスト復号のための高速補間法"電子情報通信学会論文誌(A). J83-A・11. 1309-1317 (2000)

Yukio Numakami、Masaya Fujisawa、Shojiro Sakata：“Reed-Solomon 码列表解码的高速插值方法”，电子信息通信工程师学会会刊 (A) J83-A・11（2000 年）。 ）

沼上 幸夫, 藤澤 匡哉, 阪田 省二郎: "Reed-Solomon符号のリスト復号のための高速補間法"電子情報通信学会論文誌(A). J83-A・11. 1309-1317 (2000)

Yukio Numakami、Masaya Fujisawa、Shojiro Sakata：“Reed-Solomon 码列表解码的高速插值方法”，电子信息通信工程师学会会刊 (A) J83-A・11（2000 年）。 ）

S.Sakata: "On fast interpolation method for Guruswami-Sudan list decoding of one-point algebraic-geometry codes"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes : Proc. AAECC-14A. (Eds. S.Boztas, I.E.Shparlinski). 172-181 (2001)

S.Sakata：“关于单点代数几何代码的 Guruswami-Sudan 列表解码的快速插值方法”应用代数、代数算法和纠错代码：Proc。

S.Sakata, Y.Numakami: "A fast interpolation method for list decoding of RS and algebraic-geometric codes"Proc. ISIT-2000 (Eds.A.Ephremides, T.Ericson). 479 (2000)

S.Sakata，Y.Numakami：“RS 和代数几何码列表解码的快速插值方法”Proc。