一種極化碼聯(lián)合SC球形列表譯碼算法

陳發(fā)堂，陳 洋，余永坤，鄭開放

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

0 引 言

2009年，基于信道極化定理(對于二進(jìn)制離散無記憶信道，通過信道聯(lián)合與信道分裂2個階段，信道產(chǎn)生極化，其中一部分信道容量趨近于1；另一部分則趨近于0)，Arikan提出一種新型信道編碼：極化碼。對信道容量趨近于1的部分信道輸入信息比特，其余部分則輸入凍結(jié)比特，從而在二進(jìn)制對稱信道下能逼近香農(nóng)限[1]。因此，自從極化碼的概念提出以來，在國際上引起了高度關(guān)注，于2016年，極化碼已成為5G通信增強(qiáng)移動寬帶(enhanced mobile broad band，eMBB)場景的控制信道編碼方案。

極化碼的經(jīng)典譯碼方案為串行消除(successive cancellation，SC)譯碼算法[1]，對信源比特逐位進(jìn)行估計后刪除其冗余的關(guān)聯(lián)信息，并將估計值作為先驗(yàn)信息代入之后的譯碼運(yùn)算，文獻(xiàn)[2-3]提出了一種極化碼SC譯碼碼樹節(jié)點(diǎn)分類分析方法，給出了一種簡化SC譯碼算法。但在實(shí)際應(yīng)用中，SC譯碼器譯碼性能有缺陷，較低密度奇偶校驗(yàn)碼(low density parity check，LDPC)和Turbo碼有一定的差距[4]。

為了提高極化碼譯碼性能，文獻(xiàn)[5]提出了一種性能更優(yōu)的串行消除列表(successive cancellation list，SCL)譯碼算法，當(dāng)列表尺寸LC足夠大時，SCL譯碼算法的誤碼性能接近最大似然(maximum likelihood，ML)譯碼。通常，ML譯碼采用球形譯碼(sphere decoding，SD)算法實(shí)現(xiàn)[6-7]，文獻(xiàn)[8]提出了球形列表(list sphere decoding，LSD)算法，使用廣度優(yōu)先搜索(breadth-first search，BFS)以保持LD條最小歐氏距離候選路徑，實(shí)質(zhì)上是通過犧牲譯碼性能來降低復(fù)雜度。雖然SD算法的性能較其他算法更優(yōu)，但是SD算法復(fù)雜度高，沒有實(shí)際應(yīng)用價值。文獻(xiàn)[9]提出將SCL和LSD譯碼聯(lián)合，而本文提出的極化碼聯(lián)合SC球形列表(joint successive cancellation sphere list，JSCSL)譯碼算法主要有3個優(yōu)勢：SCL譯碼和LSD譯碼2部分的計算復(fù)雜度更低；路徑抉擇方式不同，本文通過CRC校驗(yàn)的方式選擇路徑；中間分割點(diǎn)通過理論推導(dǎo)得出，以實(shí)現(xiàn)最優(yōu)的并行譯碼。

在本文中，為了在計算復(fù)雜度和譯碼性能方面尋找一個折中方案，提出了JSCSL譯碼算法，即從前往后和從后往前2個方向同時執(zhí)行SCL譯碼和LSD譯碼。仿真結(jié)果分析表明，與CA-SCL譯碼算法相比，JSCSL算法性能與其相近，但譯碼復(fù)雜度降低了40%～50%。

1 極化碼概述

1.1 極化碼編碼

碼長為N的極化碼編碼之前，首先將信道極化為N個二進(jìn)制離散無記憶信道，通過信道聯(lián)合和信道分裂2個階段，部分信道的信道容量趨近于1；另一部分信道的信道容量趨近于0。然后趨近于1的部分信道傳輸信息比特，其余部分信道則傳輸凍結(jié)比特，從而逼近信道容量。

1.2 SCL譯碼

(1)

根據(jù)文獻(xiàn)[1]中轉(zhuǎn)移概率函數(shù)的遞歸公式，可以得到LLR的遞推公式為

2tanh-1(tanh(α/2)×tanh(β/2))

(2)

為了降低SC譯碼器的運(yùn)算量，文獻(xiàn)[10-11]用最小近似法將LLR遞推公式簡化為

sign(α)sign(β)min(|α|,|β|)

(3)

(4)

在SC譯碼中，當(dāng)前的比特估計值高度依賴之前的譯碼估計結(jié)果，如果前面某一位的結(jié)果出錯，就會導(dǎo)致嚴(yán)重的錯誤傳遞，因此，一種基于SC譯碼的改進(jìn)算法被提出，即SCL譯碼算法[3]。SCL譯碼算法使用BFS的方式，從僅允許選擇“最好的一條路徑進(jìn)行下一步擴(kuò)展”改為“最大允許選擇最好的L條路徑進(jìn)行下一步擴(kuò)展”，當(dāng)搜索路徑L=1時，SCL算法退化為SC算法。為了進(jìn)一步提升譯碼性能，通過添加CRC校驗(yàn)的CA-SCL算法相應(yīng)地被提出[12]。

1.3 LSD譯碼

