一种改进的短极化码球形译码算法

王 丹,刘星星,杜一舟

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

1 引 言

2009年土耳其教授Arikan提出了极化码[1],极化码被证明是在二元离散无记忆信道(Binary Input Discrete Memoryless Channel,B-DMC)中逼近香农极限的信道编码.在第5代移动通信系统的增强移动宽带应用场景中,由于极化码在短码上表现出较好的性能,与低密度奇偶校验码(Low Density Parity Check,LDPC)和Turbo码比较,极化码在短码上的性能增益可达1dB,因此极化码入选成为有效载荷相对较小的控制信道的信道编码方案.

串行消除(Successive Cancellation,SC)译码[1]算法是最经典的极化码译码算法之一,但由于SC算法的误码性能较差,于是对SC算法投入大量的研究,它衍生的算法主要有串行消除列表[2](Successive Cancellation List,SCL)算法和串行消除翻转[3](Successive Cancellation Flip,SCF)算法等.结合SCL算法和循环冗余校验码(Cyclic Redundancy Check,CRC)检错提出CRC辅助的串行消除列表[4](CRC Aided Successive Cancellation List,CA-SCL)算法进一步提升误码性能,目前CA-SCL已经成为5G新空口标准的基线算法,CA-SCL译码表现出良好的误码性能,然而CA-SCL在中等列表大小情况下无法达到最大似然(Maximum Likelihood,ML)译码的误码性能,随着列表数L的增大,CA-SCL算法的复杂度相当于L倍SC算法的复杂度,当列表数足够大时,CA-SCL的误码性能能够超过ML译码[5].为了进一步提升误码性能,学者第一次提出球形译码[6](Sphere Decoding,SD)通过提高复杂度来达到最大似然(Maximum Likelihood,ML)译码的误码性能,传统SD的复杂度通常表示为O(N3),引入CRC到SD中提出CRC辅助的球形译码[7](CRC Aided Sphere Decoding,CA-SD)算法通过增加极化码的距离谱进一步提升误码性能,文献[8,9]分别通过优化路径度量和半径约束来降低复杂度,但由于球的半径选择原因,SD的复杂度不可预料,若半径选择过大,候选路径增加使得复杂度提升,若半径选择过小,则SD不能得到ML估计,文献[10]提出了多重球形译码树搜索(Multiple Sphere Decoding Tree Searches,MSDTS)算法避免了半径选择的问题,从而进一步降低了复杂度,文献[11,12]提出及时确定冻结比特的欧氏距离的策略,并应用到MSDTS算法中有效地降低了译码延时.将不同的数据结构与SD相结合,提出列表球形译码[13-15]和堆球形译码[16]在性能损失较小的情况下实现较低的复杂度.虽然改进后的SD复杂度有所降低,但低信噪比下的误码性能仍然很差,抗噪声干扰能力弱,于是对低信噪比下SD的误码性能提升的研究有重要意义.

极化码中的比特翻转译码最早应用于SCF译码算法,根据对数似然比(Log-Likelihood Ratio,LLR)的绝对值构造比特翻转集(Flip Bits Set,FBS),通过翻转不可靠比特来纠错,文献[17-19]提出一些策略改善了构造比特翻转集的精确度.针对MSDTS算法在低信噪比下误码性能较差的问题,本文在传统的MSDTS算法基础上,引入比特翻转到MSDTS算法提出基于比特翻转的多重球形译码树搜索(Multiple Sphere Decoding Tree Searches Based on Bit-Flipping,BF-MSDTS)算法,通过计算不同候选路径的差异性构造比特翻转集,提出扩大半径搜索和翻转不可靠比特来提升译码性能,同时固定可靠比特降低扩大半径搜索增加的复杂度,并引入搜索终止准则减少译码过程中的复杂度,在增加少量复杂度的情况下大大提升短极化码的误码性能.通过仿真验证,在码率为0.25、信噪比为2dB时,与传统的MSDTS算法比较,约提升34.5%的复杂度得到1.63dB的误码性能增益.在码率为0.5、误码率为10-4时,与 CA-SCL算法比较,提升了0.41dB,与MSDTS算法比较,提高了1.17dB .虽然复杂度有一定的提升,但少量的复杂度可以忽略不计,且在较差的信道环境下大大提升了误码性能,增强了抗噪声干扰能力,其误码性能优于传统的MSDTS算法和CA-SCL算法.

2 极化码及球形译码算法

2.1 信道极化

信道极化是构造极化码的核心理论,先经过信道合并再经过信道分解得到可靠性不同的子信道.给定N个独立同分布的B-DMC信道W经过信道合并得到WN:CN→YN,CN为输入信号,YN为输出信号,信道合并的转移概率为:

(1)

(2)

(3)

(4)

(5)

