一种自适应快速SSCL极化码译码算法*

王 玲，张治中，邓炳光

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

0 引 言

Arikan[1]首次提出极化码(Polar Code)，该码是人类已知的第一种能够被严格证明达到信道容量的信道编码方法；同时，他提出的连续消除(Successive Cancellation,SC)译码算法是第一个在Polar码中码长接近无穷时能实现信道容量的译码算法。然而，对于中等码长或短码长的编码，SC译码算法的纠错性能较差。

SC列表(Successive Cancellation List,SCL)译码通过从解码器生成的候选列表中选择码字解决了Polar码有限码长的译码问题[2]。文献[3-4]实现了多种组成节点的快速并行译码，包括R1(Rate-1)节点、R0(Rate-0)节点以及Rep(Repetition)节点等特殊节点，命名为简化连续消除(Simplified Successive Cancellation,SSC)译码算法以及简化SCL(Simplified Successive Cancellation List,SSCL)译码算法。文献[5]给出了SSCL译码路径分裂的精确边界，进一步减少了时间步数。研究发现，在循环冗余校验(Cyclic Redundancy Check,CRC)码的辅助下极性码的纠错性能优于目前最先进的低密度校验(Low Density Parity Check,LDPC)码和Turbo码[6-7]。尽管文献[8-14]提出的算法都一定程度改善了Polar译码性能，降低了时间复杂度，但随着5G商用的到来，国际移动通信标准化组织3GPP确定Polar码作为5G增强移动宽带(Enhanced Mobile Broadband,eMBB)场景的控制信道编码方案，其传统译码算法效率也很难达到5G高速率、低时延应用场景的需求。基于文献[15-20]Polar译码算法的研究可知，在能够保证满足一定译码纠错性能的前提下，5G eMBB控制信道场景亟待更优快速的译码算法。

本文在SSCL译码算法基础上提出基于路径度量(Path Metric,PM)的自适应SSCL译码算法，在不增加任何信道先验信息计算的前提下有效消除了译码过程的冗余计算，进一步提高了译码效率。

1 背景算法介绍

1.1 SC译码算法

图1 SC译码算法的二叉树表示规律

(1)

(2)

在硬件友好型计算中[18]，公式(1)可修改为

(3)

(4)

式中：⊕表示异或运算。在叶节点，根据下式判别译码输出[1]：

(5)

1.2 SCL译码算法

SCL译码算法提高了Polar译码在中短码长情况下的纠错性能，在SC译码算法的基础上增加每一层路径搜索后允许保留的候选路径数量，最大允许路径数为L。L越大，SCL译码性能越接近于最大似然译码，并且通过CRC校验辅助，SCL算法的性能得到了很大的提升。在SCL译码过程中，存在L条路径同时进行译码搜索，对于任意一条路径l∈{1,2,…,L}以及任意发送比特ui，i∈{1,2,…,N}，其对应的路径度量值定义如下[19]：

(6)

(7)

(8)

1.3 SSCL译码算法

SSCL译码算法对一些特定的码字提供了有效的译码方法，不再需要遍历完整个译码树，提高了译码效率。文献[5]提出了R0码(只含冻结比特)、R1码(只含信息比特)、Rep码(最后一位为信息比特，其余为冻结比特)的简化译码，文献[15]提出了SPC(Single Parity-Check)码(第一位为冻结比特，其余为信息比特)的简化译码。

对于R0极化码节点，其PM表示为[5]

(9)

对于R1极化码节点，其PM表示为[5]

(10)

式中：ηil表示节点信息比特的硬判决值。

对于Rep码节点，其PM表示为[5]

(11)

对于SPC节点，初始化PM表示为[5]

(12)

(13)

式中：αilmin为SPC节点中最不可靠位的LLR值。在完成最不可靠位译码之后，其余比特的PM更新表示为[5]

(14)

2 自适应SSCL译码算法

对于传统的SCL译码算法以及SSCL译码算法从2L条候选路径中筛选出L条保留路径，路径选择复杂，时间消耗大。为此，本文提出了一种简化的自适应路径选择算法，在不需要任何先验信息、相较SCL译码没有任何纠错性能损失的前提下，有效降低译码算法的排序复杂度，减少译码所需时间步数。文献[5]给出了与SCL译码性能相同的情况下SSCL译码路径分裂的精确边界。长度为Nv的R1节点中比特翻转次数t为[5]

