王 丹,劉星星,杜一舟

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

1 引 言

2009年土耳其教授Arikan提出了極化碼[1],極化碼被證明是在二元離散無記憶信道(Binary Input Discrete Memoryless Channel,B-DMC)中逼近香農(nóng)極限的信道編碼.在第5代移動(dòng)通信系統(tǒng)的增強(qiáng)移動(dòng)寬帶應(yīng)用場景中,由于極化碼在短碼上表現(xiàn)出較好的性能,與低密度奇偶校驗(yàn)碼(Low Density Parity Check,LDPC)和Turbo碼比較,極化碼在短碼上的性能增益可達(dá)1dB,因此極化碼入選成為有效載荷相對較小的控制信道的信道編碼方案.

串行消除(Successive Cancellation,SC)譯碼[1]算法是最經(jīng)典的極化碼譯碼算法之一,但由于SC算法的誤碼性能較差,于是對SC算法投入大量的研究,它衍生的算法主要有串行消除列表[2](Successive Cancellation List,SCL)算法和串行消除翻轉(zhuǎn)[3](Successive Cancellation Flip,SCF)算法等.結(jié)合SCL算法和循環(huán)冗余校驗(yàn)碼(Cyclic Redundancy Check,CRC)檢錯(cuò)提出CRC輔助的串行消除列表[4](CRC Aided Successive Cancellation List,CA-SCL)算法進(jìn)一步提升誤碼性能,目前CA-SCL已經(jīng)成為5G新空口標(biāo)準(zhǔn)的基線算法,CA-SCL譯碼表現(xiàn)出良好的誤碼性能,然而CA-SCL在中等列表大小情況下無法達(dá)到最大似然(Maximum Likelihood,ML)譯碼的誤碼性能,隨著列表數(shù)L的增大,CA-SCL算法的復(fù)雜度相當(dāng)于L倍SC算法的復(fù)雜度,當(dāng)列表數(shù)足夠大時(shí),CA-SCL的誤碼性能能夠超過ML譯碼[5].為了進(jìn)一步提升誤碼性能,學(xué)者第一次提出球形譯碼[6](Sphere Decoding,SD)通過提高復(fù)雜度來達(dá)到最大似然(Maximum Likelihood,ML)譯碼的誤碼性能,傳統(tǒng)SD的復(fù)雜度通常表示為O(N3),引入CRC到SD中提出CRC輔助的球形譯碼[7](CRC Aided Sphere Decoding,CA-SD)算法通過增加極化碼的距離譜進(jìn)一步提升誤碼性能,文獻(xiàn)[8,9]分別通過優(yōu)化路徑度量和半徑約束來降低復(fù)雜度,但由于球的半徑選擇原因,SD的復(fù)雜度不可預(yù)料,若半徑選擇過大,候選路徑增加使得復(fù)雜度提升,若半徑選擇過小,則SD不能得到ML估計(jì),文獻(xiàn)[10]提出了多重球形譯碼樹搜索(Multiple Sphere Decoding Tree Searches,MSDTS)算法避免了半徑選擇的問題,從而進(jìn)一步降低了復(fù)雜度,文獻(xiàn)[11,12]提出及時(shí)確定凍結(jié)比特的歐氏距離的策略,并應(yīng)用到MSDTS算法中有效地降低了譯碼延時(shí).將不同的數(shù)據(jù)結(jié)構(gòu)與SD相結(jié)合,提出列表球形譯碼[13-15]和堆球形譯碼[16]在性能損失較小的情況下實(shí)現(xiàn)較低的復(fù)雜度.雖然改進(jìn)后的SD復(fù)雜度有所降低,但低信噪比下的誤碼性能仍然很差,抗噪聲干擾能力弱,于是對低信噪比下SD的誤碼性能提升的研究有重要意義.

