线性分组码的两阶段最大似然软判决译码方法

Linear block codes have been deployed for error control in communication systems for many years and maximum-likelihood soft-decision decoding of them is a very important research problem. Especially, the soft-decision decoding of Reed-Solomon codes is always an important issue in IEEE Information Theory (IT) society. This is supported by giving the best paper award to the work entitled “Algebraic soft-decision decoding of Reed-Solomon codes” in 2004. Even though it is not a maximum- likelihood soft-decision decoding but sub-optimal one, it still got the award by reducing the decoding complexity drastically. Based on the notion of supercodes, we propose a two-phase maximum-likelihood soft-decision decoding (tpMLSD) algorithm for linear block codes in this proposal. The first phase applies the Viterbi algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority- first search algorithm to the trellis corresponding to the linear block code itself, which guarantees finding the ML decision. Preliminary simulations on Reed-Muller codes show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the existing recursive maximum-likelihood decoding (RMLD) when the signal-to-noise ratio per information bit is 4.5 dB. Based on this promising approach, we propose to apply this algorithm to BCH codes and finally Reed-Solomon codes. If the decoding complexity can be reduced near to those in the award-wining work with maximum-likelihood soft-decision decoding performance, it will result in an excellent work in IT society.

在通信系统中线性分组码已被应用于差错控制多年，其中最大似然软决定译码是一个非常重要的研究课题。尤其，里德 –所罗门码软判决译码一直是IEEE信息理论领域的一个重要课题。基于超级译码的概念，在本提案我们提出了一个用于线性分组码的两阶段最大似然软判决译码算法。在第一阶段我们采用维特比算法，从线性分组码的超码的奇偶校验检查矩阵中逆向导出衍生网格。使用在第一阶段存储的信息，在第二阶段中，对线性分组码本身采用网格优先搜索算法来进行最大似然软判决。对里德-穆勒码的初步实现显示，当每个信息位的信噪比为4.5分贝的情况下，与现有的递归最大似然译码方法相比，该两阶段译码方法的平均译码复杂度更低。在这个方法的基础上，我们建议将此算法应用到BCH码和里德 –所罗门码中。如果码译复杂度可减少到接近那些屡获殊荣的优秀最大似然软判决译码算法，我们的工作在信息理论领域中将是十分有意义的。

在通信系统中线性分组码已被应用于差错控制多年，其中最大似然软决定译码是一 个非常重要的研究课题。尤其里德–所罗门码软判决译码一直是IEEE信息理论领域的 一个重要课题。基于超级译码的概念在本提案我们提出了一个用于线性分组码的两阶段最大似然软判决译码算法。在第一阶段我们采用维特比算法，从线性分组码的超码的 奇偶校验检查矩阵中逆向导出衍生网格。使用在第一阶段存储的信息，在第二阶段中，对线性分组码本身采用网格优先搜索算法来进行最大似然软判决。对里德-穆勒码的初步 实现显示，当每个信息位的信噪比为4.5分贝的情况下，与现有的递归最大似然译码方法相比，该两阶段译码方法的平均译码复杂度更低。在这个方法的基础上，对于(2,1,6)和(2,1,12)去尾回旋码，我們設計的算法不仅平均的译码复杂度比现有算法好，同时当码长和码的限制长度增长时，我们的算法复杂度也比较稳定。同时在高信噪比的环境下，我们的算法复杂度也接近理论下界。对于(64,24)BCH码，我们设计的算法复杂度比现有最优的方法还好，此方法也可以推广到其它的线性分组码。