t=min(L-1,Nv)，

(15)

将产生2t种译码结果。对于高可靠信道对应的节点，大部分翻转后子路径的正确概率都很低，需要在性能损失很小的情况下删除这些子路径。在这种情况下，上述算法路径分裂次数太多，排序复杂度太大。改进的自适应译码算法假定当前存在L条路径，其PM按照升序排列为PM1≤…≤PMl≤…≤PML，其每条子路径都包含原路径度量值PMl和比特翻转后的路径度量值PMl+|αl|。

(1)进行下一信息比特翻转时，首先判断PML-1′与PML的大小，大于PML的路径直接删除，小于PML时占位PML，然后比较排序，找到新的PML，再按l减小的方向依次判断。这样得出的L条路径一定是具有最小PM的L条路径。

(2)当进行到某一信息比特翻转，其翻转后的路径如果都没有入选前L条，则该节点译码结束。若此时R1码满足当前翻转次数小于min(L-1,Nv)，其翻转次数较文献[6]减少。

下面给出上述改进算法的理论分析证明。

(16)

(17)

该节点译码结束，后续比特无需翻转,因为一定存在

(18)

对于任意路径l，有

(19)

该算法有效降低了R1节点译码候选路径排序复杂度，减少了比特翻转次数，从而减少了译码时间步数。对于SSCL译码，特殊节点的路径选择复杂度很高，降低复杂度尤为重要。图2给出了R1码(L=4,Nv=4)第1次翻转具体算法实现过程，其余比特翻转PM比较选择方法一致。

图2 路径选择策略

图3给出了R1码(L=4,Nv=4)整个执行过程及结果。该R1码经过3次图2的比特翻转操作，比文献[6]提出的最小翻转次数减少了1次，一共经历了13次比较判决。对于L=4、Nv=4的R1码，该改进算法在最差情况下只需判决24次，而在传统排序算法中，都需Ω(NlgN)次比较。该改进自适应SSCL译码算法比特翻转次数不是固定值，但一定小于或者等于文献[6]提出的次数。同时，判决次数随着PMmax逐渐减少，不符合路径单次判决删除的可能性较大。

图3 R1码路径分裂规律(L=4,Nv=4)

在有序路径集合中，排名靠后的路径被保留的几率很小，因为它们的PM较大。此外，对于一个可靠性好的信道，所有的路径几乎不可能分裂，因为相加的LLR绝对值很大。因此，该算法可以通过严格的约束有效减少译码时间步数，从而降低译码延迟。算法伪代码如下：

input：当前L条路径升序排序集合W

output:译码输出L条PM最小的L条路径集合W

1 begin

3 flag=TRUE;

4 for(inti=1;i≤min(L-1,Nv) && flag;i--) do

5 flag=FALSE;

6 for(intj=L-1;j≥1;j--) do

9 else

12 flag=TRUE;

13 end if

14 end for

16 end for

3 实验结果与性能分析

为了衡量本文提出的自适应SSCL译码算法的性能，下面将从译码器的纠错性能和复杂度两个方面进行分析。

3.1 纠错性能比较

误块率是评价译码结果是否正确的重要参数。本节通过对不同译码算法进行仿真实验，得出各算法的译码纠错性能。仿真中采用二进制加性高斯白噪声(Additive White Gaussian Noise,AWGN)，调制方式为二进制相移键控(Binary Phase Shift Keying,BPSK) 调制。其中，N=1 024，编码速率R=1/2。图4给出了传统SCL算法、SSCL译码算法以及本文提出的自适应路径选择译码算法在不同列表长度L下的误块率(Block Error Rate，BLER)曲线，图5给出了文献[20]提出的Fast-SCL算法和自适应路径选择算法在不同列表长度L下的BLER曲线，图6给出了文献[14]提出的基于路径分裂搜索集快速SCL(Path Splitting Selecting-Search Set Fast Successive Cancellation List,PSS-SS-FSCL)算法及基于路径分裂决策函数快速SCL(Path Splitting Selecting-Decision Function Fast Successive Cancellation List,PSS-DS-FSCL)算法与自适应路径选择算法在不同列表长度L下的BLER曲线。