極化碼中的比特翻轉(zhuǎn)譯碼最早應(yīng)用于SCF譯碼算法,根據(jù)對數(shù)似然比(Log-Likelihood Ratio,LLR)的絕對值構(gòu)造比特翻轉(zhuǎn)集(Flip Bits Set,FBS),通過翻轉(zhuǎn)不可靠比特來糾錯(cuò),文獻(xiàn)[17-19]提出一些策略改善了構(gòu)造比特翻轉(zhuǎn)集的精確度.針對MSDTS算法在低信噪比下誤碼性能較差的問題,本文在傳統(tǒng)的MSDTS算法基礎(chǔ)上,引入比特翻轉(zhuǎn)到MSDTS算法提出基于比特翻轉(zhuǎn)的多重球形譯碼樹搜索(Multiple Sphere Decoding Tree Searches Based on Bit-Flipping,BF-MSDTS)算法,通過計(jì)算不同候選路徑的差異性構(gòu)造比特翻轉(zhuǎn)集,提出擴(kuò)大半徑搜索和翻轉(zhuǎn)不可靠比特來提升譯碼性能,同時(shí)固定可靠比特降低擴(kuò)大半徑搜索增加的復(fù)雜度,并引入搜索終止準(zhǔn)則減少譯碼過程中的復(fù)雜度,在增加少量復(fù)雜度的情況下大大提升短極化碼的誤碼性能.通過仿真驗(yàn)證,在碼率為0.25、信噪比為2dB時(shí),與傳統(tǒng)的MSDTS算法比較,約提升34.5%的復(fù)雜度得到1.63dB的誤碼性能增益.在碼率為0.5、誤碼率為10-4時(shí),與 CA-SCL算法比較,提升了0.41dB,與MSDTS算法比較,提高了1.17dB .雖然復(fù)雜度有一定的提升,但少量的復(fù)雜度可以忽略不計(jì),且在較差的信道環(huán)境下大大提升了誤碼性能,增強(qiáng)了抗噪聲干擾能力,其誤碼性能優(yōu)于傳統(tǒng)的MSDTS算法和CA-SCL算法.

2 極化碼及球形譯碼算法

2.1 信道極化

信道極化是構(gòu)造極化碼的核心理論,先經(jīng)過信道合并再經(jīng)過信道分解得到可靠性不同的子信道.給定N個(gè)獨(dú)立同分布的B-DMC信道W經(jīng)過信道合并得到WN:CN→YN,CN為輸入信號,YN為輸出信號,信道合并的轉(zhuǎn)移概率為:

(1)

(2)

(3)

(4)

(5)

2.2 極化編碼

極化編碼的過程一般分為3個(gè)步驟:1)信道極化得到N個(gè)可靠性不同的極化子信道;2)從N個(gè)極化子信道中選取K個(gè)可靠性最高的子信道,將長度為K的信息比特v在K個(gè)可靠性最高的子信道中傳輸,信息比特索引集合定義為A,剩下的N-K個(gè)凍結(jié)比特則在可靠性較低的N-K個(gè)子信道中傳輸,凍結(jié)比特索引集合定義為Ac,若i∈A,信息比特ui=vj,j∈{1,2,…,K},若i∈Ac,凍結(jié)比特ui=0,得到了極化編碼前的序列u;3)構(gòu)造生成矩陣GN.極化碼的編碼過程可以表示為:

c=uGN=uBNF?n

(6)

(7)

bi,j表示BN中第i行第j列元素.碼長為8的極化碼編碼過程如圖1所示.

圖1 碼長為8的極化碼編碼過程

2.3 球形譯碼算法

信號在二進(jìn)制輸入加性高斯白噪聲(Binary Input Additive White Gaussian Noise,BI-AWGN)信道中傳輸時(shí),極化碼的ML譯碼等價(jià)最小化歐氏距離的問題,可以描述為:

(8)

(9)

(10)

gj,N表示生成矩陣GN中第j行第N列的元素,⊕表示模二和運(yùn)算.接著譯碼后面的比特,定義第i個(gè)信息比特到第N個(gè)信息比特的歐式距離:

(11)

圖2 信息比特長度k=4的SD過程

3 基于比特翻轉(zhuǎn)的MSDTS算法

3.1 MSDTS算法

為了降低時(shí)間復(fù)雜度,文獻(xiàn)[9]提出了球形譯碼早期的搜索終止準(zhǔn)則,對于信息比特u只能取0或1,根據(jù)公式(9)得到第i個(gè)信息比特ui的最小歐氏距離:

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

(12)

從而得到第1個(gè)信息比特到第i-1個(gè)信息比特的最小歐氏距離之和:

(13)

(14)

步驟1.對MSDTS算法所需的參數(shù)進(jìn)行初始化,譯碼索引index=N,球的半徑r2,可靠比特集合R以及Path=?;

3.2 BF-MSDTS算法

由于傳統(tǒng)的MSDTS算法在誤碼性能上不如CA-SCL算法,將比特翻轉(zhuǎn)引入MSDTS算法,提出BF-MSDTS算法,通過翻轉(zhuǎn)不可靠的比特進(jìn)一步提升誤碼性能.將通過第P級球形譯碼樹搜索得到的所有路徑進(jìn)行CRC校驗(yàn),若CRC校驗(yàn)成功則退出譯碼過程,若所有路徑都未通過CRC校驗(yàn),當(dāng)?shù)赑級球形譯碼樹搜索得到未通過CRC校驗(yàn)的路徑數(shù)超過一定數(shù)量時(shí),計(jì)算第i個(gè)信息比特中1的概率:

(15)

