基于树图剪枝的极化码译码简化算法

极化码是一种在二元对称信道下能够逼近香农限的信道编码,但其经典译码算法连续删除(successive cancellation,SC)译码和置信传播(belief propagation,BP)译码的复杂度较高,使得译码过程具有较大的计算复杂度和译码时延。对极化码译码过程的树图建模分析并对节点分类,证明了树图中部分节点对应的译码运算是冗余的。由此设计了树图剪枝的简化译码算法,在保证误码性能不变的前提下,明显降低了现有译码算法的计算复杂度。仿真结果证明,简化后SC译码和BP译码的译码复杂度较原始算法分别降低了36%~65%和41%~67%。

Simplified polar codes decoding algorithm based on pruning

Polar codes can approach the Shannon’s limit in binary symmetric channels. However, the conventional polar decoding algorithms, such as the successive cancellation (SC) and belief propagation (BP) decoding algorithms, have high computation complexity and latency in the decoding ends. Therefore, a binary tree graph is modeled and analyzed on the Polar decoding operations, which proves that the binary tree pruning can delete redundant decoding nodes. Simplified polar decoding algorithms based on pruning process of the tree graph are proposed, which greatly reduce computation complexity, and maintain the original error rate performance at the same time. Simulation results show that the simplified algorithms for the SC and BP decoding complexity can reduce by 36%~65% and 41%~67%, respectively.