极化码序列连续删除译码算法的改进设计*

李 纯，童新海

(解放军理工大学 通信工程学院，江苏 南京 210007)



极化码序列连续删除译码算法的改进设计*

李 纯，童新海

(解放军理工大学 通信工程学院，江苏 南京 210007)

极化码连续删除译码算法性能和传统的LDPC码存在一定差距。序列连续删除算法(SCL)的提出极大地改善译码性能，是极化码推向实际应用中的重要一步。但是该算法复杂度较高，延迟大。改进的序列连续删除(SCL)译码算法是基于改善极化码码长受限的情况，文中描述SCL算法是通过码树上的搜索序列路径来表示译码过程。改进的算法通过减少译码算法在码树上的序列路径来降低时间和空间复杂度。通过仿真表明，改进的算法有效地降低了译码的复杂度同时在性能上也接近最大似然(ML)译码算法。

极化码 连续删除算法 最大似然译码 序列译码

0 引 言

极化码最核心思想是利用信道极化的过程进行编译码[1-3]。通过信道极化的理论分析，Arikan证明了极化码可以获得Shannon理论极限性能，并且保持对数编译码复杂度。然而研究表明，与传统的Turbo码、LDPC码相比，极化码在码长有限时的误码性能还不是很理想，为了进一步提高极化码的性能极限，许多高性能的译码算法被相继提出。

连续删除(SC)算法由Arikan首次提出，该算法利用比特信道似然概率的硬判决值输出译码序列，根据信道的拆分来进行迭代计算。可见SC算法是一种串行迭代的过程，具有译码的时延较大，吞吐量不高等特点。为改善SC译码算法性能，人们提出序列SC译码(SCL)[2]、堆栈SC译码(SCS)[3]、循环冗余校验辅助的SCL(CRC-SCL)[4]以及置信度传播(BP)的并行译码等算法。特别是CRC-SCL算法，可以显著提高SCL算法误码性能，在一定长度的码长条件下，该算法的性能优于部分Turbo码[4-7]。

SCL算法在序列足够大时，该算法性能接近于最大似然(ML)算法性能，但是译码的时间复杂度和空间复杂度都会随着L的增加而增加，本文提出的改进SCL算法就是通过联合CRC校验，保证译码性能的同时降低译码的复杂度。改进的算法分为两部分，前半部分主要保证译码性能，后半部分是根据前半部分的译码路径，降低译码的复杂度。

1 极化码

极化码是一种线性分组码，基于信道的组合和分离的进行编码，N个二进制离散无记忆信道(B-DMC)组合在一起然后分离，当N趋于无穷大时，部分信道的信道容量会趋近于1，相应的其他信道的信道容量趋近于0。利用信道容量高的信道传送信息比特，信道容量低的信道传送冻结比特。极化码编码的码率能够调节任意K/N，其中0≤K≤N编码块长度N的大小为2n，任意给定一个N，如下式对信息比特进行编码：

(1)

式中，向量u表示长度为N的传送信息比特，GN是N阶次的生成矩阵，向量x是编码后传入信道的码字。

2 序列连续删除算法

SCL算法是在SC算法比特信道的转移概率计算过程分析基础之所提出的，基本思路是改变比特信道的译码输出代替待编码序列的方式。译码算法会根据路径概率大小保留L条概率较大的路径，当完成比特信道的转移概率计算时，SCL选择最大的路径作为译码输出。SCL算法可用下述步骤描述(如图1所示)。

(2)

图1 SCL译码算法流程Fig.1 Searching process of SCL decoder

1)初始化：假设码树的初始节点都是空值，码树的同层的节点概率之和为1，即

S(0)={∅},P(∅)=1

(3)

2)比特估计：比特通过连续的下标来进行索引：i=1,…,N

条件概率为：

(4)

6)序列检测：在所有比特都被搜寻过，重新编码计算每个序列中节点的似然概率，选择其中一条最大的似然概率路径作为输出：

(5)

3 序列连续删除算法的改进

在实际译码过程中出现译码错误的比特往往对应的是信道容量较低的信道，因此极化码的性能主要是信道容量较小的信息位。对于码长短的极化码，极化速度慢，很多子信道的信道容量较低如图2所示，在构造极化码时会将一部分低信道容量的子信道用来传送信息位，从而降低极化码的性能。在SCL上述译码算法在L足够大时，SCL算法性能接近于ML(最大似然)算法性能，译码时间复杂度和空间复杂度均为O(LNlbN)。SCL算法译码时，每次保留L条路径值较大的译码序列，从而在信道容量较低的子信道上提高译码的精度，但是译码复杂度会随着L的增大而增大，在L足够大时，SCL算法性能接近于ML(最大似然)算法性能，但是这种穷尽搜索的方式复杂度呈指数增长，并且难以实现。

图2 信道极化Fig.2 Channel polarization

基于上诉分析，本文在序列连续删除算法的基础之上，采取下列改动，在保证一定性能的条件降低原算法的复杂度：

1)首先通过信道的合并与分解，算出N个子信道的信道容量，选出k个信道容量低的信息位和m个信道容量高的固定位，其中对k个比特位进行CRC编码，通过编码后的冗余位来进校验。本文采用的CRC—24，用(j1,j2,…,j24)校验位的下标。

