基于SCL译码复杂度的改进算法设计*

李怡超，葛万成

（同济大学 中德学院，上海 200092）

0 引 言

为满足人们对数据传输的需求，优化与改进对数据编码方式十分重要。连续删除列表（Successive Cancellation List，SCL）译码算法是一种改进的递归连续删除（Successive Cancellation，SC）译码算法[1]。众所周知，极化编码（Polar Code）在码长趋于无穷时，信道极化才越完全。但是，在有限码长下，由于信道极化并不完全，依然会存在一些信息比特无法被正确译码[2]。当前i-1个信息比特的译码中发生错误后，由于SC译码器在对后面的信息比特译码时需要用到之前的信息比特的估计值，将导致较为严重的错误传递，且无法对错误进行修改。针对SC译码算法的缺点，一个直接的改进方案是增加每一层路径搜索后允许保留的候选路径数量，从仅允许选择“最好的一条路径进行下一步扩展”改为“最大允许选择最好的L条路径”进行下一步扩展，其中L≥1。然而，SCL算法会大大增加编码复杂度。本文的主要研究内容为通过设置a1和a2两个阀值，在不影响性能的前提下降低算法复杂度。

1 连续删除列表译码算法

连续删除列表（Succesive Cancellation List，SCL）译码算法中有一个参数L，被定义为列表大小。正如SC算法，对每一个信息比特，它将会把当前的译码路径分列为两条新的路径（一条定义为“0”，另一条为“1”）。当路径数增长到一个已定阀值L时，它将会删除最差的几条路径，仅保留最佳L条路径。例如，图1中，假设列表大小为4且所有的比特都是不固定的，在译第3个信息比特时扩展了8条路径，如图1（a）所示。然后，按照计算每个路径度量（Path Metric，PM）值选择4条最佳路径（001，100，110，111），如图1（b）所示。译码列表算法继续译图1（c）中的第4个信息比特，现在又有了8条路径。所以，需要继续删除路径保持L=4条路径，如图1（d）所示。最终，得到码字（1001，1101，1110，1111）。当列表大小L=1时，实际上SCL译码算法相当于SC译码算法。

图1 SCL算法

其中，用每条路径的路径度量（Path Metric，PM）值来判定这条路径是好是坏。对于在i∈N层的每条路径L路径度量值被定义为：

即该路径所对应的译码序列的概率，实现时往往采用对数形式。所以，路径度量值可以随着译码过程递归更新为：

对数似然比（Log-Likelihood Ratio，LLR）在通信中常用于软解码，不管发送端发射比特1还是比特0，接收端都有可能误判。如果收到信号正确，正确判为0的概率与正确判为1的概率的比值就是似然比，对其取自然对数就是对数似然比，可表示为：

对于一个BiAWGN信道，输出yi对应的信道对数似然比LLR可以被表示为：

2 基于SCL译码复杂度的改进算法设计

2.1 基于LLR的方案设计

作为计算LLR的初始值，信道输出端的LLR可由式（4）计算得到。信道的LLR与信噪比相关，如果信噪比非常大、信道情况很好，相应的噪声方差σn2就很小。所以，信道LLR的绝对值很大。通过译码过程中LLR的不断更新，在算法的每次循环后得到的LLR的绝对值就会非常大。很明显，LLR越大，对信息比特的判决越可靠，因为对数似然比LLR是正确判为0的概率与正确判为1的概率的比值。如果LLR为正且值很大，代表着判为0的证据更为可靠；反之，如果LLR为负且绝对值|Li|很大，则代表着判为1的证据更为可靠。所以，在每次循环时可以不用按例计算每条路径的路径度量值后根据路径度量值得大小进行判决，而是可以尝试在每更新一次LLR后，当满足Li≥a1这一条件时直接进行一次硬判决，这样SCL译码的算法复杂度将会被强制降低。因此，需要找到最合适的阀值a1使算法的复杂度能够自适应BiAWGN信道的信噪比变化。

极端情况下，如果a1=∞，需要在译每个信息比特时都扩展路径，然后选择L条最有可能的路径，和原先的SCL译码算法相同。如果a1=0，则对于每一次循环，|Li|总是大于0，每个信息比特都需要进行硬判决，如同SC译码算法只有一条译码路径，对应的是完全没有噪声的信道传输。换句话说，带有未知参数a1的SCL译码的性能将会随着相应复杂度的降低而在某种程度上变差。

2.2 基于PM的方案设计

从路径度量值的式（2）可知，必须选择有最大路径度量值的路径对应的码字为译码序列。因为0＜Pr{uu1|y1Ni}＜1，所有的路径度量值PM(ui1)都是负的。当在主函数的每一次i循环时，当计算完L条路径的路径度量值PM=[PM0,…PML-1]后，对这些路径度量值从大到小进行排列，可以得到新的PM=[PM0,…PML-1]，然后计算前后两个路径度量值的差值d=[d1,…dL-1][3]。现在设置一个未知参数a2作为阀值，如果dl∈d＞a2，则直接删去路径L后面的所有路径。

例如，设置a2=5，列表大小L=4，则如果d2=5，意味着PM1-PM2≥5，可以删除PM2和PM3对应的两条路径，保留PM0和PM1对应的两条路径继续计算。