2.2 极化编码

极化编码的过程一般分为3个步骤:1)信道极化得到N个可靠性不同的极化子信道;2)从N个极化子信道中选取K个可靠性最高的子信道,将长度为K的信息比特v在K个可靠性最高的子信道中传输,信息比特索引集合定义为A,剩下的N-K个冻结比特则在可靠性较低的N-K个子信道中传输,冻结比特索引集合定义为Ac,若i∈A,信息比特ui=vj,j∈{1,2,…,K},若i∈Ac,冻结比特ui=0,得到了极化编码前的序列u;3)构造生成矩阵GN.极化码的编码过程可以表示为:

c=uGN=uBNF⊗n

(6)

(7)

bi,j表示BN中第i行第j列元素.码长为8的极化码编码过程如图1所示.

图1 码长为8的极化码编码过程

2.3 球形译码算法

信号在二进制输入加性高斯白噪声(Binary Input Additive White Gaussian Noise,BI-AWGN)信道中传输时,极化码的ML译码等价最小化欧氏距离的问题,可以描述为:

(8)

(9)

(10)

gj,N表示生成矩阵GN中第j行第N列的元素,⊕表示模二和运算.接着译码后面的比特,定义第i个信息比特到第N个信息比特的欧式距离:

(11)

图2 信息比特长度k=4的SD过程

3 基于比特翻转的MSDTS算法

3.1 MSDTS算法

为了降低时间复杂度,文献[9]提出了球形译码早期的搜索终止准则,对于信息比特u只能取0或1,根据公式(9)得到第i个信息比特ui的最小欧氏距离:

dmin(ui)=min{(yi-1)2,(yi+1)2}

(12)

从而得到第1个信息比特到第i-1个信息比特的最小欧氏距离之和:

(13)

(14)

步骤1.对MSDTS算法所需的参数进行初始化,译码索引index=N,球的半径r2,可靠比特集合R以及Path=∅;

3.2 BF-MSDTS算法

由于传统的MSDTS算法在误码性能上不如CA-SCL算法,将比特翻转引入MSDTS算法,提出BF-MSDTS算法,通过翻转不可靠的比特进一步提升误码性能.将通过第P级球形译码树搜索得到的所有路径进行CRC校验,若CRC校验成功则退出译码过程,若所有路径都未通过CRC校验,当第P级球形译码树搜索得到未通过CRC校验的路径数超过一定数量时,计算第i个信息比特中1的概率:

(15)

概率为1或0说明第i个信息比特为可靠比特,根据概率更新可靠比特集合R:

(16)

为了降低复杂度,固定该比特的译码结果,避免了重复搜索可靠比特以及冗余的不可靠比特的节点访问带来的复杂度,图3比较了固定与不固定可靠比特的节点访问情况,其中黑色实线表示固定可靠比特的节点访问情况,黑色虚线表示不固定可靠比特的节点访问情况,其中u1和u2为可靠比特,明显减少了P+1级球形译码树搜索访问的节点数.

图3 固定信息比特后的MSDTS过程

重复上述过程直至到达设置的最大半径阈值.若最终CRC校验失败,得到了L条未通过CRC检验的路径,在这L条路径找出容易出错的比特并构造翻转集.本文提出差异性的概念确定不可靠的比特,通过翻转不可靠的比特进行纠错,L条路径中第i个信息比特中0和1的差异性可以描述为:

(17)

其中m0,i表示第i个信息比特ui=0的路径数,m1,i表示第i个信息比特ui=1的路径数,根据m0,i、m1,i估计一条较优的路径:

(18)

若m0,i=m1,i,则difference(i)=1,此时差异性最大,该比特为不可靠比特.difference(i)越大则说明第i个信息比特译码错误的概率越大,选取S个difference(i)最大的值对应的信息比特作为翻转集,在翻转集中按照difference(i)的大小进行降序排序.先对较优的路径进行CRC校验,校验失败则依次翻转不可靠的比特,直至CRC检验通过结束译码过程,当翻转集中所有信息比特都执行比特翻转操作之后仍未通过CRC校验视为译码错误.提出的BF-MSDTS算法流程框图如图4所示.

图4 BF-MSDTS译码算法流程框图

根据上述描述并结合图4中BF-MSDTS算法流程框图,算法步骤如下:

步骤4.根据公式(17)计算候选路径中每个信息比特的差异性difference(i),从大到小排序选取前S个构造翻转集FBS;

提出的BF-MSDTS算法,通过扩大半径搜索和翻转不可靠比特使得误码性能大大提升,同时采用搜索终止准则和固定可靠比特降低复杂度,可以解决低信噪比下MSDTS算法复杂度偏高时误码性能较差的问题.下面对提出的BF-MSDTS算法进行仿真验证.

