一种极化码的译码算法研究

郑昊

摘 要：极化码是近年来提出的一种新型编译码技术，是目前唯一能被证明达到香农极限的纠错编码，是无线通信领域的重大突破，因此受到了国内外学者的广泛关注和研究。各国学者相继提出了一些译码算法，但这些算法在译码性能、延时、吞吐率、计算复杂度等方面表现的并不理想。通过对标准BP译码算法迭代过程方程式的改进，文章提出了一种改进的BP译码算法，经仿真分析，对比标准的BP译码算法，改进算法在保持译码性能不降低的前提下，有效降低了计算复杂度和时间复杂度。

关键词：极化码;置信度传播译码;计算复杂度;时间复杂度;香农极限;无线通信

中图分类号：TP39 文献标识码：A 文章编号：2095-1302（2019）05-00-03

0 引 言

極化码[1]由土耳其学者Arikan于2008年提出，在码长趋于无穷大时，极化码可达到信道容量。极化码具有结构化、编译码复杂度低等特点，引起了各国学者的广泛关注和研究。极化码的核心在于信道极化现象，包括信道组合、信道分裂。通过对已知信道的极化处理，部分子信道容量趋近于1，部分子信道容量趋近于0，我们选择在趋近于1的信道上传输有用的信息，在趋近于0的信道上传输冗余信息。基于此特性，文献[2]提出了串行抵消译码算法（Successive Cancellation，SC），文献[3]提出了列表串行抵消译码算法（Successive Cancellation List，SCL），文献[4]提出了置信度传播译码算法（Belief Propagation，BP），但SC，SCL都是串行译码算法，存在延时较高、吞吐率较低的缺陷，而BP译码算法又涉及大量乘除运算，计算复杂度较高。

针对上述译码算法的不足，文章提出了一种改进的BP译码算法，对标准BP算法的迭代公式进行改进，并对数域简化。经仿真分析，在保持译码性能不降低的前提下，可有效降低译码计算复杂度和时间复杂度。

1 BP译码算法

（N，K）的极化码迭代译码因子图网络由（M+1）N个节点组成，其中N=2M，每一个节点（i，j）与相邻节点进行信息传递更新，当达到预置的最大迭代次数之后，将迭代后的信息输出再进行硬判决译码。图1所示为N=8的极化码因子图。

因子图包括3层，每层包含4个基本运算单元，用来更新和迭代计算译码信息，通过相邻层之间的信息迭代更新，达到最佳译码性能。在相邻层之间节点进行迭代信息交换的过程中，包含左向迭代信息和右向迭代信息。在一次迭代过程中先计算从右至左的传播信息，直至最左边一层，再计算从左至右的传播信息，直至最右边一层，此时完成一次迭代运算。图2所示为BP译码算法的基本计算单元。

2 改进的BP译码算法

上节详细描述了标准BP译码算法，可以看出，标准算法在迭代计算的过程中，第i次迭代计算需要第i-1次迭代计算的数据作为输入，增加了运算成本。同时，标准算法是基于概率域的运算，涉及大量乘除运算，计算复杂度高且可能造成数据溢出。为了改善以上问题，本文提出了一种改进的BP译码算法，所有信息传递过程都在本次迭代内完成，不涉及之前的迭代轮次，迭代过程如图4、图5所示，同时将概率域内的运算变换至对数域，以有效降低计算复杂度，并防止数据溢出。改进的BP译码算法在对数域内经过min-sum[5]简化后，得到迭代过程方程式，见式（7）～式（10）。译码流程与标准BP译码算法相同。

3 译码算法仿真

对码长N=1 024，码率R=0.5的极化码，在BPSK（二进制相移键控）和AWGN（加性高斯白噪声）信道下对标准BP译码算法和改进的BP译码算法进行译码性能仿真，如图6所示。从图中可以看出，在迭代次数为40次，信噪比较小时两种算法性能几乎一致，随着信噪比增大，改进算法性能略优于标准算法。

迭代译码算法通常根据最差噪声情况来设置固定的迭代次数，但是在实际信噪比情况下，较少的迭代次数就可以达到收敛条件。我们使用基于CRC的迭代终止准则[6]对两种译码算法进行对比，如图7所示。从图中可以看出，相同条件下，改进的BP译码算法所需要的迭代次数随着信噪比的增加远小于标准BP译码算法，因此在时间复杂度上优于标准BP译码算法。

4 结 语

本文对极化码标准BP译码算法进行了简要概述，通过分析不足对其进行了改进，提出一种改进的BP译码算法，并对两种算法进行仿真比较。仿真结果表明，在译码性能略优于原算法的情况下，改进的BP译码算法可以有效降低计算复杂度和时间复杂度。

参 考 文 献

[1] ARIKAN E. Channel polarization：a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE trans. Inf. theory，2009，55（7）：：3051-3073.

[2] ARIKAN E. Channel polarization：a method for constructing capacity-achieving codes[C]// IEEE International Symposium on Information Theory（ISIT）， 2008：1173-1177.

[3] TAL I，VARDY A. List decoding of polar codes[C]// in Proceedings of the IEEE International Symposium on Information Theory Proceedings （ISIT11），2011：1-5.

[4] ARIKAN E. A performance comparison of polar codes and Reed-Muller codes[J]. IEEE communications letters，2008，12（6）：447-449.

[5]黄胜武.Polar Code译码算法的研究与实现[D].成都：电子科技大学，2017.

[6]刑超，赵生妹，郑宝玉.极化码置信传播算法早期终止准则的研究[J].信号处理，2016，32（3）：253-259.

[7]田佳佳.极化码的译码算法研究[D].成都：电子科技大学，2016.

[8]吴道龙.极化码构造与译码算法研究[D].西安：西安电子科技大学，2016.

[9]刑超，徐顺频，赵生妹.一种基于整数操作的极化码最小和译码算法[J].南京邮电大学学报（自然科学版），2015，35（1）：52-55.

[10]王继伟.极化码编码与译码算法研究[D].哈尔滨：哈尔滨工业大学，2013.