同样，在这里讨论a2=0与a2=∞两种特例。当a2=0时，需要删除除了最大路径度量值的路径以外的所有路径，实际上就是SC译码算法，对应于完全没有噪声的信道传输。但是，当a2=∞时，不能删除任何路径，实际上等同于原有的SCL译码算法。因此，此设计方案中能够使复杂度随着信噪比的增大而降低。需要说明的是，未知参数a2的值的确定很重要，因为它将会影响SCL译码的性能。

3 仿真与分析

3.1 设计方案的仿真目标

综合考虑提出的两个方案，可以将a1和a2两个阀值设计在一个改进算法中实现。发现a1=0且a2=0代表了最坏的性能和相应最低的复杂度。当a1=∞且a2=∞时，可以得到最好的性能和最高的复杂度。很明显，这两种情况是改进后的SCL译码算法中的两个极限。仿真将通过对树搜索（Tree Searching）中的访问过的节点（Visited Nodes）的数量仿真来估计复杂度。

例如，假设待译码序列中有3个比特，且它们全是未固定比特，列表大小为L=4。所以，当a1=∞、a2=∞时，需要像图2一样扩展所有的路径，然后在这8条路径中选择L条最好的路径。很明显，访问过的节点的个数为14。但是，当a1=0、a2=0时，对每一个比特都进行了硬判决，如图3所示。最后，只有一条路径对应的码字为译码序列，假设为011。这种情况下只有3个访问过的节点，所以它的复杂度比上一张图的复杂度要低。

图2 a1=a2=∞时的路径树

图3 a1=a2=0时的路径树

下面给出在这两种极限情况下的Matlab仿真。

仿真参数的设置如下：N=1 024，L=16，code_rate=0.5。目标是根据给予的工作点（Operating Point）来优化a1和a2。a1和a2必须满足两个条件：一是改进后的性能必须要接近原SCL译码的性能，如图4所示；二是访问过的节点数量将会随着信噪比的增大明显减少，当信噪比特别大时，访问过的节点数量最终靠近SC译码算法，如图5所示。

图4 误码率对比

图5 访问节点数对比

3.2 数值结果分析

为了确定a1和a2的最佳阀值，现在挑选不同的a1和a2来仿真它们的性能和对应的访问过的节点数量。部分结果如图6、图7所示，不同的a1和a2的性能均在SC译码和原SCL译码两种极限之间。它们对应的访问过的节点数量均有不同程度的下降，且最终比较接近于SC译码的访问过的节点数量。

图6 不同参数设置的误码率对比

图7 不同参数设置的访问节点数对比

3.2.1 a2=15的仿真结果

首先，假设a2=15不变，在此基础上为a1选择一些变量来仿真，结果如图8、图9所示。其次，根据仿真结果画出在BLER=10-4处使用不同的a1的编码和原SC译码相比的信噪比增益，如表1所示。可见，只有当a1=5、a2=15时的性能比原SCL译码的性能差的比较明显。从表2中可以看出，a1越小，访问过的节点数量减少的程度越高。所以，a1越大，该译码的性能越好，同时需要访问的节点数越多。在通过权衡复杂度后，发现a1=15时，其性能与原译码规则基本相同，且大大减少了访问节点的数量。

图8 a2=15时误码率仿真

图9 a2=15时访问节点仿真

表1 BLER=10-4的信噪比增益

表2 在访问过的节点数为5 000处的信噪比增益

3.2.2 a1=10的仿真结果

在此仿真中假设a1=15，然后为a2挑选一些变量进行仿真，结果如图10、图11所示。观察仿真结果，在不同a2下的译码对比SCL译码在BLER=10-4处的噪声比增益和在访问过的节点为5 000的信噪比增益，如表3、表4所示。可以直观看到，当a1=10、a2=5时，所对应的译码性能最差；a2越小，复杂度越低。因此，认为a2=10是最好的选择，因为其在译码性能几乎不变的情况下，访问节点数大大减少。

图10 a1=10时误码率仿真

图11 a1=10时访问节点仿真

表3 BLER=10-4的信噪比增益

表4 在访问过的节点数为5 000处的信噪比增益

3.2.3 性能与复杂度权衡后的仿真结果

设置参数a1=15、a2=10。现在找到最优阀值a1和a2，使之能够很好地适应信噪比的增长。从表3可以看出a1=15、a2=10下的SCL译码相比于原SCL译码的误码率的损失。权衡性能与复杂度，如图12、图13所示的带圆圈的线段是a1和a2最佳选择的仿真结果。它对应的性能非常接近于原SCL译码的性能，且访问过的节点数量随着信噪比的增大明显减少。此外，电脑中此参数下的SCL译码算法译出一个块的码字的时间为0.001 4 s，原SCL的译码速度为0.026 s，几乎是SCL译码的20倍。

图12 a1=15、a2=10时误码率仿真

图13 a1=15、a2=10时访问节点仿真

如果SCL译码中存在一个工作点，如要求SCL译码算法将会在2.5 dB≤SNR≤3.5 dB工作，在这个范围中，SCL译码的甚至已经接近至SC算法的复杂度，且其误码率也可以保持和原算法相同。

4 结 语

本文基于对数似然比LLR和路径度量值，提出了一种译码复杂度可以随着信噪比增加而降低的改进的SCL算法。通过对算法的仿真分析，提出了最优化后的a1、a2值以及其工作点。改进后的算法可以适应信噪比的变化，且在信噪比高的情况下有较低的复杂度，使改进算法比原SCL算法在保证误码率的前提下，在算法复杂度上优势明显。