关于Chase型译码算法的研究

Chase-like decoding algorithms are generalizations of the Chase decoding algorithms which have been applied in variant areas for long time. A Chase-like decoding algorithm employs a simple innner decoder around some given search centers to generate a few candidate codewords from which the best one is output, its complexity is about proportion to the number of search centers. A Chase-like decoding algorithm is asymptotically optimum when achieving bounded-distance decoding. The main objectives of this project include: (1) Design an algorithm to find the least number of search centers which ensure the Chase-like decoding algorithm may achieve given error performance. With the use of the optimum search centers found by computer searching, propose good Chase-like decoding algorithms applied to a few code lengths and signal-to-noise ratios in a big scope. (2) Improve the computation method of the error-correction radius and then estimate the least number of search centers with which the Chase-like decoding algorithm achieves bounded-distance decoding. (3) Improve the earlier termination conditions and ruling-out conditions imposed to known Chase-like decoding algorithms and the computation methods for them, so as to decrease the complexity without degrading their error performance. (4) For the non-binary case, the algebraic structure of the codes will be utilized to generate the search centers suitably. The Chase-like decoding algorithms are studied when combining the GMD or OSD algorithms. The inner decoder of Chase-like decoding algorithms is also considered to be improved further or replaced simply by a decoder with much better error performance, such as a list-decoding algorithm.

Chase型译码算法是长期以来获得广泛应用的Chase译码算法的推广，利用一个简单的内部译码器和给定的搜索中心产生一系列候选码字并输出其中最好者，计算复杂度与搜索中心的数量成正比。达到限界距离译码的Chase型译码算法是渐近最优的。本项目的主要研究目标：（1）设计计算机算法来计算达到指定误码率所需搜索中心的最小数目。以计算机搜索获得一些最佳搜索中心为基础，提出对码长和信噪比都具备较大适用范围的好的Chase型译码算法的设计方法。（2）在改进其纠错半径的计算方法的基础上，对达到限界距离译码所需搜索中心的最小数目进行估计。（3）改进已有的Chase型译码算法所附加的早期终止条件和除外条件及其计算办法，在不降低纠错能力的基础上降低其计算复杂度。（4）对于非二元码的情形，利用码的代数结构来构造搜索中心，还将Chase型译码算法与GMD算法或OSD算法进行结合研究，并且考虑对内部译码器进行改进。

Chase型译码算法利用一个简单的内部译码器围绕设定的中心搜索产生一系列候选码字并输出其中最好者，广泛应用于各种通信系统的差错控制。设计具有好的译码性能Chase型译码算法是纠错编码领域的重要问题。本项目的主要研究内容和结果：（1）对于较短的码长，研究了利用计算机算法来计算达到指定误码率所需搜索中心的最小数目。利用这些以计算机搜索获得一些搜索中心，提出了对码长和信噪比都具备较大适用范围的Chase型译码算法的几个设计方法。（2）我们通过改进Chase性译码算法纠错半径的已有计算方法，对达到限界距离译码所需搜索中心的最小数目进行了估计，得到了渐进最优的Chase型译码算法的最小复杂度的一个界。（3）对已有的Chase型译码算法所附加的早期终止条件和除外条件及其计算办法进行了改进，在不降低纠错能力的基础上降低了算法的计算复杂度。（4）对于基于代数图构造的LDPC码，我们充分利用其代数结构来构造搜索中心。（5）将Chase型译码算法与GMD算法或OSD算法进行结合，并应用于list-decoding方面的研究。完成发表本项目标注论文19篇并获得两项授权专利，其中SCI检索论文10篇。