极化码自适应连续消除列表比特翻转译码算法

刘 伟，段红光

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

极化码(polar code)是第一类被证明在无限码长下利用连续消除(successive cancellation, SC)译码实现二进制输入无记忆对称信道容量的纠错码[1]。然而对于有限码长，采用SC译码算法的误块率(block error ratio, BLER)高于低密度奇偶校验(low density parity check code ,LDPC)码[2]。

比特翻转是另一种改进SC译码算法，SC-Flip译码算法最早在文献[6]中提出，采用对数似然比(log-likelihood ratio, LLR)的绝对值作为评估信息比特的可靠性指标，通过翻转不可靠比特来纠正译码错误；文献[7]基于SC译码产生的第1个错误估计分布，提出固定索引选择和增强索引选择来降低选择比特翻转索引的复杂度；文献[8]提出基于错误分布的分区串行消除比特翻转算法，可以纠正至少一个比特错误，并降低了计算复杂度；文献[9]提出了一种更为准确的判断信息位决策可靠性的方法，并在文献[10]中基于该可靠性度量方法提出了多比特翻转算法，然而文献[9-10]都需要对可靠性指标进行大量的排序来识别不可靠比特，导致较大译码延迟；文献[11]引入了一种渐进的多比特翻转SC译码算法，并且通过构造临界集(critical set, CS)作为比特翻转的索引集使用；文献[12]将比特翻转方法应用到SCL译码算法中，提出一种连续消除列表比特翻转(SCL flip, SCLF)译码算法，但该算法若要获得更好性能，则需要较大的L值，导致复杂度提高。为了降低其译码复杂度，本文提出了一种自适应连续消除列表比特翻转译码算法(adaptive SCLF, AD-SCLF)，该算法最初设置较小的L值，如果没有路径通过CRC校验，则迭代地增加路径保留数L，直到达到预设的最大值Lmax。

1 极化码基本原理

1.1 极化码构造

1.2 极化码译码

(1)

根据判决函数h判决比特ui

(2)

图1给出码长N=4时的SC译码树，该算法只保留一条路径，其中，黑色粗线表示经过SC译码后保留的路径，黑色节点表示被淘汰的节点。

SCL译码算法作为一种增强的译码算法，在译码算法中需要保存L条备选路径，以减少丢失正确路径的机会。根据文献[16]定义一个路径度量值(path metric, PM)为

(3)

在每次译码过程中，SCL的候选路径数量将成倍增加，在路径数量达到预设路径保留数L时，通过剪枝过程从列表中选择L条最佳路径，直到译码结束。译码结束后译码器将从列表中选择PM最小的路径作为译码输出。图2给出码长N=4，路径保留数L=2时的SCL译码树，其中，灰色路径代表被剪枝的路径。

图1 N=4时SC译码树Fig.1 SC decoding tree with N=4

图2 N=4和L=2时SC译码树Fig.2 SCL decoding tree with N=4 and L=2

1.3 SC-Flip算法和SCLF算法

SC-Flip译码算法的核心思想是由于SC译码过程中导致错误传播的第1个比特的判决错误总是由信道噪声引起的[6]，故如果能够识别并纠正(翻转)该比特决策，则可以提升译码性能。文献[11]将极化码按照完全二叉树进行转换，根据得到的可靠性位置，将最后一级子节点按照可靠性位置进行标记，接着标记父节点，若子节点都是黑色则父节点标记黑色，若都是白色则标记白色，若一白一黑则标记灰色，如图3。基于该结构构造一种CS来识别第1个判决错误的比特，CS是通过选择每个“速率为1”的节点中的第1个信息位的索引作为其元素。例如在图3中，当N=8时，CS={4，6，7}，这些索引位于虚线框中。文献[12]中提出CS中对应的信息比特往往是最不可靠的比特，可能是SC译码过程中引起错误传播的第1个错误比特，并且验证了第1个错误比特在CS集中的概率高达100%。

图3 N=8时极化码的临界集Fig.3 Critical set of polar codes with N=8

SCLF算法基于SCL算法提出，将比特翻转引入到SCL中，指出SCL译码中有3种分裂状态的路径，即“克隆状态”、“删除状态”和“SC状态”，并确定“SC状态”的路径可以用于比特翻转。但是适用于SC-Flip算法的临界集并不适用于SCLF算法，故文献[12]通过删掉部分不能用于比特翻转的位置，重新获得修正后的临界集(revised critical set, RCS)来表示比特翻转的位置，表示为

(4)

SCLF算法采用CRC-Polar级联的方法。当SCL译码完成后，使用CRC校验当前译码结果，如果CRC校验成功，表示SCL译码成功并终止。如果CRC校验失败，将处于“SC状态”的路径进行比特翻转，并开始重新再次尝试SCL译码，在尝试译码时，所选择翻转不可靠比特ui进行反向决策，即如果在第1次译码失败时ui=0(1)，在翻转译码时ui被设置为1(0)。在每次SCL译码尝试结束时进行CRC校验，直到CRC校验成功为止。

2 AD-SCLF译码算法

AD-SCLF译码算法通过动态选择路径保留数的方法，在中高信噪比时能大大减小路径保留数，但同时需要解决在进行比特翻转时的2个问题，即如何从失败的路径中识别出最佳翻转路径，以及如何从最佳翻转路径中识别出最佳翻转的位置。

2.1 翻转路径

