Fast GMD Decoding of Codes from Algebraic Curves

代数曲线代码的快速 GMD 解码

基本信息

批准号：
10650354
负责人：
SAKATA Shojiro
金额：
$ 1.28万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10650354/
关键词：
algebraic geometric codes codes from curves soft-decision decoding GMD (generalized minimum distance) decoding erasure-and-error decoding BMS (Berlekamp-Massey-Sakata) algorithm erasure-addition algorithm erasire-deletion algorithm RS符号

项目摘要

The objective of this research is to extend our previous method for fast decoding of one-point algebraic geometric codes (codes from algebraic curves or surfaces) to a fast GMD (generalized minimum distance) decoding of these codes. For fast GMD decoding of conventional algebraic codes including RS codes, several alternative methods have been given by other researchers. On the other hand, based on the recognition that algebraic geometric codes are a natural extention of conventional algebraic codes from one dimension to n dimension, we published some survey papers in volumes Grobner Bases and Applications and Codes, Curves and Signals as well as in journals Journal of IEICE and Mathematical Science. First, in this broad perspective, we published a paper on another version of fast GMD decoding of one-dimensional algebraic codes in IEICE Transactions. Next, we published a paper on fast erasure-and-error decoding method of one-point algebraic geometric codes jointly with American and Danish researchers in IEEE Transactions on Information Theory, the contents of which should be a core of fast GMD decoding method of these codes based on BMS algorithm. But, there still remains a difficult problem of how we can dispense with many redundant iterations of these erasure-and-error decoding procedures which are required by majority logic in determining the unknown syndrome values necessary for error correction up to the designed distance. To settle this problem, we have proposed a pair of GMD procedures, i.e. erasure-addition and erasure-deletion which can be combined with each other in many alternative ways during a fast GMD decoding process. At present we are trying to construct a kind of heuristic algorithm for fast GMD decoding method. Together with these research works we have published several relevant papers on fast decoding of algebraic geometric codes and its parallel implementation, etc.

这项研究的目的是将我们先前的方法扩展到快速解码的单点代数几何代码（从代数曲线或表面代码）到这些代码的快速GMD（广义最小距离）。对于包括RS代码在内的常规代数代码的快速GMD解码，其他研究人员已经提供了几种替代方法。另一方面，基于认识到代数几何代码是从一个维度到n维度的常规代数代码的自然扩展，我们发表了一些有关Grobner基础以及应用程序，曲线和信号的调查论文，以及IEICE和IEICE和数学科学期刊。首先，从这个广泛的角度来看，我们发表了一篇论文，介绍了IEICE交易中一维代数代码的另一种版本的快速GMD解码。接下来，我们发表了一篇关于与美国和丹麦研究人员在IEEE信息理论中共同与美国和丹麦研究人员共同的一点代数几何代码的快速擦除和错误解码方法的论文，其内容的内容应为基于BMS Algorithm的这些代码的快速GMD解码方法的核心。但是，仍然存在一个困难的问题，即我们如何在这些删除和错误解码过程的许多冗余迭代中分配，这是多数逻辑所必需的，这些逻辑在确定误差校正所需的未知综合征值时，直至设计距离。为了解决这个问题，我们提出了一对GMD程序，即擦除和删除删除，可以在快速的GMD解码过程中以多种替代方式相互结合。目前，我们正在尝试为快速GMD解码方法构建一种启发式算法。与这些研究作品一起，我们发表了几篇有关代数几何代码快速解码及其并行实施等的相关论文。