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

在此之前，我们给出了一种达到设计距离的单点代数几何码的快速译码算法，该算法可以在传统的von Neumann型计算机上以串行形式实现。现在，我们已经建立了一种用sytolal阵列结构来并行处理的并行实现译码算法的方法。我们的部分结果在几个国际会议上公布：(1)我们对原始快速译码算法并行化的基本想法，1996年7月在奥地利莱恩的IMAX-ACA会议上；(2)作为我们并行译码方法的核心的快速算法的矢量版，在1997年6月，法国图卢兹的AAECC-12会议上；发表在计算机科学(LNSC)的讲座笔记，第1255卷(编辑莫拉等)，斯普林格，1997；(3)在IEEE国际研讨会…上用脉动阵列结构实现我们的并行译码算法时，一种有效地调度整个信元(处理器)的方法《信息论的更多内容》，德国乌尔姆，1997年7月。对于码长n，我们的方法具有O(N)阶的时间复杂度，优于[R.Kotter，一种用于AG码的BM算法的快速并行实现，关于AG Godes和循环码的代数译码，论文，林科平大学，(节)3,1996]所获得的O(n^2)。此外，我们还研究了几个相关的主题，如纠删纠错的软判决译码方法，这些方法是可以并行化的(部分内容包含在发表在LNSC-1255上的论文中)。1997年9月，在美国伊利诺伊州举行的Allerton通信、控制和计算会议上提出了一种快速广义最小距离(GMD)译码方法，并在Allerton会议前夕的BlahutFest特别会议上发表了关于Berlekamp-Massey-Sakata算法的演讲。关于Grobner基和编码理论的教程论文发表在Grobner基和应用(编辑：Buchberger等人)上，剑桥大学出版社，1998。较少

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