概率為1或0說明第i個(gè)信息比特為可靠比特,根據(jù)概率更新可靠比特集合R:

(16)

為了降低復(fù)雜度,固定該比特的譯碼結(jié)果,避免了重復(fù)搜索可靠比特以及冗余的不可靠比特的節(jié)點(diǎn)訪問帶來的復(fù)雜度,圖3比較了固定與不固定可靠比特的節(jié)點(diǎn)訪問情況,其中黑色實(shí)線表示固定可靠比特的節(jié)點(diǎn)訪問情況,黑色虛線表示不固定可靠比特的節(jié)點(diǎn)訪問情況,其中u1和u2為可靠比特,明顯減少了P+1級球形譯碼樹搜索訪問的節(jié)點(diǎn)數(shù).

圖3 固定信息比特后的MSDTS過程

重復(fù)上述過程直至到達(dá)設(shè)置的最大半徑閾值.若最終CRC校驗(yàn)失敗,得到了L條未通過CRC檢驗(yàn)的路徑,在這L條路徑找出容易出錯(cuò)的比特并構(gòu)造翻轉(zhuǎn)集.本文提出差異性的概念確定不可靠的比特,通過翻轉(zhuǎn)不可靠的比特進(jìn)行糾錯(cuò),L條路徑中第i個(gè)信息比特中0和1的差異性可以描述為:

(17)

其中m0,i表示第i個(gè)信息比特ui=0的路徑數(shù),m1,i表示第i個(gè)信息比特ui=1的路徑數(shù),根據(jù)m0,i、m1,i估計(jì)一條較優(yōu)的路徑:

(18)

若m0,i=m1,i,則difference(i)=1,此時(shí)差異性最大,該比特為不可靠比特.difference(i)越大則說明第i個(gè)信息比特譯碼錯(cuò)誤的概率越大,選取S個(gè)difference(i)最大的值對應(yīng)的信息比特作為翻轉(zhuǎn)集,在翻轉(zhuǎn)集中按照difference(i)的大小進(jìn)行降序排序.先對較優(yōu)的路徑進(jìn)行CRC校驗(yàn),校驗(yàn)失敗則依次翻轉(zhuǎn)不可靠的比特,直至CRC檢驗(yàn)通過結(jié)束譯碼過程,當(dāng)翻轉(zhuǎn)集中所有信息比特都執(zhí)行比特翻轉(zhuǎn)操作之后仍未通過CRC校驗(yàn)視為譯碼錯(cuò)誤.提出的BF-MSDTS算法流程框圖如圖4所示.

圖4 BF-MSDTS譯碼算法流程框圖

根據(jù)上述描述并結(jié)合圖4中BF-MSDTS算法流程框圖,算法步驟如下:

步驟4.根據(jù)公式(17)計(jì)算候選路徑中每個(gè)信息比特的差異性difference(i),從大到小排序選取前S個(gè)構(gòu)造翻轉(zhuǎn)集FBS;

提出的BF-MSDTS算法,通過擴(kuò)大半徑搜索和翻轉(zhuǎn)不可靠比特使得誤碼性能大大提升,同時(shí)采用搜索終止準(zhǔn)則和固定可靠比特降低復(fù)雜度,可以解決低信噪比下MSDTS算法復(fù)雜度偏高時(shí)誤碼性能較差的問題.下面對提出的BF-MSDTS算法進(jìn)行仿真驗(yàn)證.

4 仿真結(jié)果與分析

4.1 誤碼性能分析與仿真

本文應(yīng)用高斯近似方法構(gòu)造極化碼,將極化編碼后的序列c經(jīng)過BPSK調(diào)制得到x=1-2c,通過BI-AWGN信道得到接收信號y=(y1,y2,…,yN),可以表示為y=x+z,z表示均值為0,方差為σ2的噪聲.在5G應(yīng)用場景中,控制信道的極化碼編碼方案采用中低碼率進(jìn)行編碼,因此,在本部分中選擇碼率0.5或0.25進(jìn)行仿真,碼長N為64,碼率為0.5采用CRC-11,其生成多項(xiàng)式為g(x)=x11+x10+x9+x5+1,碼率為0.25采用CRC-6,其生成多項(xiàng)式為g(x)=x6+x+1.

將CA-SCL算法的列表大小設(shè)為32,提出的BF-MSDTS算法的翻轉(zhuǎn)集大小設(shè)為10.圖5表明碼率為0.5情況下提出的BF-MSDTS算法與其他3種譯碼算法的BLER性能仿真.

圖5 極化碼的誤碼性能(N=64,R=0.5)

