一种重复使用公共路径的SCL译码算法.pdf

2023 年第 7 期20计算机应用信息技术与信息化一种重复使用公共路径的 SCL 译码算法卢丽金1 莫洁安1LU Lijin MO Jiean 摘要 针对极化码的译码有时会出错且存在高译码复杂度的问题，提出一种基于重复使用公共路径的 SCL 译码算法。首先，从译码树的根节点出发，逐层往叶子节点层扩展路径，直至到达叶子节点层，并判断是否有能够重复使用公共路径的相关信息。然后，判断是否成功译码，若当前译码失败时，该译码器可以从第 T 层重新进行译码，若成功译码，对列表大小进行判断。最后，输出译码比特，退出译码，译码结束。实验结果表明，通过适当的设计，新提出的译码方法在中等和高 SNR 情况下显著降低了计算复杂度，且性能损失可忽略不计。关键词 极化码；SCL 译码；重复使用；复杂度；公共路径 doi：10.3969/j.issn.1672-9528.2023.07.0051.广西民族师范学院数理与电子信息工程学院 广西崇左 532200 基金项目 本文得到广西民族师范学院科研经费资助项目（项目编号：2020YB003）资助 0 引言基于一种称为信道极化的技术，极化码最初由 Arikan 提出1。近几年引起了广泛关注2-6。当码长趋于无穷大时，在具有低复杂度的串行抵消（successive cancellation,SC）解码器下，证明了极化码能够获得 B-DMC（binary-input discrete memoryless channel）的对称信道容量。B-DMC 的全称为二进制输入离散无记忆信道。尽管极化码能够逼近信道容量，但经验研究表明，在码长长度有限的情况下，基于 SC 译码的极化码，在性能方面比不上Turbo码或低密度奇偶校验（low density parity-check,LDPC）码。为了克服极化码的这一固有缺点，旨在增强极化码性能，几种译码方案已经被提出。据了解，在不增加码长的情况下，串行抵消列表（successive cancellation list,SCL）译码可以获得更好的纠错性能7-8，与最大似然（maximum likelihood,ML）的纠错性能尤为接近。以提高极化码的纠错能力作为切入点，各专家学者又提出了几种解码方法。极化译码有时也会出错。幸运的是，有的文献提出了具有循环冗余校验（cyclic redundancy check,CRC）码的级联 方 案（CRC-aided successive cancellation list,CA-SCL），而有的文献提出自适应串行抵消列表（adaptive successive cancellation list,AD-SCL）解码方法，以解决当前解码失败的问题9-10。然而，使用 CRC 级联来接近 ML 性能时所需列表大小（L）比没有级联时大得多。因此，对于如此大的列表，上述 SCL 解码器的复杂性将非常高。文献中解码过程总是从译码树的第一层开始译码，计算复杂性仍然不理想。将注意力集中在上述复杂性问题上，如果可以从译码树的某一层执行译码过程，那么将省去许多不必要的操作。所以，极化码译码的复杂度可以充分利用这个思路来降低。本文提出了基于重复使用公共路径的 SCL 译码算法。随着列表大小的增加，该算法的平均复杂度基本上不会呈现线性增加的现象。通过适当的设计，仿真结果表明，在保持与传统 SCL 译码相同的性能下，新提出的算法可以显著地降低复杂度。1 极化编码与极化译码1.1 极化信道的可靠性估计极化码编码时，很关键的一点是，对于 N 个分裂信道来说，其可靠程度一定要区分清楚。也就是说，要知道哪几个分裂信道是可靠的信道，哪几个分裂信道是不可靠的信道。每个极化信道的可靠性在极化码中占据着重要角色。一般地，可靠性的衡量能采用巴氏参数（Bhattacharyya 参数）的估算、密度进化（density evolution,DE）的计算或者高斯近似（Gaussian approximate,GA）的计算三种方法中的一种来实现。巴氏参数可以精确、低复杂度地测量二元删除信道的可靠性，但其计算复杂度在其他信道下会相当高。对于二进制输入对称信道，如果采用巴氏参数来估量其可靠性，将会产生高计算复杂度。二进制输入加性高斯白噪声信道也是如此。密度进化早已广泛应用于 Turbo 码和 LDPC 码的研究，可以可靠计算任意二进制输入对称信道的信道极化。密度进化算法的计算复杂度也非常高。究其原因为，对于每个消息的概率密 2023 年第 7 期21计算机应用信息技术与信息化度函数，DE 需要卷积计算才能得到。高斯近似是基于对密度进化的改进而得来的。同样，对于二进制输入加性高斯白噪声信道极化后所得到的极化信道，也可以采用高斯近似算法进行可靠性计算。1.2 极化编码给定码长N=8，信息序列长度K=4，编码速率R=0.5。在此，将以文字表述的形式简单阐明极化码编码的过程。用大写字母 A 来表示信息比特序号集合，4,6,7,8A=，用符号 Ac来表示固定比特序号集合，Ac=1,2,3,5。信息比特的集合为(i1，i2，i3，i4)，固 定 比 特 集 合 为（0，0，0，0），将(i1，i2，i3，i4)与（0，0，0，0）混合后得到序列81u=(0，0，0，i1，0，i2，i3，i4)。序列81u乘以生成矩阵得到序列88311vu F=，1011F=。图 1 所示结构示意图可以获得81v。将(1，2，3，4，5，6，7，8)对应的比特进行反序操作，得到（1，5，3，7，2，6，4，8）。再根据81v比特进行反序重排操作，最终得到编码比特序列81x。图 1 81x的实现结构示意图1.3 极化译码ML 路径在译码树某一层的扩展过程中容易丢失，这是SC 译码算法的缺点之一。一个直接的改进译码方案被提出。其实也就是在每一层进行路径搜索之后，对于允许保留的候选路径，应适当增加数量，满足L1。以SCL译码算法为例，L=1，简单阐述极化码译码的过程。将二进制比特序列映射为实数序列，映射关系为:1 01 1iiixsx+=若若xi为第 i 个二进制比特，0 或者 1。根据编码器输出得到:（s1，s2，s3，s4）=（-1，-1，+1，+1）对上述序列加以加性高斯白噪，得到接收信号 yiyi=si+ni噪声值 ni服从均值为 0，方差为 2的正态分布，各噪声值相互独立。本例设 2=0.5，噪声样值分别为：（n1，n2，n3，n4）=（-0.1，-0.6，-1.5，0.2）那么，经过信道后得到接收序列：（y1，y2，y3，y4）=（-1.1，-1.6，-0.5，1.2）每 个 码 字 比 特 的 对 数 似 然 比（Log-Likelihood Ratio,LLR）是根据接收序列计算出来的。LLR 如下：2Pr0|2()lnPr1|iiiiiiixyyzL yxy=（1）yi为接收信号，2为方差。通过上式计算得到（z1，z2，z3，z4）=（-4.4，-6.4，-2.0，4.8）当 L=1，SCL 译码中，初始化 zi，一条空路径存在于候选路径表中。该路径的度量（Path Metric,PM）值()0PM=。接下来，先对第 1 个比特相关的对数似然比进行计算，得到(1)441()(4.4,2.0)2.0Lyf=；然后再计算候选路径的度量值，1(0)2.0PM u=，1(1)PM u=；对候选路径的度量值进行比较，11(0)(1)PM uPM u=，只能留下一条路径，因此10u=被用作后续的路径扩展。对于第 2、3、4 个比特也是重复上述计算与操作，对应的幸存序列分别为 00、001、0010。最终选择序列0010作为译码结果输出。模拟结果表明，SCL 译码可以非常接近 ML 译码的性能，对于实际通信系统中涉及的码长，例如 1024，给列表大小 L 设置数值，只需要32，有可能甚至更小。2 重复使用公共路径的 SCL2.1 重复使用公共路径方案在极化码的不同译码过程中，可能会出现不同的译码结果。有些译码结果被验证是错误的，而有些译码结果被验证是正确的。从这些错误路径和正确路径中，分别随机地取出一条，为了便于分析，把这两条译码路径放在同一棵码树上表示，可以发现一个有趣的现象，从第一层到某一层，某两条候选路径是重叠的，把这一重叠部分的路径称为公共路径。极化码现有的译码算法，如经典的 SC 算法、SCL译码算法以及 AD-SCL 译码算法等，都存在公共路径的现象。针对这种现象，若当前译码失败需要再次进行译码时，要是能够省去公共路径的计算操作，重复使用公共路径，直接从某一层开始译码，这样便能实现显著降低译码复杂度的目的。以 CA-SCL 译码算法为例，本文做了一个实验。在加性高斯白噪声（additive white Gaussian noise,AWGN）信道上，先后进行 L=16 与 L=32 的 SCL 译码，然后分别取它们的一条最有可能的候选路径进行逐比特对比。在不同信噪比下，分别进行 10 000 次上述操作，并记录出现公共路径的次数和每次出现公共路径的长度。最后，计算公共路径的平均长度与 N 的比值，可以得到如表 1 的数值结果。当 L=16 的 CA-SCL 解码不能通过 CRC 时，如果省略公共路径的计算操作，从某个解码层开始重新解码，结合表 1，与文献 6 中的 SCL相比，本文预测在 SNR=1.75dB 时，复杂度将降低 95.6%。2023 年第 7 期22计算机应用信息技术与信息化表 1 不同信噪比下 SCL 译码方案的 Eb/No(dB)1.00.5661.250.8011.50.9011.750.9562.00.9622.2 重复使用公共路径的 SCL在即将提出的算法里，路径扩展差距度和可能会出现错码的译码层这两个指标是至关重要的。路径扩展差距度用P来表示。它是衡量能否重复使用公共路径的指标。一般地，路径度量表示的是该路径所对应的译码序列的概率，借助路径度量，扩展差距度可描述为:()()()()111111firstsecondfirstfirstsecondsecondii,l,liNiNr,l,lr,l,l PPM uPM u =ln P u|yln P u|y=1111firstfirstsecondsecondiNr,l,liNr,l,lP u|y =lnP u|y （2）其中，1 2firstl,.,L，1 2secondl,.,L，1,2,.,iN，firstl和secondl分别表示的是具有最大和次大路径度量值的候选路径的标号。利用公式（2），可以算出 P。根据以前的研究，能够发现错误比特可能出现在某一解码层。如果是初次出现误码的译码层，则该解码层的索引将由 T 表示，1,2,.,TN。T 的大小反映了公共路径的长度。借助公共路径，针对新算法提出以下三个原则：原则 1：路径扩展差距度 P 应满足minPP。minP表示路径扩展差距度的最小值。minP的大小通过自适应控制。原则 2：公共路径的长度应该足够长。如果公共路径长度太短，新译码方案的复杂性将不会显著降低。原则 3：当决定从第 T 层重新进行译码时，当前列表大小 L 应该变大 2 倍。当合理增加列表大小时，正确序列留在候选列表里的概率也会增大。从这一个角度也可以看出能获得更好的性能。本文提出了基于重复使用公共路径思路的译码方案，即 R-SCL（reusing-common-path successive cancellation list）算法。此算法可以重复使用公共路径，从第 T 层开始重新译码。新提出的算法与现有的 CA-SCL 译码在本质上是有明显区别的。新提出的算法的主要思想是：在 SCL 译码过程中，通过计算并判决 P，尽可能准确地找到可以进行重复使用的公共路径，并记录 T 的相关信息；当译码失败时，若 T 满足给定的条件，则返回到 T，令 L=2L,继续译码。基于重复使用公共路径的 SCL 译码算法的译码步骤为：（1）初始化。将列表大小初始化为 1，令 T=0。（2）逐层扩展路径。从译码树的根节点出发，逐层往叶子节点层扩展路径，直至到达叶子节点层。（3）判断是否有能够重复使用公共路径的相关信息。如果有，跳到步骤（5）；如果没有则计算路径扩展差距度 P。（4）判断路径扩展差距度 P。如果minPP，令T=i；否则令 T=0。（5）判断是否成功译码。如果成功译码则跳到步骤（8）；否则跳到步骤（6）。（6）判断 T 是否满足原则 2。如果满足则重复使用第一层到第 T 层的对数似然比，令 L=2L，直接从第 T 层开始继续译码；否则跳到步骤（7）。（7）判断 L 是否满足maxLL。如果是，令 L=2L，并跳回步骤（1）；否则跳到步骤（8）。（8）译码结束；输出译码比特，退出译码。基于重复使用公共路径的 SCL 译码算法的具体译码过程，如图 2 流程图所示。基于重复使用公共路径的 SCL 译码方案中，对于是否可以重复使用的公共路径，决策标准有点严格。为了确保译码结果足够理想，本文对 SNR 和判断条件提出了更高的要求。因此，基于重复使用公共路径的 SCL 译码算法适用于中等或高 SNR 的环境。此外，如果所提出的新译码方案不能通过 CRC 校验，可以检查是否处在低的 SNR环境中，将当前列表大小 L 放大 2 倍，并重新执行解码过程，直到成功解码或达到最大列表大小。图 2 R-SCL 译码算法流程图3 仿真分析极化码算法性能仿真的过程主要有三部分。第一个部分为发送端部分。首先是产生随机比特序列，即生成 0、1 等概率的二进制序列；然后添加 24 个循环冗余校验比特，使添加循环冗余校验比特后的序列长度为 512；接着进行极化码编码，编码比特序列的长度为 1024；最后进行二进制相移键控调制，根据映射规则进行二进制相移键控符号映射，得到调制符号序列。第二个部分为信道部分。将发送端得到的符号序列通过信道发送给接收端。此时的信道主要是加噪，模拟加性高斯白噪声信道的功能。第三个部分为接收端部分。接收端对接收符号序列进行极化译码，即采用 R-SCL 译码方案，得到长度为512的译码序列；去除译码序列中的24个循环冗余校验比特；2023 年第 7 期23计算机应用信息技术与信息化比较统计误块率（block error rate,BLER），对源比特序列和译码比特序列进行逐比特对比，返回不同元素的数量。图 3 从不同角度对各种译码方案的 BLER 进行了对比。码长为 1024，信息比特序列为 512，码率为 0.5。从图中可以看出，在不同信噪比下，SC 译码算法的 BLER 都是最大的，也就意味着 SC 译码算法的 BLER 性能最差。当 L1 时，CA-SCL 译码、AD-SCL 译码以及 R-SCL 译码的 BLER 性能总是比 SC 译码算法的好。当 L=4 时，CA-SCL 译码、AD-SCL 译码以及 R-SCL 译码的 BLER 曲线是堆叠在一起的；当L=32 时，CA-SCL 译码、AD-SCL 译码以及 R-SCL 译码的BLER 曲线也是堆叠在一起的。实验结果表明，在 L 相同的情况下，CA-SCL 译码、AD-SCL 译码以及 R-SCL 译码能够拥有相同的 BLER 性能。图 3 各种译码方案的 BLER 比较图 4 对各种译码方案的平均复杂度进行了对比。码长为1024，信息比特序列为 512，码率为 0.5，L=32。通过应用新译码方法，R-SCL 的计算复杂度可以显著降低，并且在中等和高 SNR 条件下非常接近 SC。当 SNR=2.252.5 dB 时，AD-SCL、R-SCL 与 SC 译码的平均复杂度曲线几乎是重叠在一起的。而 CA-SCL 译码的平均复杂度最大。实验结果表明，保证 BLER 性能不变，在中等和高 SNR 条件下，与 AD-SCL 译码相比，R-SCL 译码能够显著降低平均复杂度。具体地，当SNR=1.75 dB 时，新提出的算法能够降低约 25.4%的复杂度。4 结束语R-SCL 提出了重复使用公共路径的方案，若当前译码失败需要再次进行译码时，省去公共路径的计算操作，重复使用公共路径，直接从第 T 层开始译码，这样便能实现显著降低译码复杂度的目的。该算法通过重复使用公共路径，实现了显著降低译码复杂度的目的。仿真结果表明，在中等和高 SNR 条件下，与 AD-SCL 译码相比，R-SCL 译码能够显著降低平均复杂度且保证 BLER 性能不变。具体地，当SNR=1.75 dB 时，新提出的算法能够降低约 25.4%的复杂度。参考文献：1 ARIKAN E.Channel polarization:A method for constructing capacity-achieving codes for symmetric binary-input memoryless channelsJ.IEEE transactions on information theory,2009,55(7):3051-3073.2 TAL I,VARDY A.How to construct polar codesJ.IEEE transactions on information theory,2011,59(10):6562-6582.3 王华华,秦红等.极化码基于比特翻转改进的 BP 译码算法 J.光通信研究,2021(04):5-9.4 汪晓雅,席兵,高锦盟,等.一种 5G 系统自适应快速 SCL极化码译码算法 J.无线电工程,2022,52(05):807-813.5 王垚,王翔,杨国东,等.基于编码矩阵结构特征的非删余极化码参数盲识别算法 J.通信学报,2022,43(02):22-33.6 魏浩,张梦洁,王东明.6G 极化码低时延译码方案 J.移动通信,2022,46(06):64-71.7 TAL I,VARDY A.List decoding of polar codesJ.IEEE transactions on information theory,2015,61(5):2213-2226.8 CHEN K,NIU K,LIN J R.List successive cancellation decoding of polar codesJ.Electronics letters,2012,48(9):500-501.9 王琼,罗亚洁,李思舫.基于分段循环冗余校验的极化码自适应连续取消列表译码算法 J.电子与信息学报,2019,41(07):1572-1578.10 LI B,SHEN H,TSE D.An adaptive successive cancellation list decoder for polar codes with cyclic redundancy checkJ.IEEE communications letters,2012,16(12):2044-2047.【作者简介】卢丽金（1992），女，广西南宁人，硕士，主要研究方向为无线通信、信道编码。E-mail:。莫洁安（1989），通信作者（E-mail:），男，广东肇庆人，讲师，硕士，主要研究方向为：大数据、人工智能。（收稿日期：2023-03-10 修回日期：2023-04-28）图 4 各种译码方案的平均复杂度比较