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
项目状态：
已结题

项目摘要

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

在我们给出了一个快速解码算法的单点代数几何代码到设计距离之前，可以在von Neumann类型的常规计算机上以串行形式实现。现在，我们已经估算了一种以并行形式实现解码算法的方法。我们的部分结果在几个国际会议上介绍：（1）我们在1996年7月在奥地利的IMAX-ACA会议上平行原始快速解码算法的BSIC思想；（2）快速算法的矢量版本，它是我们在法国图卢兹的AAECC-12上的平行解码方法的内核，1997年6月；发表在计算机科学（LNSC）的讲义上，第1255卷（Eds.Mora等），Springer，1997年；（3）一种在IEEE IEEE International Symposiu上使用收缩阵列体系结构实施我们平行分组算法的有效安排方法的方法，这是关于信息理论的更多信息。 AG代码的BM算法，关于AG神和循环代码的代数解码，论文，Linkoping Univ。，（部分）3,1996]。此外，我们开始研究几个相关主题，例如校正擦除和错误的软决策方法，这些方法可以并行化（部分包含在LNSC-1255中发表的论文中）。 1997年9月，在美国伊利诺伊州的Allerton通信，控制与计算会议上，介绍了一种快速概括的最小距离（GMD）解码方法，并在AllertonChinding oflerton会议上的特别会议Blahutfest上进行了有关Berlekamp-Massey-Sakata算法的演讲。关于Grobner基础和编码理论的教程论文发表在Grobner基础和应用中（Eds.Buchberger等），Cambridge Univ.Press，1998。