图4 传统SCL、SSCL算法与自适应SSCL算法的BLER性能比较

图5 Fast_SCL与算法自适应SSCL算法的BLER性能比较

图6 PSS-SS-FSCL、PSS-DS-FSCL算法与自适应SSCL算法的BLER性能比较

显然，对于同一译码算法，随着码长L的增加，BLER值减少，其纠错性能更好。简化后的SSCL译码算法与SSCL译码算法纠错性能一致，相对传统的SCL译码算法也几乎没有任何纠错性能的损失。因为文中的自适应快速译码算法基于最新的SSCL译码算法，仅改变了PM值的选择方式，仿真结果符合理论分析。同时，该算法与基于经验性的Fast-SCL算法相比，在信噪比较高的情况下，前者纠错性能更高；随着L增加，两者纠错性能差距更大。Fast-SCL译码算法在译码R1码时，仅考虑两比特翻转，随着L的增加或码长变长，纠错性能显著下降，仿真结果与实际分析结果相吻合。文献[14]给出了基于搜索集和决策函数的FSCL译码算法与传统SCL译码算法纠错性能基本一致的仿真结果，本文中仿真得出自适应SSCL算法与文献[14]中两种算法的译码纠错性能几乎一致，仿真结果与实际分析结果相吻合。

3.2 复杂度比较

本文提出的自适应译码算法可以有效降低译码算法的PM排序复杂度，减少译码时间步数，提高译码效率。在实际译码过程中，依赖码字本身的架构。表1给出了N=1 024、Eb/N0=2 dB的极化码在不同译码速率、不同L下，分别采用传统SCL译码算法、SSCL译码算法、文献[5]提出的Fast-SSCL译码算法、文献[14]提出的PSS-SS-FSCL算法和PSS-DS-FSCL算法以及本文提出的自适应路径选择译码算法所需的时间步数。

表1 不同译码算法所需时间步数(N=1 024，Eb/N0=2 dB)

从表1可以看出，传统的SCL译码及SSCL译码算法所需时间步数与码率有关，与列表长度L无关。文献[5]提出的Fast-SSCL算法所需时间步数与列表长度L和特殊节点比特个数有关。对于本文提出的自适应路径选择译码算法，其所需时间步数收缩了文献[6]的边界，但不同码字所需时间步数波动较大，受到码字结构影响大。同时，相对文献[14]提出的PSS-DS-FSCL算法，本文提出的自适应算法所需时间步数明显减少，而相对文献[14]提出的PSS-SS-FSCL算法，尽管在L较大时其所需时间步数差别较小，但是考虑到文献[14]提出算法都是基于算法前期设置搜索集及决策函数，一定程度上增大了算法复杂度，所以本文提出的自适应SSCL算法更优。综合图5可知，在信噪比高的场景下，随着PMmax不断变小，排名靠后的路径几乎不会保留，单次比较可直接删除子路径，降低排序比较复杂度，减少译码步数，从而提高译码效率。

本文提出的自适应SSCL译码算法，主要改善了译码复杂度，旨在不降低误码性能的前提下，提升其译码的效率，降低译码时间，能更好地应对5G高可靠性、低延迟的海量数据交互场景下的控制信道译码。5G时代的一些终端模拟器、路测仪表仪器等，对用户资源的灵活支持及时间颗粒的进一步缩短。物理下行控制信道承载下行控制信息是5G系统的调度核心。Polar译码作为PDCCH接收盲检处理中的重要一环，检测算法的复杂度高低及性能优劣直接影响着整个5G仪器系统的效率。

4 结束语

本文提出的基于路径选择的自适应SSCL译码算法，通过对码树路径分裂后的路径选择过程进行去冗余化计算，降低了PM排序复杂度，有效减少了译码时间步数，在性能和时延方面都超过了现阶段应用最广的SSCL译码算法和基于经验计算的Fast-SSCL译码算法。此外，它较基于先验消息计算阈值的译码算法更加灵活，复杂度更低。Polar码作为5G技术信道编码技术之一，随着5G 3D超高清视频等大流量移动宽带业务的发展，译码性能亟待优化。本文译码算法性能尽管较主流译码算法得到了显著提高，但是牺牲了信道利用率，因此如何提高信道利用率是未来工作的一个重点。