SD算法模型為

(5)

(6)

(6)式中，初始條件D(u(N+1))=0。因此，SD是找到具有最小歐氏距離的D(u(1))的葉子節(jié)點(diǎn)。SD譯碼中半徑r2的設(shè)定極為關(guān)鍵，較小的半徑值將導(dǎo)致修建所有的葉子節(jié)點(diǎn)，較大的半徑值將導(dǎo)致較少的有效修剪，從而不必要地增加訪問節(jié)點(diǎn)的數(shù)量，因此，多徑SD樹搜索被提出[8]，采用多個不同半徑值執(zhí)行樹搜索，半徑r2的計算表達(dá)式為

(7)

(7)式中：α為r2的擴(kuò)張步長；ω為擴(kuò)張次數(shù)，初始值為1。當(dāng)檢測過程在執(zhí)行第ω次樹搜索時，候選解小于列表大小LS，若半徑r2向外擴(kuò)張，則執(zhí)行(ω+1)次樹搜索，直到最后得到LS條候選解，如圖1。根據(jù)文獻(xiàn)[8]得知，半徑r2的最優(yōu)擴(kuò)張步長α為0.5。

圖1 多徑SD樹搜索(LS=4)Fig.1 Multipath SD tree search (LS=4)

2 JSCSL譯碼算法

本文提出的JSCSL譯碼算法在譯碼復(fù)雜度上比CA-SCL譯碼算法更優(yōu)，但與其譯碼性能接近。該算法的基本思想是對同一碼字，同時執(zhí)行SCL和LSD譯碼算法，待2種譯碼并行執(zhí)行完畢后，聯(lián)合其列表組合。這2種算法之間的共同點(diǎn)是都采用了BFS方式，不同點(diǎn)是譯碼路徑抉擇和譯碼順序：SCL譯碼算法是通過計算LLR獲得候選解，而LSD譯碼算法是通過計算與碼字的歐氏距離獲得候選解。

將長度為N的碼字{u1,u2,…,uN}，分割為2組{u1,u2,…,uM}和{uM,uM+1,…,uN}，由于SCL逐次譯碼的特點(diǎn)，所以從u1到uM采用SCL譯碼算法，與此同時，從uN到uM+1采用LSD譯碼算法，從而得到2個譯碼列表，然后通過CRC校驗(yàn)的方式將2個譯碼列表聯(lián)合，最終輸出滿足CRC校驗(yàn)的碼字。圖2展示了JSCSL譯碼流程，前M比特碼字采用SCL(L=LC)譯碼得到LC條路徑(Path1-PathLC)，后(N-M)比特碼字采用LSD(L=LD)譯碼得到LD條路徑(Path1-PathLD)，之后分別將LC條路徑和LD條路徑一一組合，待組合后的碼字滿足CRC校驗(yàn)，則輸出碼字結(jié)果。仿真結(jié)果分析表明，JSCSL譯碼算法在不損失譯碼性能的條件下，實(shí)現(xiàn)并行譯碼，降低譯碼復(fù)雜度。

圖2 JSCSL譯碼方案Fig.2 JSCSL decoding scheme

本文中，計算分割點(diǎn)M是根據(jù)SCL和LSD的復(fù)雜度完成，目的是使2種并行執(zhí)行的算法在相同時間內(nèi)完成，以實(shí)現(xiàn)最優(yōu)的算法復(fù)雜度。

首先是SCL復(fù)雜度的分析，根據(jù)SC譯碼算法的LLR遞推公式(3)，存在2種運(yùn)算因子：Type A，f(α,β)≈sign(α)sign(β)min(|α|,|β|)；Type B，g(α,β)=(-1)uα+β。“信息域”集合A的設(shè)定決定著Type A節(jié)點(diǎn)的個數(shù)N1和Type B節(jié)點(diǎn)的個數(shù)N2，對于列表排序采用冒泡排序算法。假設(shè)SACL，SMCL，SCCL為SCL譯碼過程中的加法次數(shù)，乘法次數(shù)和比較次數(shù)，分別表示為

(8)

LSD復(fù)雜度分析：根據(jù)(5)式，每一次i計算需要(N-i)次加法運(yùn)算和(N-i+1)次乘法運(yùn)算，ki為訪問的第i個比特位置，假設(shè)SADL，SMDL，SCDL為LSD譯碼過程中加法次數(shù)，乘法次數(shù)和比較次數(shù)，分別表示為

(9)

通過上述SCL和LSD復(fù)雜度分析，為了達(dá)到最優(yōu)的并行譯碼，讓2部分獨(dú)立譯碼在相同時間內(nèi)完成，則M值計算式為

(10)

分割點(diǎn)M理論分析的正確性，通過第3節(jié)仿真分析得以驗(yàn)證。根據(jù)上述的理論分析得出JSCSL譯碼算法完整譯碼流程如下。

初始化：

分割點(diǎn)M=Point_cal(nodeSCL,nodeLSD);

for i=1:LC

for j=1:LD

break;

end if

end for

end for

3 性能與復(fù)雜度分析

