Efficient Decoding Method of Some Algebraic Geometry Codes

一些代数几何代码的高效解码方法

基本信息

批准号：
02650262
负责人：
SAKATA Shojiro
金额：
$ 1.22万
依托单位：
Toyohashi University of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1990
资助国家：
日本
起止时间：
1990 至 1991
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-02650262/
关键词：
Error-Correcting Codes Algebraic Geometry Codes Algebraic Curves Computational Complexity of Decoding Algorithm Fast Decoding Algorithm Two-Dimensional Berlekamp-Massey Algorithm 2D Syndrome Array Total Ordering over the 2D Integral Lattice

项目摘要

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.

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