2)经过CRC编码之后，对整个发送信息序列进行极化编码。译码时，在没有经过校验位j24之前，所有位采用序列连续删除算法。

3)按照每个信息位取0和1的概率，分别计算转移概率，按照概率的大小保留L条大的路径作为参考路径，在译码位大于j24时，用CRC对L条路径进行判断，如果有一条或多条路径通过了CRC校验，保留概率最大的路径作为输出，然后继续译后面的信息位置；如果没有通过校验，则发出指令重新译码。

4)对于j4后面的所有位译码，抛掉剩余路径，将通过校验的序列继续往下进行译码，同时将L值固定到1(即连续删除算法)，直接通过概率大小值来判断信息位为0还是为1，降低算法的复杂度，同时性能上和原算法也相近。

4 仿真结果与性能分析

在AWGN信道下，本文采用码长N=1 024，码率R=0.5，L=32，CRC-24生成多项式为g(D)=D24+D23+D6+D5+D+1对于m=24CRC校验比特放在发送信息比特的中间，所有的K=k+m送入编码器中。结果表明，改进算法的FER和SCL算法的性能想接近，同时在理论上很接近ML算法的误帧率。改进的SCL算法性能如图3所示。

图3 改进SCL算法性能Fig.3 Performance of modified SCL algorithm for polar codes

分析译码器复杂度通过调用递归路径节点概率计算的次数为标准。因此码长1 024，码率0.5的SC译码算法的复杂度为1 024×8=8 192。表1对比了各个信噪比条件下算法的复杂度，可见改进的SCL算法比较原算法，相应的复杂度降低了很多。

表1不同译码复杂度统计

5 结 语

极化码是编码领域较新的一个课题，目前在国际上是一个研究的热点，代表了未来通信发展的一个方向。本文中在译码时分为两部分，前半部分通过SCL算法，加上CRC校验，选出一条概率乘积大的路径；后半部分把L固定为1，降低复杂度，同时性能上也与原算法近似。在后半部分算法的复杂度从O(LNlogN)降为O(NlogN)。本文所提出的前半部分利用CRC校验选取最优路径，后半部分抛掉多余路径精简算法，降低译码复杂度，仿真结果表明，本算法可以在相对较低复杂度下保持极化码在中短码长的性能。

[1] ARIKAN.E. Channel polarization: A method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels [J].IEEE Trans.Inf. Theory,2009,52(07):3051-3073.

[2] ARIKANE. Channel Combining and Splitting for Cutoff Rate Improvement [J].IEEE Trans. Inf. Theory, 2006,52(02):628-639.

[3] 李斌，王学东，王继伟.极化码原理及应用[J].通信技术，2012，45(10):21-23. LI Bin，WANG Xue-dong，WANG Ji-wei. Theory and Application of Polar Code[J]. Communications Technology,2012,45(10):21-23.

[4] Tal I,VardyA. List decoding of polar codes[C]. USA: IEEE ISIT 2011,2011:1-5.

[5] NiuK, chen K. CRC-Aided decoding of polar codes [J].IEEE Communications Letters,2012,16(10):1668-1671.

[6] Niu K, chen K. Stack decoding of polar codes [J].Electronics Letters,2012,48(12):695-697.

[7] Huang Z L, Diao C J, Chen M. Latency reduced method for modified successive cancellation decoding of polar codes [J].Electronics Letters,2012,48(23):1506-1506.

[8] Leroux C, Raymond C J, Sarkis G. Hardware implementation of successive-cancellation decoders for polar codes [J]. Journal of Signal Processing Systems,2012,69(3):305-315.

LI Chun(1989-),male,M.Sci.,mainly engaged in satellite communication technology.

童新海(1971—)，男，教授，主要研究方向为现代通信技术.

TONG Xin-hai(1971-),male, professor, mainly engaged in modern communication technology.

Modified Successive Cancellation List Decoding Algorithm for Polar Codes

LI Chun, TONG Xin-hai

(Institute of Communication Engineering, PLAUST, Jiangsu Nanjing 210007, China)

The decoding performance of polar codes successive cancellation (SC) algorithm could hardly match with that of traditional LDPC. The proposal of successive cancellation list (SCL) greatly improves the decoding performance,and thus is an important step to put the polar codes into practical application, and however, this algorithm is of high complexity and long latency.Modified SCL decoding algorithm aims to improve the finite-length performance of polar codes.This paper describes the decoding process with searching sequence of paths on code tree. This proposed algorithm can reduce the time and space complexity by reducing unnecessary path searching operations. Simulations indicate that the modified SCL decoding algorithm decreses the decoding complexity while approaching the performance of maximum likelihood (ML) decoding algorithm.

polar code; successive cancellation; maximum likelihood decoding; list decoding

10.3969/j.issn.1002-0802.2015.01.004

2014-08-13；

2014-12-08 Received date:2014-08-13；Revised date：2014-12-08

TN911.3

A

1002-0802(2015)01-0019-04

李 纯(1989—)，男，硕士，主要研究方向为卫星通信；