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

我们以前曾给出过一个一点代数几何码的快速译码算法，它能在冯·诺依曼型的普通计算机上以串行形式实现。现在，我们已经建立了一种方法来实现解码算法的并行形式与符号阵列结构的并行处理。我们的部分结果在几个国际会议上发表：（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年。少

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