极化码的连续消除译码性能改进方法

袁辽， 倪卫明(复旦大学 信息科学与工程学院，上海 200433)

极化码的连续消除译码性能改进方法

袁辽， 倪卫明
(复旦大学 信息科学与工程学院，上海 200433)

研究了极化码的连续消除译码性能改进方法。提出了两种改进算法，分别为双路径判决延迟译码和含阈值可变路径判决延迟译码。传统的连续消除译码算法为码树上贪婪算法，不能修正在当前节点之前的判决错误。利用判决延迟译码来为当前译码节点提供修正上一个节点判决错误的机会。提出的双路径和含阈值可变路径的判决延迟译码通过增加译码码树中的计算节点和增加存储空间来提升译码性能。仿真结果显示双路径判决延迟译码比较于传统的连续消除译码方式，对译码性能有1.1 dB左右的增益，含阈值可变路径判决延迟译码有进一步的译码增益效果。

极化码； 连续消除译码； 判决延迟译码； 双路径判决延迟译码

0 引言

极化码[1]是由Arikan在信道极化的基础上首次提出，在保证信道总容量不变[2]的情况下，二元离散无记忆信道产生极化现象: 一部分子信道表现出无噪信道的特征，另外一部分子信道表现为纯噪声信道的特征。无噪子信道的信道容量能趋于1，将需要传输的信息在无噪子信道上传输。剩余的子信道信道容量趋于0，该部分子信道传输收发方均已知的比特。由此信道极化从整体上提高信道传输的可靠性。

对于极化码的编码，I. Tal 和A. Vardy[3]提出2种近似量化的构造方法，有效降低码长较大时编码的复杂度。R. Mori 和T. Tanaka[4]提出使用卷积构造的方法，进一步提高编码效率，达到线性的复杂度。极化码的提出是基于二进制删除信道(BEC)，而H. Li和J. Yuan[5]提出在加性高斯白噪声信道下的极化码编码的方法。Arikan在极化码首次提出时同时引入连续消除译码 (successive cancellation, SC)方法。在连续消除译码的基础上，列表连续消除译码[6]和堆栈连续消除译码[7]相继提出。

本文以连续消除译码为基础，提出两种译码算法。在文中两种方法分别称为双路径判决延迟译码和含阈值可变路径的判决延迟译码。两种方法都采用了对于信息比特译码判决延迟的方案[8]，增加码树中的计算节点和路径选择，来提高译码性能。通过码树分析，本文比较了两种译码算法和经典的连续消除译码算法以及判决延迟译码算法的复杂度。仿真结果显示提出的两种算法对于译码性能有增益效果。

1 连续消除译码

(1)

对于码长N=2n，1≤i≤n，后验概率可如下递归计算如式(2)、(3)。

(2)

(3)

(4)

对于i∈I，相应的递归计算方式如式(5)、(6)。

(5)

(6)

(7)

3 判决延迟译码

3.1 单路径判决延迟译码

连续消除译码，可以看作是码树上的贪婪算法。如图1所示(节点下方数字代表后验概率)。

图1 极化码码树的路径选择

连续消除译码算法只对当前节点进行判决，一旦路径选择完成，将进行到下一节点，图中黑色实心单箭头所示路径为连续消除译码算法对于该码树的译码结果。但是，实际中，黑色空心双箭头所示路径为后验概率最大的路径，连续消除译码在第一判决时，路径选择就发生了偏差，选择的是当前最优，而不是全局最优的解。

针对上述缺陷，本文采用判决延迟译码算法。连续消除译码中如果当前节点的路径选择错误，算法没有机会在对其进行修正。而错误的路径选择，会对随后的节点的路径选择产生干扰，引发更多的错误。因此，延迟判决译码算法，对于每一个节点，对于判决进行延迟，采用后一步的节点的判决结果，来替代当前节点的判决，为当前节点的判决增加修正的机会。

对于i∈I，判决延迟译码表达式如下：

(8)

(9)

(10)

对于i=N，则判决方法和连续消除译码一致。特别指出，ui+1表示为下一个信息比特位。应用判决延迟译码，对于图1再次进行译码判决，即可得到后验概率最大的空心双箭头路径，修正了连续消除译码的判决错误。

3.2 双路径判决延迟译码

将参与连续消除译码和判决延迟译码两种算法的节点和路径从满二叉树图中取出，分别表示如图2所示。

