高维基矩阵下信道极化码设计与译码算法优化研究

Following the turbo and low density parity check (LDPC) codes, polar codes are another capacity achieving codes with low encoding and decoding complexity. Compared to the turbo and LDPC codes, a major advantage of polar codes is that its capacity achieving performance over arbitrary symmetric binary-input discrete memoryless channels can be theoretically proved. Now, there are two main problems for polar codes in practical application: 1) Compared with turbo and LDPC codes, the performance of polar codes at short to moderate block lengths is disappointing; 2) The traditional successive-cancellation (SC) decoders suffer from a very high latency. Around the two issues, the project will study the following four aspects：1）Design of polar codes under high dimension kernel matrix; 2) Design of polar codes under low latency SC decoding algorithms; 3) Latency reduced methods for list SC decoding algorithms; 4) Latency reduced methods for SC decoder under high dimension kernel matrix. Research questions of this project are a key issue to be resolved for polar codes in practice and the research will provide theoretical and practical support for polar codes in practical application.

信道极化码（polar codes）是继Turbo码和低密度奇偶检验码（LDPC）之后被发现的又一个能够逼近信道容量、同时有着低编译码复杂度的信道编码方案。极化码比Turbo和LDPC码更进一步的是：在任意二进制输出离散无记忆对称信道下，理论上严格证明了其渐近性能可以达到信道容量。然而，与现有技术相比（Turbo和LDPC码），中短长度极化码译码纠错性能存在劣势的问题和极化码的连续消去(SC)译码算法的译码延时问题是极化码应用于实际中需要解决的两个关键问题。本项目围绕着如何解决这两个问题进行研究，包括四方面的内容：1）高维基矩阵下的极化码设计方法；2）面向低延时SC译码方案的极化码设计方法；3）列表连续消去译码算法的延时减少方法；4）高维基矩阵下的SC译码算法延时减少方法。本项目的研究问题是极化码应用于实际需要解决的关键问题，研究成果将为极化码的实用化提供理论基础和方案支持。

相比于原2×2维核矩阵，高维核矩阵具有更大的信道极化速率，因此其具有着更优的译码纠错性能。然而，高维核矩阵极化码设计和其低译码复杂度问题是高维核矩阵研究瓶颈问题。课题组围绕着高维核矩阵极化码设计和其低译码复杂度问题，进行了深入的研究，取得一些有意义的成果，现总结如下：.1..高维核矩阵极化设计研究结果.① 基于二进制擦除BEC信道的精确极化码设计方法。该方法的贡献如下：1) 当核矩阵维数小于等于16时，获得了所有最优核矩阵的单步位信道擦除概率多项式；2) 仿真表明，基于BEC信道的精确极化码设计方法，能有效设计高维核矩阵极化码。.② 设计一种极化码的快速蒙特卡洛（MC）构造方法，用于设计高维核矩阵阵极化码。该方法的贡献如下：1) 发现MC构造方法中的连续消去（SC）译码过程可以被并行地执行，从而大量的降低SC译码延时；2) 针对高维核矩阵的极化码，在SC和列表SC译码下，MC构造方法比高斯密度进化构造方法有着更优的译码纠错性能； 3) 相比于2×2维核矩阵极化码，高维核矩阵（如维数为15和16时）的极化码在SC和列表SC（LSC）译码下也有显著的译码性能提升。.2..高维核矩阵极化码低复杂度译码算法研究结果.① l-表达式方法.获得任意高维核矩阵的SC译码在似然比域的简化递归计算式，极大减少了高维核矩阵(维数小于等于16)的SC译码的译码复杂度。.② W-表达式方法.为了进一步降低复杂度，类比于l-表达式，分开考虑位信道转移概率，提出了一个W-表达式方法。当核矩阵维数小于等于16时，W-表达式将SC译码的复杂度从维数m的指数级复杂度-O(2^mNlogN)，降低为维数的多项式级复杂度-O(m^2NlogN)。