根据(3)式可进一步改写为[16]

(5)

2.2 翻转位置

文献[11]采用CS寻找不可靠决策位置，一旦置信序列确定，那么CS也将确定，文献[12]提出改进的RCS，即删除掉部分不能用于翻转的位置，从而降低复杂度，提高译码性能。SC-Flip译码根据其LLR的绝对值排序作为翻转位置。该准则中LLR绝对值可以表示为

(6)

本文设计了一种结合RCS与度量值M(ui)的方法，将RCS中的元素通过对应的LLR绝对值进行排序得到RCS′，并选取其中前T个最小M(ui)对应位置作为翻转位置，然后根据新判决函数h′进行判决

(7)

2.3 AD-SCLF算法

AD-SCLF算法是通过动态规划路径保留数，从预设最小路径保留数开始进行译码。当该路径不能正确译码输出时，则进行SCLF译码，当进行T次比特翻转的译码尝试后也不能输出正确译码时，则增大路径保留数，直到达到预设路径保留最大值。具体算法流程如图4。

根据算法流程图，当路径保留数L=1时，图4中SCL算法即为SC算法，SCLF算法即为SC-Flip算法。编译码具体实现步骤如下。

图4 AD-SCLF算法流程图Fig.4 Algorithm flow chart of AD-SCLF

步骤1利用高斯近似法(DE-GA)生成置信序列，将信息比特与冻结比特混合进行极化编码；

步骤2设置初始路径保留数L=1以及最大路径保留数Lmax；

步骤3利用SCL进行译码(当L=1时即为SC译码)，将L条输出路径进行CRC校验，若存在至少一条输出路径通过CRC校验，则直接执行步骤6，否则执行步骤4；

步骤4在失败的路径中选择最小PM值对应的路径，作为SCLF翻转的路径(当L=1时即为SC-flip)，依次翻转临界集RCS′的前T个比特位置分别进行T次译码尝试，将L条输出路径进行CRC校验，若至少存在一条输出路径通过CRC校验，则直接执行步骤6，否则执行步骤5；

步骤5增大扩展路径保留数L，即L=2·L，若L≤Lmax，则返回步骤3，否则返回译码失败并结束译码；

步骤6选择通过CRC校验的路径作为译码输出，返回译码成功并结束译码。根据置信序列取出信息比特并去除CRC校验比特，得到净信息比特，进行误码统计。

3 仿真分析

3.1 参数设置

本文仿真分别在AWGN信道和瑞利(Rayleigh)信道下进行，SCLF算法和AD-SCLF算法均采用12位CRC校验，生成多项式为g(x)=x12+x11+x3+x2+1，2种算法的最大允许比特翻转数为32。

设置初始路径保留数为1，相当于SC译码算法。为了对算法性能进行仿真对比，分别采用N=256和N=512码长，且在每一个码长下设置3种最大路径保留数Lmax=4，Lmax=8和Lmax=16。文中涉及其他参数如表1。

表1 仿真参数

3.2 性能分析

图5和图6分别给出在AWGN信道下，码长N=256和N=512时，SCLF算法和AD-SCLF算法的BLER性能比较；图7和图8分别给出在Rayleigh信道下，码长N=256和N=512时，SCLF算法和AD-SCLF算法的BLER性能比较。仿真结果表明，在AWGN信道和Rayleigh信道下，本文提出的AD-SCLF算法的译码与SCLF算法在同一路径保留数 (L=Lmax)下曲线接近重叠，表示BLER性能相当。

图5 高斯信道下AD-SCLF和SCLF的BLER性能比较(N=256)Fig.5 BLER performance comparison of AD-SCLF and SCLF over AWGN channel (N=256)

图6 高斯信道下AD-SCLF和SCLF的BLER性能比较(N=512)Fig.6 BLER performance comparison of AD-SCLF and SCLF over AWGN channel (N=512)

图7 瑞利信道下AD-SCLF和SCLF的BLER性能比较(N=256)Fig.7 BLER performance comparison of AD-SCLF and SCLF over Rayleigh channel (N=256)

图8 瑞利信道下AD-SCLF和SCLF的BLER性能比较(N=512)Fig.8 BLER performance comparison of AD-SCLF and SCLF over Rayleigh channel (N=512)

3.3 复杂度分析

图9 高斯信道下AD-SCLF和SCLF的复杂度对比(N=256)Fig.9 Complexity comparison of AD-SCLF and SCLF over AWGN channel (N=256)

图10 高斯信道下AD-SCLF和SCLF的复杂度对比(N=512)Fig.10 Complexity comparison of AD-SCLF and SCLF over AWGN channel (N=512)

图11 瑞利信道下AD-SCLF和SCLF的复杂度对比(N=256)Fig.11 Complexity comparison of AD-SCLF and SCLF over Rayleigh channel (N=256)

图12 瑞利信道下AD-SCLF和SCLF的复杂度对比(N=512)Fig.12 Complexity comparison of AD-SCLF and SCLF over Rayleigh channel (N=512)

4 结束语

针对SCLF译码算法需要较大路径保留数带来译码复杂度增加，本文提出一种自适应的SCLF算法，其路径保留数可以随着信噪比的增大而减小，从而降低平均复杂度。通过在AWGN信道和Rayleigh信道下仿真分析可知，在中高信噪比条件下，本文提出的AD-SCLF译码算法在不影响译码性能的条件下降低SCLF译码算法的复杂度。