图2 连续消除译码(右)，判决延迟译码(左)示意图

显然，延迟判决译码方法的对于算法的增益，源于对于判决节点计算的增加。将原本单节点的两条路径的比较，拓展为双节点，四条路径的比较，从而获得对于连续消除译码的修正。单路径判决延迟译码算法，在处理判决结果时，只保留了下一个节点中后验概率最大的路径。而对于ilt;N每一个判决延迟的每一个计算单元，都含有两个节点和四条路径。因此，考虑保留2条路径，将算法改进为双路径判决延迟译码。该算法步骤如下：

3.3 含阈值可变路径的判决延迟译码

判决延迟译码引入保存双路径，为译码的进一步增加了修正后验概率最大路径的能力。而使用最大似然译码等同于考虑所有可行路径，可以找到全局最优的路径，但是算法所需要的复杂度随码长指数增长，而收益增长甚小。在判决延迟译码中，有下一信息位的后验概率的辅助，考虑对于当前保留节点和路径数进行动态修正。显然，当后验概率值接近时，在随后的信息比特的概率值比较时，更容易出现概率值大小关系反转的现象。因此，引入阈值，对于判决延迟译码算法，进行可变路径的改变。具体算法如下：

步骤4. 遍历ilt;N，重复步骤2, 3；当i=N时，比较计算的是最终保留所有序列(2条或3条路径)的后验概率值，取较大者为最终译码序列。

4 算法分析

4.1 码树分析

对于ilt;N，连续消除译码，判决延迟译码，双路径判决延迟译码以及含阈值可变路径判决延迟译码的基本计算单元的变化如图3—图5所示。

图3 判决延迟译码(右)和连续消除译码(左)计算单元比较

对于连续消除译码算法，其参与计算的节点数VSC很容易给出式(11)。

VSC=2*K+(N-K)+1

(11)

图4 单路径延迟判决译码(右)和双路径判决延迟译码(左)计算单元比较

图5 延迟判决译码(右)和含阈值可变路径判决延迟译码(左)计算单元比较

而对于单路径判决延迟译码算法，其节点数则与第一个信息比特有关。设第一个信息比特之前有VF1个固定比特，之后有VF2个固定比特，满足VF1+VF2=N-K。不同于连续消除译码算法，在第一个信息比特之后的固定比特，将有传递2条路径，因此，判决延迟译码算法所需计算节点数VOSDD为式(12)。

VOSDD=4*K+VF1+2*VF2-1

(12)

类似地，双路径判决延迟译码，相比较于单路径判决延迟译码，只是对其选择路径的方式不同，所需的计算节点V2-OSDD并没有增加式(13)。

V2-OSDD=4*K+VF1+2*VF2-1

(13)

而含阈值可变路径判决延迟译码，设K*PK次保留3路径，对于计算节点的额外增加，就由这些路径引发。因此，其计算节点数量VK-OSDD如下式(14)。

VK-OSDD=4*K+2*(K*PK)+VF1+

(14)

双路径判决延迟译码相比于单路径判决延迟译码，没有增加额外的计算节点，只是对于存储空间提出新的要求。而含阈值可变路径判决延迟译码，则与阈值正相关的增加了所需的计算节点，并且同样对存储空间提出更多需求。

4.2 复杂度分析

我们对于提出的算法，进行复杂度的分析，并与传统的连续消除译码算法进行对比。连续消除译码算法的复杂度已知为Nlog2N。单路径判决延迟译码算法的复杂度已知为2Nlog2N-(N-1)。

对于双路径延迟译码算法，如码树分析中所示，其计算节点相较于单路径延迟译码算法并没有增加，优化的部分为延迟译码中路径选择的方式。因此，双路径延迟译码算法复杂度维持为2Nlog2N-(N-1)。虽然计算复杂度上没有增加，但是空间复杂度上，双路径延迟译码提升了一倍，需要单路径延迟译码2倍的存储空间。类似地，对于含阈值可变路径判决延迟译码，不同阈值引发不同的算法复杂度的增加。显然地，阈值越小，其引入的额外路径更多，算法复杂度增加更多。因此，含阈值可变路径判决延迟译码算法复杂度，受阈值影响，有上限和下限：当不引入额外路径，算法等同于双路径延迟译码，算法复杂度下限为2Nlog2N-(N-1)；当全部每一次计算单元，都引入额外路径，算法等效于三路径延迟译码，算法复杂度上限为3Nlog2N-(N-1)。同样的，含阈值可变路径判决延迟译码也需要增加额外的空间复杂度，对存储空间有额外需求。含阈值可变路径判决延迟译码的主要贡献在于，在更可能出现译码反转的节点上增加更多的修正机会，以小的算法复杂度增加获得较大的性能提升增益。