在本節(jié)中，對提出的JSCSL譯碼算法仿真結(jié)果進(jìn)行分析，在加性高斯白噪聲(additive white Gaussian noise，AWGN)信道下，采用的調(diào)制方式為正交相移鍵控(quadrature phase shift keying，QPSK)。

為了證明本文提出的JSCSL算法的性能，本節(jié)采取誤幀率(frame error rate，F(xiàn)ER)性能，以驗(yàn)證JSCSL算法給系統(tǒng)性能帶來的提升。同時也對SC，LSD，SCL和CA-SCL算法進(jìn)行了系統(tǒng)FER性能仿真和復(fù)雜度分析，以進(jìn)一步驗(yàn)證JSCSL算法的性能。

分別對(256,128)型和(1 024,512)型極化碼的FER性能仿真，并且將幾種不同譯碼算法性能進(jìn)行了仿真對比，如圖3和圖4。LSD，SCL和CA-SCL譯碼算法采用的搜索路徑數(shù)相同(L=4)，JSCSL譯碼算法中SCLpart和LSDpart采用的搜索路徑分別為LC=4和LD=4，(256,128)極化碼和(1 024,512)，根據(jù)各自的“信息域”集合A，分別計算得出M1=153和M2=533，并且設(shè)定CRC校驗(yàn)碼類型為CRC-24。

從圖3和圖4中可以看出，與SC，LSD和SCL算法相比，JSCSL譯碼算法可以顯著提高譯碼器的FER性能，例如在Eb/N0=2.2 dB時，圖3中分別約有7.2 dB，4.8 dB和2.7 dB的性能增益。隨著碼長的逐漸增加，給譯碼器帶來的增益會隨之增加。同樣在Eb/N0=2.2 dB，圖4中分別約有7.8 dB，5.7 dB和4 dB的性能增益。

圖3 碼長256時幾種譯碼算法誤幀率Fig.3 Frame error rate of several decodingalgorithms(256)

圖4 碼長1 024時幾種譯碼算法誤幀率Fig.4 Frame error rate of several decodingalgorithms(1 024)

通過對以上仿真結(jié)果分析得出，JSCSL算法譯碼器擁有顯著的性能增益，但是隨著碼長的增加，JSCSL算法較CA-SCL算法的性能將有所下降，但下降趨勢不明顯。例如在Eb/N0=2.2 dB時，圖3中JSCSL譯碼算法相對于CA-SCL譯碼算法約有0.2 dB，圖4中約有0.4 dB的性能損失。雖然JSCSL譯碼算法相比于CA-SCL譯碼算法有所性能損失，但是JSCSL譯碼算法增加了譯碼的并行性，大大降低了譯碼復(fù)雜度。

在(256，128)和(1 024，512)極化碼下，對JSCSL譯碼算法復(fù)雜性進(jìn)行分析，并且與其他幾種譯碼算法復(fù)雜性進(jìn)行了對比，如表1和表2。在譯碼階段，對加法器、乘法器和比較器3種運(yùn)算器進(jìn)行了次數(shù)的統(tǒng)計。

表1 碼長256時幾種譯碼算法運(yùn)算器次數(shù)

表2 碼長1 024時幾種譯碼算法運(yùn)算器次數(shù)

從表1和表2中可以看出，將JSCSL譯碼算法復(fù)雜性分為獨(dú)立的2部分：SCL part和LSD part，2部分使用運(yùn)算器總和相差不大，從而也驗(yàn)證了第2節(jié)中對分割點(diǎn)M值的理論推導(dǎo)。表1中JSCSL譯碼復(fù)雜度相比于SCL譯碼，CA-SCL譯碼和LSD譯碼分別降低了約為40%，40%和62%，表2中JSCSL譯碼復(fù)雜度相比于SCL譯碼，CA-SCL譯碼和LSD譯碼分別降低了約為46%，46%和67%。

通過對JSCSL譯碼算法的仿真結(jié)果和計算復(fù)雜度分析可知，JSCSL譯碼算法相對于LSD和SCL算法在性能和復(fù)雜度方面都有很大的增益，缺點(diǎn)是JSCSL譯碼算法中添加了CRC校驗(yàn)碼字，降低了譯碼有效性。與有效性相同的CA-SCL譯碼算法相比，在高信噪比條件下，雖然有0.2～0.3 dB的性能損失，但是在復(fù)雜度上降低了40%～50%。

4 結(jié)束語

本文提出的JSCSL算法是將碼字分為2部分獨(dú)立譯碼，增加譯碼并行性，從而達(dá)到降低譯碼復(fù)雜度的目的。通過對JSCSL譯碼算法的仿真結(jié)果和計算復(fù)雜度分析，JSCSL譯碼算法相比于LSD和SCL算法在性能和復(fù)雜度上都有很大的增益，但是損失了譯碼有效性。相比于CA-SCL譯碼算法，在信噪比高時，有輕微的性能損失，但在復(fù)雜度上降低了40%～50%，從而可以在復(fù)雜度和性能方面達(dá)到一個新的平衡。接下來需要研究的問題是，用硬件平臺(例如FPGA)并行實(shí)現(xiàn)該算法。