Fast Parallel Implementation of Bounded-Distance Decoding of Codes from Argebraic Curves with Systolic Array Achitecture

脉动数组结构的代数曲线有界距离译码的快速并行实现

• 批准号: 08650424
• 负责人: SAKATA Shojiro
• 金额: $ 1.22万
• 依托单位: University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08650424/
• 关键词: algebraic geometric codes; codes from curves; algebraic algorithm; Berlekamp-Massey-Sakata algorithm; parallel decoding method; architecuture for parallel processing; systolic array; シストリックアレイ; 代数幾何学符号; 多次元Berlekamp-Masseyアスゴリズム

Before we gave a fast decoding algorithm for one-point algebraic geometric codes up to the designed distance, which can be implemented in serial form on conventional computers of von Neumann type. Now we have etablished a method for implementing the decoding algorithm in parallel form with a sytolic array architecture for the parallel processing. Parts of our results were presented in several international conferences : (1) Our bsic idea for paralleliztion of the original fast decoding algorithm at the conference IMAX-ACA,Line, Austria, in July, 1996 ; (2) A vector version of the fast algorithm which is the kernel of our parallel decoding method at the conference AAECC-12, Toulouse, France, June, 1997 ; published in Lecture Notes in Computer Science (LNSC), Vol.1255 (Eds.Mora et al.), Springer, 1997 ; (3) A method for efficient scheduling of the whole cells (processors) in implementing our parallel decoding algorithm with a systolic array architecture at the IEEE International Symposiu … More m on Information Theory, Ulm, Germany, July, 1997. For the codelength n, our method has time complexity of order O (n), which is better than O (n^2) obtained by [R.Kotter, A fast parallel implementation of a BM algoritm for AG codes, On Algebraic Decoding of AG Godes and Cyclic Codes, Dissertation, Linkoping Univ., (section) 3,1996]. In addition, we have proceeded to investigate several relevant themes such as a soft decision decoding method for correcting both erasures and errors, which can be parallelized (Part is contained in the paper published in LNSC-1255). A fast generalized minimum distance (GMD) decoding method was presented in the Allerton Conference on Communication, Control and Computation, Illinois, USA,September, 1997, and a lecture on the Berlekamp-Massey-Sakata algorithm was given at the special conference BlahutFest just before the Allerton Conference. A tutorial paper on Grobner bases and coding theory is published in Grobner Bases and Applications (Eds.Buchberger et al.), Cambridge Univ.Press, 1998. Less

在此之前，我们给出了一种单点代数几何码在设计距离内的快速解码算法，该算法可以在传统的冯诺依曼型计算机上串行实现。现在，我们已经建立了一种以并行形式实现解码算法的方法，并采用了并行处理的系统阵列架构。(1) 1996年7月，在奥地利Line召开的IMAX-ACA会议上，提出了原始快速解码算法并行化的基本思路；(2)在1997年6月法国图卢兹AAECC-12会议上，提出了一种快速算法的矢量版本，该算法是并行解码方法的核心；发表于《计算机科学讲义》（LNSC），第1255卷（编辑）。Mora et al.)， b施普林格，1997；(3)基于压缩阵列架构的并行译码算法的全单元（处理器）高效调度方法，《IEEE国际信息理论研讨会》，1997年7月，德国。对于码长n，我们的方法的时间复杂度为O (n)阶，优于[R]得到的O （n^2）。Kotter， AG码的BM算法的快速并行实现，关于AG码和循环码的代数解码，博士论文，林雪平大学，（第3部分），1996。此外，我们还着手研究了几个相关主题，例如用于纠正擦除和错误的软判决解码方法，该方法可以并行化（部分内容包含在LNSC-1255上发表的论文中）。在1997年9月美国伊利诺斯州的Allerton通信、控制与计算会议上提出了一种快速广义最小距离（GMD）译码方法，并在Allerton会议前的blahuttest特别会议上作了关于Berlekamp-Massey-Sakata算法的演讲。关于Grobner碱基和编码理论的教程论文发表在Grobner碱基和应用（编辑）。Buchberger等人)，剑桥大学出版社，1998年。少

项目成果

S.Sakata: "Fast GMD decoding of algebraic codes" Proc.35th Annual Allerton Conference on Communication,Control and Computing. to appear.

S.Sakata：“代数代码的快速 GMD 解码”Proc.第 35 届阿勒顿通信、控制和计算年度会议。

S.Sakata: "Fast GMD decoding of algebraic codes" Proc.35th Annual Allerton Conference on Communication,Control and Computing. (to appear).

S.Sakata：“代数代码的快速 GMD 解码”Proc.第 35 届阿勒顿通信、控制和计算年度会议。

S.Sakata: "Fast erasure-and-error decoding of any one-point AG codes up to the Feng-Rao bound" Bulletin Univ.Eelct.-Comm.9,1. 39-57 (1996)

S.Sakata：“对任何单点 AG 代码进行快速擦除和错误解码直至 Feng-Rao 界”Bulletin Univ.Eelct.-Comm.9,1。

M.Kurihara, S.Sakata, K.Kobayashi: "On a class of byte-error-correcting codes from algebraic curves and their fast decoding algorithm" IEICE Trans. Fundamentals. E79-A. 1298-1304 (1996)

M.Kurihara、S.Sakata、K.Kobayashi：“关于代数曲线的一类字节纠错码及其快速解码算法”IEICE Trans。

M.Kurihara, S.Sakata, K.Kobayashi: "On a class of byte-error-correcting codes from algebraic curves and their fast decoding algorithm" IEICE Trans.Fundamentals. E79-A. 1298-1304 (1996)

M.Kurihara、S.Sakata、K.Kobayashi：“关于代数曲线的一类字节纠错码及其快速解码算法”IEICE Trans.Fundamentals。