在低信噪比情況下,由于受到高斯白噪聲的干擾較大,正確譯碼結(jié)果的歐氏距離會(huì)偏大,擴(kuò)大半徑能夠增大搜索范圍,使正確的路徑在擴(kuò)大后的半徑范圍內(nèi),從而提升誤碼性能,同時(shí)翻轉(zhuǎn)不可靠的比特進(jìn)一步提升誤碼性能,顯然提出的BF-MSDTS算法的性能優(yōu)于CA-SCL算法,當(dāng)誤碼率為10-3時(shí),提出的BF-MSDTS算法與CA-SCL的誤碼性能比較,提高了0.74dB.當(dāng)誤碼率為10-4時(shí),與CA-SCL算法比較,提高了0.41dB,與MSDTS算法比較,提高了1.17dB.在高信噪比情況下,與CA-SCL算法比較,誤碼性能的提升較小,由于高信噪比下正確譯碼結(jié)果的歐氏距離偏小,此時(shí)擴(kuò)大較小的半徑就能搜索到正確的路徑,不需要通過翻轉(zhuǎn)不可靠的比特提升性能.與傳統(tǒng)的MSDTS算法比較,在高信噪比下仍然有不錯(cuò)的誤碼性能增益,當(dāng)誤碼率為10-5時(shí),有0.96dB的性能增益.

將CA-SCL算法的列表大小設(shè)為32,提出的BF-MSDTS算法的翻轉(zhuǎn)集大小設(shè)為5.圖6表明碼率為0.25情況下提出的BF-MSDTS算法與其他3種譯碼算法的BLER性能仿真.

圖6 極化碼的誤碼性能(N=64,R=0.25)

在低信噪比情況下,當(dāng)誤碼率為10-3時(shí),提出的BF-MSDTS算法與CA-SCL的誤碼性能比較,提高了0.6dB.當(dāng)誤碼率為10-3時(shí),提出的BF-MSDTS算法與MSDTS算法的誤碼性能比較,提高了1.14dB.在高信噪比情況下,與CA-SCL算法比較,當(dāng)誤碼率為10-6時(shí),有0.18dB的性能增益,與MSDTS算法比較,當(dāng)誤碼率為10-5時(shí),有0.92dB的性能增益.

4.2 復(fù)雜度分析與仿真

在低信噪比情況下,顯然CA-SCL的復(fù)雜度低于MSDTS和提出的BF-MSDTS算法,因?yàn)榇藭r(shí)信道環(huán)境差,需要更大的半徑才能搜索到正確的候選路徑,同時(shí)需要比特翻轉(zhuǎn),導(dǎo)致復(fù)雜度較高.提出的BF-MSDTS算法隨著信噪比的增加,復(fù)雜度逐漸降低,在高信噪比的情況下,此時(shí)可以更快找到正確的候選路徑,降低了擴(kuò)大半徑搜索帶來的復(fù)雜度,同時(shí)減少了比特翻轉(zhuǎn)的復(fù)雜度,因此BF-MSDTS算法和MSDTS算法的復(fù)雜度會(huì)低于CA-SCL算法,當(dāng)信噪比超過6.6dB時(shí),提出的BF-MSDTS算法的復(fù)雜度低于CA-SCL算法,在信噪比為7dB時(shí),BF-MSDTS算法與CA-SCL算法比較,誤碼性能接近的情況下復(fù)雜度減少了約20%.結(jié)合圖6與圖7,在信噪比為2dB時(shí),與MSDTS算法比較,約提升34.5%的復(fù)雜度得到1.63dB的誤碼性能增益,有效地解決了MSDTS算法低信噪比下誤碼性能較差的問題.圖7表明了碼率為0.25的情況下提出的BF-MSDTS算法與其他3種譯碼算法的復(fù)雜度仿真.

圖7 譯碼的復(fù)雜度分析(N=64,R=0.25)

5 結(jié)束語

為了改善傳統(tǒng)的MSDTS算法在低信噪比下誤碼性能較差的問題,本文提出了BF-MSDTS算法,利用步進(jìn)擴(kuò)大半徑搜索和翻轉(zhuǎn)不可靠信息比特改善了低信噪比下的誤碼性能,同時(shí)運(yùn)用搜索終止準(zhǔn)則和固定可靠信息比特來降低復(fù)雜度,從而在復(fù)雜度提升不多的情況下大大提升了低信噪比下MSDTS的誤碼性能.結(jié)果顯示,在碼率為0.25、信噪比為2dB時(shí),與MSDTS算法比較,約提升34.5%的復(fù)雜度得到1.63dB的誤碼性能增益.在碼率為0.5、誤碼率為10-4時(shí),與 CA-SCL算法比較,提升了0.41dB,與MSDTS算法比較,提高了1.17dB.顯然提出的BF-MSDTS算法有效地解決了MSDTS算法在低信噪比下誤碼性能不如CA-SCL算法的問題.