4 仿真结果与分析

4.1 误码性能分析与仿真

本文应用高斯近似方法构造极化码,将极化编码后的序列c经过BPSK调制得到x=1-2c,通过BI-AWGN信道得到接收信号y=(y1,y2,…,yN),可以表示为y=x+z,z表示均值为0,方差为σ2的噪声.在5G应用场景中,控制信道的极化码编码方案采用中低码率进行编码,因此,在本部分中选择码率0.5或0.25进行仿真,码长N为64,码率为0.5采用CRC-11,其生成多项式为g(x)=x11+x10+x9+x5+1,码率为0.25采用CRC-6,其生成多项式为g(x)=x6+x+1.

将CA-SCL算法的列表大小设为32,提出的BF-MSDTS算法的翻转集大小设为10.图5表明码率为0.5情况下提出的BF-MSDTS算法与其他3种译码算法的BLER性能仿真.

图5 极化码的误码性能(N=64,R=0.5)

在低信噪比情况下,由于受到高斯白噪声的干扰较大,正确译码结果的欧氏距离会偏大,扩大半径能够增大搜索范围,使正确的路径在扩大后的半径范围内,从而提升误码性能,同时翻转不可靠的比特进一步提升误码性能,显然提出的BF-MSDTS算法的性能优于CA-SCL算法,当误码率为10-3时,提出的BF-MSDTS算法与CA-SCL的误码性能比较,提高了0.74dB.当误码率为10-4时,与CA-SCL算法比较,提高了0.41dB,与MSDTS算法比较,提高了1.17dB.在高信噪比情况下,与CA-SCL算法比较,误码性能的提升较小,由于高信噪比下正确译码结果的欧氏距离偏小,此时扩大较小的半径就能搜索到正确的路径,不需要通过翻转不可靠的比特提升性能.与传统的MSDTS算法比较,在高信噪比下仍然有不错的误码性能增益,当误码率为10-5时,有0.96dB的性能增益.

将CA-SCL算法的列表大小设为32,提出的BF-MSDTS算法的翻转集大小设为5.图6表明码率为0.25情况下提出的BF-MSDTS算法与其他3种译码算法的BLER性能仿真.

图6 极化码的误码性能(N=64,R=0.25)

在低信噪比情况下,当误码率为10-3时,提出的BF-MSDTS算法与CA-SCL的误码性能比较,提高了0.6dB.当误码率为10-3时,提出的BF-MSDTS算法与MSDTS算法的误码性能比较,提高了1.14dB.在高信噪比情况下,与CA-SCL算法比较,当误码率为10-6时,有0.18dB的性能增益,与MSDTS算法比较,当误码率为10-5时,有0.92dB的性能增益.

4.2 复杂度分析与仿真

在低信噪比情况下,显然CA-SCL的复杂度低于MSDTS和提出的BF-MSDTS算法,因为此时信道环境差,需要更大的半径才能搜索到正确的候选路径,同时需要比特翻转,导致复杂度较高.提出的BF-MSDTS算法随着信噪比的增加,复杂度逐渐降低,在高信噪比的情况下,此时可以更快找到正确的候选路径,降低了扩大半径搜索带来的复杂度,同时减少了比特翻转的复杂度,因此BF-MSDTS算法和MSDTS算法的复杂度会低于CA-SCL算法,当信噪比超过6.6dB时,提出的BF-MSDTS算法的复杂度低于CA-SCL算法,在信噪比为7dB时,BF-MSDTS算法与CA-SCL算法比较,误码性能接近的情况下复杂度减少了约20%.结合图6与图7,在信噪比为2dB时,与MSDTS算法比较,约提升34.5%的复杂度得到1.63dB的误码性能增益,有效地解决了MSDTS算法低信噪比下误码性能较差的问题.图7表明了码率为0.25的情况下提出的BF-MSDTS算法与其他3种译码算法的复杂度仿真.

图7 译码的复杂度分析(N=64,R=0.25)

5 结束语

为了改善传统的MSDTS算法在低信噪比下误码性能较差的问题,本文提出了BF-MSDTS算法,利用步进扩大半径搜索和翻转不可靠信息比特改善了低信噪比下的误码性能,同时运用搜索终止准则和固定可靠信息比特来降低复杂度,从而在复杂度提升不多的情况下大大提升了低信噪比下MSDTS的误码性能.结果显示,在码率为0.25、信噪比为2dB时,与MSDTS算法比较,约提升34.5%的复杂度得到1.63dB的误码性能增益.在码率为0.5、误码率为10-4时,与 CA-SCL算法比较,提升了0.41dB,与MSDTS算法比较,提高了1.17dB.显然提出的BF-MSDTS算法有效地解决了MSDTS算法在低信噪比下误码性能不如CA-SCL算法的问题.