一种基于深度学习预测的极化码路径移位SCL译码算法

田 浩,吴晓富,张索非

(1.南京邮电大学 通信与网络技术国家工程研究中心,江苏 南京 210003;2.南京邮电大学 物联网学院,江苏 南京 210003)

0 引言

极化码[1]已被证明在连续相消(Successive Cancellation,SC)译码下可以实现二进制对称信道容量。尽管如此,相对于最大似然译码的性能,码长较短的极化码在SC译码的条件下表现仍显不足。因此,为了提高极化码的译码性能,文献[2]提出了连续相消列表 (Successive Cancellation List,SCL) 译码。该方法在译码过程中保持L条译码路径,从而实现了高性能的译码。此外,文献[3]提出了一种基于循环冗余校验(Cyclic Redundancy Checksum,CRC)级联极化码的SCL译码方法(CRC-Aided SCL,CA-SCL),进一步提高了极化码的译码性能。

当CA-SCL译码器译码失败时,原则上可以使用各种Post-Processing方法来进一步提高译码性能,这些方法通常基于误码位置预测来启动多次译码过程,从而纠正前一次译码中出现的错误。SCL比特翻转译码算法(SCL-Flipping)[4-5]可以看作是一种基于SCL译码的Post-Processing方法,但SCL-Flipping为达到理想性能需要进行的重新译码次数一般在10次以上,这不仅提高了译码复杂度,也无法满足实际应用对译码低时延的要求。文献[6]提出了一种路径移位(Shifted-Pruning)SCL译码方法,也是一种Post-Processing算法,其与比特翻转不同的操作在于:采用路径移位的方式来重新捕获前一次译码中被淘汰的正确译码路径,该算法的最大重新译码尝试次数取决于关键位置集合(Critical Set)的大小。实验结果表明,在重新译码次数相同的条件下,路径移位译码算法的性能要优于比特翻转算法。在文献[7-8]的Post-Processing处理中,利用了首轮译码过程中生成的信息来预测译码错误的位置,其性能虽然得到了提升,但是未能充分利用第一次译码过程中生成的信息,性能距离理论界限还有较大的差距。

近年来,鉴于深度学习在计算机视觉和自然语言处理中的发展,人们开始研究将深度学习应用于提升极化码SC或SCL译码性能的可能性。长短时记忆 (Long Short-Term Memory,LSTM) 网络被用于SCL-Flipping的错误位置定位[9-10]。在文献[11]中,提出了一种具有两个可微分神经计算机(Differentiable Neural Computer,DNC)的深度学习辅助SCL-Flipping算法,其中一个DNC用于对多个比特翻转位置的排序,另一个DNC用于在比特翻转译码尝试中重新选择错误比特位置。然而,由于上述方法需要多次重新译码尝试,大大限制了其实际应用。

本文提出了一种基于深度学习预测的极化码路径移位SCL算法。核心思路是利用深度神经网络准确地预测SCL译码路径首次丢失的错误节点位置,并在此处激活偏移量为L的路径移位,以此来重新捕获被淘汰的正确译码路径。以码率1/2、码长128的极化码为例,在SCL-32的基础上,仅需要一轮额外的译码,其性能可以有效逼近该码长的有限长码性能界限。

1 极化码、SCL译码及其Post-Processing

1.1 极化码

通过上述编码过程,极化码可以实现信道极化的效果,将信息集中在部分位置上,使得在接收端进行解码时更容易恢复出原始信息。同时,通过适当选择冻结比特的位置,可以在传输过程中对抗信道噪声和干扰,提高通信系统的可靠性和性能。

1.2 SCL译码

(1)

对应信息位的ui+1判决由对数似然比值决定,即:

(2)

而冻结比特位置的ui+1一般默认为0,无需判决。

与SC译码不同,SCL译码[12]不仅是保留一条路径,而是动态维护一个大小为L的路径列表。当译码处于信息比特位置时,译码路径进行分叉,可能会导致维护的译码路径数量大于L。当译码路径数量大于L时,SCL译码器会根据最新的路径度量来筛选出L条最优路径,该路径度量值计算如下:

