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月奥地利的IMAX-ACA会议上，我们提出了将原快速译码算法并行化的基本思想：（2）在1997年6月法国图卢兹的AAECC-12会议上，我们提出了一种向量形式的快速译码算法，它是我们并行译码方法的核心;发表于Lecture Notes in Computer Science（LNSC），Vol.1255（Eds.莫拉et al.），Springer，1997年;（3）在IEEE国际研讨会上，提出了一种用脉动阵列结构实现并行译码算法的有效调度方法。 ...更多信息 1997年7月在乌尔姆，德国，信息论硕士。对于码长n，我们的方法具有O（n）阶的时间复杂度，这优于由[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.，（第3条，1996年）]。此外，我们已经着手研究了几个相关的主题，如软判决解码方法，用于纠正擦除和错误，这可以并行化（部分包含在LNSC-1255发表的论文）。一种快速的广义最小距离（GMD）译码方法在1997年9月于美国伊利诺斯州举行的Allerton通信、控制和计算会议上提出，在Allerton会议之前的BlahutFest特别会议上，给出了关于Berlekamp-Massey-Sakata算法的演讲。关于Grobner基和编码理论的教程论文发表在Grobner Bases and Applications（Eds.Buchberger et al.）中，剑桥大学出版社，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。