5 仿真结果

为展示提出的双路径判决延迟和含阈值可变路径判决延迟译码对于译码性能的提升，在图6中对比了双路径判决延迟译码和单路径延迟译码以及传统连续消除译码的性能对比，在图7中对比了不同阈值下，含阈值可变路径判决延迟译码与双路径延迟译码以及四路径延迟译码的性能对比。仿真采用加性高斯白噪声信道，选取极化码长，码率为0.5。

图6 连续消除，判决延迟和双路径判决延迟的译码性能对比

图7 阈值k=0.1,0.15,0.2下不同译码方案对比

仿真结果显示的是不同信噪比情况下，不同译码算法的误比特率。特别地，由于双路径判决延迟的译码性能已经比较接近最大似然译码，在对比含阈值可变路径判决延迟译码性能时，选用的信噪比跨度较小，来较为明显地反映性能的提升。

6 总结

本文提出的双路径判决延迟译码算法和含阈值可变路径判决延迟译码都可提升极化码的译码性能。码树分析和算法分析显示，本文提出的算法复杂度增加甚小。仿真结果显示，在加性高斯白噪声信道下，双路径判决延迟译码对于单路径延迟译码有0.75 dB的增益，而含阈值可变路径判决延迟译码对于译码性能有进一步的增益。

[1] Arikan, Erdal. "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels."[J]. IEEE Transactions on Information Theory 55.7(2009):3051-3073.

[2] Arikan, Erdal. "Channel combining and splitting for cutoff rate improvement."[J]. IEEE Transactions on Information Theory 52.2(2005):628-639.

[3] Tal, Ido, A. Vardy. "How to Construct Polar Codes."[J]. IEEE Transactions on Information Theory 59.10(2011):6562-6582.

[4] Mori, Ryuhci, T. Tanaka. Performance and construction of polar codes on symmetric binary-input memoryless channels[C]//IEEE International Symposium on Information Theory IEEE, 2010:1496-1500.

[5] Li, Huijun, J. Yuan. A practical construction method for polar codes in AWGN channels, Tencon Spring Conference[C]//IEEE, 2013:223-226.

[6] Tal, Ido, A. Vardy. List Decoding of Polar Codes, Information Theory[J]. IEEE Transactions on 61.5(2012):2213-2226.

[7] Niu, K, K. Chen. Stack decoding of polar codes[J]. Electronics Letters, 48.12(2012):695-697.

[8] Hadi, Ammar, E. Alsusa, K. M. Rabie. A method to enhance the performance of successive cancellation decoding in polar codes. International Symposium on Communication Systems, Networks and Digital Signal Processing[J]. IEEE, 2016:1-5.

MethodsforEnhancingSuccessiveCancellationDecodingofPolarCodes

Yuan Liao, Ni Weiming
(Department of Information Science and Technology，Fudan University，Shanghai 200433)

In this paper, we study methods to enhance successive cancellation decoding of polar codes. We propose two improved algorithms: two-path decision delay decoding and variable path decision delay decoding with the threshold. Conventional successive cancellation decoding is greedy algorithm in code tree, it means that successive cancellation decoding can’t correct errors from the former nodes. In this paper, the decision delay decoding is used to provide opportunity to correct previous error for the current node. The proposed two-path and variable path decision delay decoding can improve the decoding performance by increasing the computing nodes and increasing the storage space. The simulation results show that compared to successive cancellation decoding, the two-path decision delay decoding has 1.1dB gain on decoding performance. In addition, variable path decision delay decoding has more gain.

Polar code; Successive cancellation decoding; Decision delay decoding; Two-path decision delay decoding

袁 辽(1993-)，男，宁波人，硕士研究生，研究方向：信道编码、通信算法优化.

倪卫明(1970-)，男，上海市人，博士，副教授，研究方向为无线通信和无线网、通信信号处理、编码技术等.

1007-757X(2017)11-0042-04

TN911.22

A

2017.03.10)