(3)

当集合A中所有的位置都已被访问过时,译码器会从存活下来的L条路径中选择路径度量值最小的作为最佳译码路径。对于CA-SCL译码器,只有通过CRC的路径才能作为译码路径,否则,视为译码失败。

1.3 SCL译码的Post-Processing方法

CA-SCL译码器能够通过CRC来判断译码器是否译码成功,当译码失败时,可以采用Post-Processing方法启动SCL再译码流程来提高译码性能。鉴于SCL译码的判决码字是按比特节点顺序译出,因此SCL的Post-Processing方法是在上一次SCL译码过程中的可能错误位置作路径修正从而再启动一轮新的SCL译码,具体流程如图1所示。图中,(a)为一般Post-Processing流程,(b)为本文所提方案。

图1 SCL译码的Post-Processing方法流程Fig.1 Post-Processing method flow for SCL decoding

首轮SCL译码将按照标准的译码流程执行,随后进行CRC。如果校验通过,则译码成功,译码流程结束;否则,则认为本轮译码失败。此时,对首轮译码所产生的中间过程信息进行分析,并根据译码置信度构造关键位置集合,并从中取出第一位元素,然后开启新的一轮译码。如图1中(a)所示,在后续译码过程中,与第一轮译码不同的是,当译码到达关键位置时,需要对该位译码结果做相应调整。当译码结果无法通过CRC时,无需再次构造关键位置集合,只需要从首轮构造的集合中按顺序取出相应元素。其他步骤均与首轮译码相同。

目前SCL译码主流的Post-Processing方法有比特翻转和路径移位两种。比特翻转是指在预测的错误位置处,对译码比特进行翻转;而路径移位方法有所不同,路径移位是指在当前位置处不保留前L条路径,而是保留第k～L+k条路径,其中k表示路径移位的大小。本文采用的Post-Processing方法即为路径移位,并且k取值为L。

2 基于深度学习的SCL译码错误位置预测

2.1 SCL译码错误位置预测技术进展

目前,文献中各种SCL译码的Post-Processing方法的主要差异是关键位置集合的选取[6-8]。文献[6-7]采用了2L条路径中的两条关键路径度量之差Δi来衡量当前信息位可靠性的方法,即:

(4)

文献[6-7]使用的方式有所不同,文献[6]采用的是一种不依赖于实时信道的方式,通过多次模拟来统计Δi-Δi-1的大小,当Δi-Δi-1<0时,则认为该比特位置i处译码置信度较低,故收集该比特位置作为关键位置集合的元素。但是该方法没有利用信道的实时信息,因此,性能提升有限。而文献[7]则直接利用Δi值来衡量信息位i的可靠性,Δi值越大,则认为该位置越可靠。因此,关键位置集合可以通过对Δi(i∈AA0)进行排序来确定,其中A0表示包含最小的lbL个信息位索引的集合。然而,当正确路径被淘汰时,后续的译码过程中容易出现错误传播现象,这通常会导致该方法的准确率降低。

文献[8]提出信息位ui(i∈AA0)的一种译码置信度:

(5)

式中:α≥1用于缓解误码传播效应。当α=1时,一旦SCL译码器在位置i1∈A处第一次淘汰了正确路径,由于译码的错误传播效应,后续的译码均会受到影响,下标位置越靠后(即i>i1,i∈A)影响越大。为了减小因错误传播带来的估计偏差,式(5)中的α可以适当增大。进一步地,Ei(α)值更小的信息比特下标i更容易成为译码错误位置。因此,文献[8]通过定位更小Ei(α)值的信息比特位置来构造关键位置集合。实验结果表明,与使用Δi的算法相比,使用Ei(α)来构造关键位置集合的Post-Processing方法性能更加优秀。

尽管现有的Post-Processing方法可以在标准SCL译码的基础上获得明显的性能提升,但距离短码的有限长理论界限仍存在相当大的性能差距。因此,如何充分利用第一次SCL译码期间生成的路径度量信息来准确预测正确译码路径首次丢失位置仍具挑战性。

