极化码的线性规划译码和最大似然译码问题研究

Polar codes have become a hot research topic in the channel coding area and become a competitive alternative of Turbo codes and low-density parity-check codes in the next-generation communication system. This project focuses on this hot topic and investigates the linear program (LP) decoding and maximum likelihood (ML) decoding problems for Polar codes...In this project, low-complexity methods will be proposed for LP decoding of Polar codes based on the specific structure of the LP decoding problem as well as the optimization principle. Using the ML certificate of LP decoding, improved LP decoding algorithms for Polar codes will be provided, which improve the decoding performance with a slight increase in computational complexity when the original LP decoder converges to a non-integral pseudocodeword. There are close connections between Polar codes and Reed-Muller (RM) codes. Using the ideas in the decoding algorithms of RM codes, efficient trellis-based ML decoding and reliability-based near ML decoding methods will be presented for Polar codes with short lengths and moderate lengths, respectively, in this project. In order to improve decoding performance, hybrid decoding methods for Polar codes with moderate lengths will be provided based on the reliability-based decoding and LP decoding. The weight distribution properties of low-weight codewords and pseudocodewords of Polar codes will be determined using the structures of Polar codes and the connections between Polar codes and RM codes. In addition, the decoding performances will be analyzed using the obtained weight distributions.

极化码是目前信道编码领域的研究热点，并且在下一代通信系统中成为Turbo码和低密度奇偶校验码的有力竞争者。本项目将瞄准这一热点问题，创新性地研究极化码的线性规划译码和最大似然译码问题。.本项目拟利用极化码的LP译码问题的特定结构，采用最优化原理，提出该LP译码问题的低复杂度求解方法。针对LP译码可能收敛到非整数伪码字这一问题，利用LP译码的最大似然特性，提出极化码的改进LP译码算法，在性能和复杂度之间获得更好的折中。极化码和Reed-Muller(RM)码有密切联系。本项目拟利用RM码译码算法的设计思想，提出短码长的极化码基于网格图的有效ML译码方法以及中等码长的极化码基于可靠性的有效近似ML译码方法，并与LP译码相结合设计中等码长的极化码的混合译码方法，以获得性能改善。利用极化码的结构以及与RM码的联系，确定极化码的低重量码字和伪码字的重量分布，并利用重量分布对极化码的性能进行分析。

本项目对差错控制编码领域的研究热点——极化码、Reed-Muller(RM)码及其子码的线性规划(LP)译码和最大似然(ML)译码及相关问题进行了深入研究，在下述方面取得了主要成果：. 针对求解LP译码问题具有复杂度高的缺点，对采用次梯度方法求解LP译码问题进行了研究。提出了一种校验节点处理方法，证明了其复杂度为校验节点度的线性函数，进而给出了一种LP译码的迭代算法，具有极低的单次迭代复杂度。通过仿真验证了提出方法的性能可以接近标准LP译码的性能。. 利用LP译码原理，提出了一种码间干扰(ISI)信道下的交替方向乘子(ADMM)译码方法—l2-box ADMM译码算法。为了提升性能，在目标函数中引入恰当的惩罚项，进一步提出了l2-box ADMM惩罚译码算法。仿真分析表明，提出的l2-box ADMM惩罚译码算法在ISI信道下的性能优于已有的ADMM惩罚译码算法，并且保持了ADMM译码算法低复杂度的优点。. 研究了RM码和RM子码的ML译码。基于Kaneko等的工作，给出了一种RM子码的高效ML译码算法。证明了当RM子码最小距离等于其母码时，算法输出为ML码字。对于短码长范围内，通过计算机搜索分析得到了RM子码最小距离等于其母码的情形。此外，提出了一种近似ML译码算法，并给出了在译码性能和复杂度之间获得折中的参数确定方法。. 对刻画线性码ML译码和LP译码性能的码字和伪码字分布性质进行了深入研究。编写了二元线性码的低重量码字和伪码字搜索算法的程序，观察了Polar码和RM子码的码字和伪码字分布。对于二元汉明码，利用其与一阶RM码的关系，证明了其满秩校验矩阵的伪码字的若干性质，解释了其采用LP译码的性能。