2.2 基于深度学习的错误位置预测

在采用SCL-32进行极化码译码的过程中,当正确路径的路径度量值大于第L条最佳路径的路径度量值时,表明在当前信息比特索引下,正确的译码路径将被淘汰,从而导致SCL译码失败。

为了探究SCL译码路径首次丢失的错误节点位置的概率分布,本文使用蒙特卡洛仿真的方式来收集SCL译码失败的信息。(128,64+8,A)极化码在Eb/N0=2 dB条件下, SCL译码器译码路径首次淘汰的错误位置的概率分布如图2所示。该实验对传输全零码字和随机码字两种情况进行模拟,通过对5 000个译码错误的帧进行数据收集,可以总结出两个结论:

(a) 全零码字

(b) 随机码字

① 错误位置的总体概率分布几乎与传输的码字无关;

② 错误位置的分布非常不均匀,大约有一半的信息比特位置更容易出现错误。

在64+8=72个信息比特索引中,有30个位置没有监测到错误,这意味着实际会发生错误的位置的个数要小于所有信息比特的数量。

ie=fθ(Γ)∈A,

(6)

式中:fθ(Γ)表示具有参数θ的深度神经网络。实验中采用了修改版的ResNet-18作为网络模型fθ(·),其输入维度从H×W×C(高×宽×通道)调整为L×K×1,最终全连接层输出维度为K。本文使用Adam优化器进行模型的训练,完成预训练的模型fθ(·)可用于离线推理和预测。

2.3 基于深度学习预测的极化码路径移位SCL算法

使用深度学习方法预测译码错误位置后,可以采用Post-Processing方法进一步提高SCL译码性能。本文采用了译码路径移位的方法[6],当译码失败时,该方法首先通过深度学习模型对路径被淘汰的错误节点位置进行预测,并在该位置处重新选择被丢弃的L条路径,尝试找回正确路径。

如算法1所示,本文提出的基于深度学习预测的极化码路径移位SCL算法具体流程如下:当首轮的SCL译码失败(即CRC校验未通过)时,启动第二轮译码尝试(如图1(b)所示)。在这个过程中,将前一轮SCL译码所返回的路径度量张量Γ输入到预训练模型fθ(·)进行推理,从而得到正确译码路径首次被淘汰的位置的预测值,并在第二轮SCL译码过程中对该位置进行路径移位。需要注意的是,新一轮SCL译码在模型预测的位置处,之前被丢弃的L条路径将被重新选择,以便捕获正确的译码路径,从而改善SCL译码性能。

3 仿真结果

在仿真实验中,主要考虑码长N=128、码率为1/2的极化码,信息比特位置的集合A是由遗传算法[13]搜索得到,极化码译码采用CA-SCL译码器,其中8位循环冗余校验的生成多项式为x8+x7+x6+x5+x4+x3+1。实验中假定极化码字采用二进制相移键控(Binary Phase Shift Keying, BPSK)调制,在传输过程中经过加性高斯白噪声(White Gaussian Noise,AWGN)信道。需要注意的是,实验中涉及到的Post-Processing方法均在SCL-32译码器的基础上实现。

3.1 首次错误位置预测的准确率

为了收集用于深度学习模型fθ(·)训练的数据,对极化码的SCL译码进行了大量的仿真。当SCL译码器译码失败时,收集其路径度量张量以及译码路径首次淘汰的错误节点位置作为有标签数据。数据收集的信噪比Eb/N0为1.25～3 dB,每间隔0.25 dB取一次的数值。在每个信噪比点上采集了50 000组有标签数据用于构建训练数据集,以及5 000组有标签数据用于测试模型性能。因此,训练数据集共有50k×((3-1.25)/0.25+1)=400k个样本。模型的训练使用学习率为1×10-4的Adam优化器,并根据训练进度逐渐降低学习率。在训练过程中,数据输入的每个批次大小(batch size)设为1 024,最大训练迭代次数设为500。

图3展示了已经完成预训练的ResNet-18模型fθ(·)在不同信噪比下的预测精度。需要注意的是,经过训练的模型的预测准确性依赖于数据集收集的信噪比。如果模型工作的信噪比包含在训练数据集中,则其性能明显优于不包含在其中的信噪比。为了更加清晰明了,本文使用DL(w)和DL(w/o)来区分模型工作的信噪比是否包含在数据集收集的信噪比中。如图3所示,DL(w)可以达到约99%的准确性,而DL(w/o)的准确性约为56%。

图3 不同的Post-Processing方法首轮预测的准确率Fig.3 Accuracy of initial prediction in different Post-Processing methods

现有Post-Processing方案的主要不同之处在于关键位置集合的构建,关键位置集合的元素即为正确译码路径首次被淘汰的位置,通常使用某种可靠性度量进行确定,例如式(4)或式(5)。根据图3可以看出,基于深度学习预测的方法明显优于文献[7-8]中提出的两种方法。此外需要注意的是,上述两种方法在第一轮预测时的准确率都低于25%。

3.2 与现有Post-Processing方法的性能对比

图4对CA-SCL译码器采用Δi方法[7]、Ei(α)的方法[8]以及本文提出的方法(Post-Processing-DL)进行了比较。所有Post-Processing方法均在列表大小为SCl-32译码器上实施。T表示最大重新解码尝试次数。需要强调的是,所提出的Post-Processing-DL只进行一轮重新解码尝试,即T=1,而文献[7-8]中的后处理方案通常假定T≥1。

图4 不同Post-Processing方案译码性能对比Fig.4 Comparison of decoding performance in different Post-Processing schemes

由图4可以看出,当训练数据集中存在该方法所工作的信噪比时(Post-Processing-DL(w)),该方法的表现显著优于其他方法。对于其他信噪比处,Post-Processing-DL(w/o)的性能与采用Ei(α)(T=5)的方法相近。此外,本文提出的Post-Processing-DL(w)方法的性能甚至比SCL-128的效果更好,并且非常接近该短码的有限长理论界限[14]。

3.3 深度学习方法复杂度分析

基于深度学习辅助的Post-Processing会带来相当大的计算复杂性。由于深度学习模型前向推理过程需要进行大量的乘积累加运算,非深度学习方法在计算复杂性上具有明显的优势。尽管使用ResNet-18 模型可以准确预测错误位置,但不适合直接部署在可编程门阵列(Field Programmable Gate Array,FPGA)上。对于FPGA来说,更倾向于使用规模较小的模型。这个问题在文献[15-16]中有广泛讨论。文献[15]提出了SqueezeNet模型,在模型大小上有显著缩减,但性能损失不大。

为了减少计算负担并便于可能在FPGA上部署,实验中使用相同的数据集训练了一个SqueezeNet模型。表1为ResNet-18和SqueezeNet之间的对比。其中,MACCs指的是网络推理过程中的乘累加操作的数量,它以百万次(M)为单位进行计量,用于衡量网络推理的计算复杂度和性能。从表1中可以看出,通过使用SqueezeNet,模型的大小和复杂度显著减小,而预测准确率只有轻微的降低。

表1 ResNet-18和SqueezeNet预测准确率及复杂度对比Tab.1 Comparison of prediction accuracy and complexity between ResNet-18 and SqueezeNet

4 结束语

本文提出了一种基于深度学习预测的极化码路径移位SCL算法。相较于已有的Post-Processing方案,所提出的方法采用深度神经网络来预测SCL译码路径首次被淘汰的错误节点位置,神经网络模型采用预训练的方式,使用时可离线进行推理得出预测结果。使用神经网络来预测译码路径首次被淘汰的错误节点位置可以实现高效的Post-Processing,基本上只需进行两轮译码即可获得较大的性能提升,这与其他方案形成鲜明对比。本文提出的算法应用在SCL-32时,性能甚至比SCL-128表现更好。

本文所提出的算法虽然性能表现优异,但其落地应用仍存在一些值得进一步探讨的问题,包括开发适用于FPGA部署的小规模错误节点预测神经网络模型,以及如何提高该模型泛化能力,使得在无训练样本的信噪比范围内仍然能有效工作。