李桂萍, 李聰娜

(1.西安工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 陜西 西安 710021； 2.陸軍邊海防學(xué)院 科研處， 陜西 西安 710108)

極化碼(Polar Codes)[1]是理論上能夠證明可達(dá)信道容量限的一種編碼技術(shù)，其因具有規(guī)則的編碼結(jié)構(gòu)、明確的構(gòu)造方法以及低復(fù)雜的編譯碼算法而成為糾錯碼領(lǐng)域的研究熱點(diǎn)。在連續(xù)刪除譯碼算法SC(Successive Cancellation)下，當(dāng)碼長無限增大時，極化碼具有良好的漸進(jìn)性能。但是在短碼下，極化碼的性能卻是次優(yōu)的。針對這一問題，一些學(xué)者提出了許多改進(jìn)的SC譯碼算法，如連續(xù)刪除列表譯碼算法SCL(Successive Cancellation List)[2]、棧譯碼SD(Stack Decoding)算法[3]以及自適應(yīng)SCL譯碼算法[4]等。盡管在列表寬度或棧深度足夠大時，這些改進(jìn)譯碼算法能夠達(dá)到最大似然(Maximum Likelihood)譯碼的性能，但是它們都是基于串行譯碼機(jī)制的硬判決譯碼算法，無法滿足高輸出通信應(yīng)用的需求，也無法滿足磁記錄等場合對軟信息的需求。后來Fayyaz U U等在SC譯碼算法的基礎(chǔ)上提出了軟輸出連續(xù)刪除譯碼算法(Soft Cancellation, SCAN)[5]，解決了軟信息的輸出問題。本文針對SCAN算法，研究降低譯碼復(fù)雜度和空間復(fù)雜度的方法，以及如何提高譯碼性能等。

1 極化碼SC譯碼算法與置信傳播譯碼算法

(1)

上述過程中L0(0,i)表示譯碼器接收到的碼長為N的碼字序列中第i位的LLR值；Ln(i,0)為譯碼過程第n(這里n=logN,N為碼長)階段第i位的LLR值。式(1)中補(bǔ)集Ic表示固定位下標(biāo)集合，由于上述譯碼過程是基于極化碼因子圖[6-7](如圖1所示)執(zhí)行的，因此Ln(i,0)可通過式(2)或式(3)的遞歸計算得到。其中，因子圖上第λ(其中λ∈{0,1,…,n})列第φ(φ∈{0,…,2λ-1})組中第ω(ω∈{0,…,2n-λ-1})個節(jié)點(diǎn)的對應(yīng)似然值Lλ(φ,ω)的計算方法為：

當(dāng)φ為偶數(shù)時

Lλ(φ,ω)=Lλ-1(φ,2ω)ΔLλ-1(φ,2ω+1)

(2)

當(dāng)φ為奇數(shù)時

(3)

其中式(2)中符號Δ表示的運(yùn)算如式(4)所示：

(4)

Bλ-1(φ,2ω)=Bλ(φ-1,ω)?Bλ(φ,ω)

(5)

Bλ-1(φ,2ω+1)=Bλ(φ,ω)

(6)

圖1 碼長為8的極化碼對應(yīng)的因子圖

同SC譯碼算法相比，置信傳播BP(Belief Propagation)譯碼算法[8-10]的執(zhí)行也是基于因子圖對似然值進(jìn)行迭代更新的，但是更新內(nèi)容以及順序不盡相同。在BP 算法中因子圖上每個節(jié)點(diǎn)均傳輸兩種與LLR值相關(guān)的信息，即：Li,j和Ri,j。這里L(fēng)i,j表示因子圖上節(jié)點(diǎn)(i,j)向左傳播的LLR值；Ri,j為節(jié)點(diǎn)(i,j)向右傳播的消息，其中i=0,1,…,n表示列號，j=0,1,…,N-1表示行號。在BP算法執(zhí)行前，對因子圖上第一列節(jié)點(diǎn)的LLR值L0,j和最后一列節(jié)點(diǎn)的LLR值Rn,j進(jìn)行初始化，初始化L0,j的方法同SC譯碼算法；初始化Rn，j的方法為：當(dāng)j為信息位時，使Rn,j=0，否則Rn,j=∞ 。因子圖中某一個極化單元上各節(jié)點(diǎn)相關(guān)信息的兩種LLR傳播方向如圖2所示，圖中變量j0、j1、j2與j3分別表示相應(yīng)節(jié)點(diǎn)。向左和向右傳輸?shù)腖LR值更新規(guī)則分別如式(7)-式(10)所示。

BP譯碼算法每次迭代均包括從右向左和從左向右這兩個方向上的消息更新過程，且每個方向上的更新逐列進(jìn)行，但在每一列中可以并行更新相應(yīng)的消息。因此BP譯碼算法在每一次迭代中均需存儲N(logN+1)個LLRs值、在實數(shù)域上執(zhí)行2NlogN次的加法運(yùn)算和比較運(yùn)算[5]。

圖2 因子圖一個極化單元中各節(jié)點(diǎn)相關(guān)信息傳播方向 Li+1,j2=f(Ri+1,j3+Li,j1,Li,j0)

(7)

Li+1,j3=f(Ri+1,j2,Li,j0)+Li,j1

(8)

Ri,j0=f(Ri+1,j2,Ri+1,j3+Li,j1)

(9)

Ri,j1=f(Ri+1,j2,Li,j0)+Ri+1,j3

(10)

2 極化碼低復(fù)雜迭代SCAN譯碼算法

基于SC譯碼算法的SCAN算法與BP譯碼算法的區(qū)別是消息更新的時序不同，SCAN算法中對第i列的似然值Li,j或Ri,j更新時，并不是直接并行更新而是將該列的N個似然值分成2i組，逐次更新該組中的N/2i似然值。與BP譯碼算法相比較，SCAN譯碼算法在每次迭代中具有相同的計算復(fù)雜度，但收斂速度更快，且空間復(fù)雜度較低。本文基于原SCAN算法，通過改變左向LLR值和右向LLR值的更新時序提出了進(jìn)一步降低譯碼復(fù)雜度和空間復(fù)雜度的軟輸出譯碼算法。

2.1 通信傳輸模型設(shè)計

圖3 本文通信傳輸模型

2.2 本文算法基本原理

本文提出的改進(jìn)SCAN算法的基本原理如下：

首先根據(jù)列號i值將極化單元上的消息傳遞時序分為i=0與i>0兩種情況：①當(dāng)i=0、計算第1列的左向似然值L1,j3時，為了把所有行號j3+1為偶數(shù)的右向似然值帶入到下次的迭代過程中，在單元圖上計算L1,j3時仍采用原規(guī)則公式(7)，即L1,j3=f(R1,j3+1+L0,j2,L0,j1)，具體見圖4；②當(dāng)i>0且j為偶數(shù)時，由于前一階段的計算過程在實數(shù)域上保留了已計算似然值的總和，從而消除了Ri,j+1與Li,j之間的依賴性，這樣在后面的迭代中就不需再用每列中序號為偶數(shù)的右向LLR值，因此計算Li,j按照規(guī)則Li+1,j2=f(Li,j1,Li,j0)進(jìn)行更新，具體見圖5。

圖4 因子圖第1列左向LLR值更新規(guī)則

圖5 因子圖第1列后所有列左向LLR值更新規(guī)則

本文算法對軟信息的更新時序同原SCAN算法，仍按照SC譯碼的順序?qū)σ蜃訄D上的軟信息進(jìn)行更新。由圖4和圖5可知，實現(xiàn)本文算法不需為每一個節(jié)點(diǎn)分配存儲空間，因此具有較低的空間復(fù)雜度。

若令L表示維數(shù)為logN+1的向量，則L={L[0],L[1],…,L[logN]}，其中L[i]是維數(shù)為2logN-i的向量，用于存儲因子圖第i列左向LLR值。將所有的右向LLR值根據(jù)其j值分為奇數(shù)組R0={R0[0],R0[1],…，R0[n-1]}和偶數(shù)組Re={Re[0],Re[1],…,Re[n]}兩組。維數(shù)為2logN-i的數(shù)組R0[i]表示第i列中所有序號為奇數(shù)的右向LLR值；數(shù)組Re[1]表示第i列中所有序號為偶數(shù)的右向LLR值，維數(shù)也為2logN-i。在上述參數(shù)的基礎(chǔ)上，本文提出的改進(jìn)算法包括如下幾個重要的步驟：

步驟1，設(shè)置最大迭代次數(shù)iternum

步驟2，每一次迭代中，按順序j=0,1,…,N-1逐次更新左向LLR，并對右向LLR值進(jìn)行初始化：若j為偶數(shù)，且當(dāng)前位是固定位，則Re[j][0]=∞，否則設(shè)置Re[j][0]=0；若j為奇數(shù)，且當(dāng)前位是固定位，則R0[j][0]=∞，否則設(shè)置R0[j][0]=0，同時更新右向LLR。

上述步驟的實現(xiàn)過程如圖6所示，圖7為進(jìn)一步描述該算法的執(zhí)行流程。

在本文改進(jìn)算法中，需要對左向和右向傳播的LLR值進(jìn)行更新，具體更新算法為：

(1) 左向LLR值更新算法LLR(j,L,R0,Re)

輸入：j,L,R0,Re

步驟1，首先將j表示成logN位的二進(jìn)制形式

圖6 低復(fù)雜改進(jìn)SCAN算法主程序?qū)崿F(xiàn)過程

圖7 本文提出算法的執(zhí)行主流程

tlogN-1tlogN-2…t0，其中t0表示最低位。若j是非0偶數(shù)，從tlogN-1tlogN-2…t0最低位開始查找等于1的位，若存在k滿足tk+1=1(0≤k≤logN-1)且所有r≤k的tr均為0，則sj=logN-(k+1)；若j=0，則sj=1；若j為奇數(shù)(即此時t0=1)，則sj=logN，列號i=sj。

步驟2，對因子圖上第i列中前2logN-i個節(jié)點(diǎn)對應(yīng)的左向LLR值依次進(jìn)行更新。更新規(guī)則為:

L[i][k]=f(L[i-1][2k],L[i-1][2k+1]+R0[i][k]) 若j=0

(11)

L[i][k]=L[i-1][2k]+f(L[i-1][2k]+Re[i][k]) 若j>0

(12)

步驟3，分別對第i列之后的所有列逐次更新前2logN-i個節(jié)點(diǎn)對應(yīng)的左向LLR值：

L[i][k]=f(L[i-1][2k],L[i-1][2k+1])

上述左向LLR值更新函數(shù)LLLR(j,L,R0,Re)的程序?qū)崿F(xiàn)過程如圖8所示。

圖8 左向LLR值更新函數(shù)LLLR(j,L,R0,Re)的程序?qū)崿F(xiàn)過程

(2) 右向LLR值更新函數(shù)RLLR(j,L,R0,Re)

輸入：j,L,R0,Re

步驟1，從最右邊開始選取tlogN-1tlogN-2…t0中tk=0的最小整數(shù)k，計算ej=logN-k;若不存在這樣的k，則令ej=0。

步驟2，從第logN-1列到第ej+1列按序更新前2logN-i個下標(biāo)為奇數(shù)的節(jié)點(diǎn)對應(yīng)的右向LLR值

R0[i][2k]=f(Re[i+1][k],Re[i+1][k]+L[i][2k+1])

(13)

R0[i][2k+1]=R0[i+1][k]+f(Re[i+1][k]+L[i][2k])

(14)

其中l(wèi)ogN-1≤i≤ej+1。

步驟3，i=ej，對該列中前2logN-i個下標(biāo)為偶數(shù)的節(jié)點(diǎn)按式(15)和式(16)更新其對應(yīng)的右向LLR值：

Re[i][2k]=f(Re[i+1][k],R0[i+1][k]+L[i][2k+1])

(15)

Re[i][2k+1]=R0[i+1][k]+f(Re[i+1][k]+L[i][2k])

(16)

2.3 復(fù)雜度分析

由因子圖可知，BP譯碼算法需為每列LLR值分配N個存儲空間，因此空間復(fù)雜度為N(logN+1)；而原SCAN算法的空間復(fù)雜度則降低為4N-2+NlogN/2[5]。這兩種算法所需浮點(diǎn)運(yùn)算的復(fù)雜度均為2NlogN[5-7]。通過分析提出算法的主要流程，可計算出本文算法的空間復(fù)雜度已降至5N-3，浮點(diǎn)運(yùn)算復(fù)雜度為N(3logN+1)/2，與BP譯碼算法以及原SCAN算法相比減少了N(n-1)/2。因此，本文提出的改進(jìn)算法具有較低的空間復(fù)雜度和計算復(fù)雜度。

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

在二元加性高斯白噪聲信道下，選取碼長分別為1 024和4 096且碼率為0.5、0.7的極化碼，采用BPSK調(diào)制，比較了極化碼在SC譯碼算法、BP譯碼算法、原SCAN譯碼算法以及本文譯碼算法下的性能。

3.1 碼例為(1 024,512)的極化碼不同譯碼算法性能比較

從仿真結(jié)果可知(圖9)，利用本文譯碼算法在迭代次數(shù)為2時的極化碼具有與SC譯碼算法相當(dāng)?shù)男阅?，且?yōu)于相同迭代次數(shù)的原SCAN譯碼算法；隨著迭代次數(shù)的增加，極化碼在本文算法下的性能優(yōu)于SC譯碼算法，如當(dāng)?shù)螖?shù)為4時，性能增益大約為0.15 dB。與BP譯碼算法相比，極化碼在本文譯碼算法下的性能也明顯較優(yōu)，這是因為極化碼因子圖上存在大量的短環(huán)，導(dǎo)致BP不能有效收斂。

3.2 碼例為(4 096,2 867)的極化碼不同譯碼算法性能比較

本文進(jìn)一步研究了碼長較長、碼率較大時極化碼在本文譯碼算法下的性能。仿真結(jié)果表明(見圖10)，與SC譯碼算法相比，極化碼在本文譯碼算法下當(dāng)?shù)螖?shù)為4時仍能獲得大約0.18 dB的性能增益；與原SCAN譯碼算法相比，本文譯碼算法在相同迭代次數(shù)下仍具有較優(yōu)的性能。

圖9 (1 024,512)極化碼不同譯碼算法下性能

圖10 (4 096,2 867)極化碼不同譯碼算法下性能

4 結(jié) 語

本文基于原SCAN算法，通過改變左向LLR值和右向LLR值的更新時序提出了進(jìn)一步降低譯碼復(fù)雜度和空間復(fù)雜度的軟輸出譯碼算法。與原SC譯碼算法相比，提出的算法可減少譯碼過程中浮點(diǎn)運(yùn)算量，并能夠減少因子圖中為每列節(jié)點(diǎn)分配的存儲空間，同時具有更快的收斂速度，是一種能更好的為磁記錄等應(yīng)用場景提供軟信息的有效譯碼算法。

[1] Arikan E. Channel polarization: a method for constructing capacity achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions Information Theory, 2009, 55(77): 3051-3073.

[2] Tal I, Vardy A. List decoding of polar codes[J]. IEEE Transactions Information Theory, 2015, 61(5):2213-2226.

[3] Niu K, Chen K. Stack decoding of polar codes[J]. Electronics Letters, 2012, 48(12): 695-697.

[4] Li B, Shen H, Tse D. An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check[J]. IEEE Communications Letters, 2012, 16(12): 2044-2047.

[5] Fayyaz U U, Barry J R. Low-complexity soft-output decoding of polar codes[J]. IEEE Selected Areas Communications, 2014, 32(5): 958-966.

[6] Forney G D. Codes on graphs: normal realizations[J]. IEEE Transactions Information Theory, 2001, 47(2): 520-548.

[7] Eslami A, Pishro-Nik H. On finite-length performance of polar codes: stopping sets, error floor and concatenated design[J]. IEEE Transactions on Communications, 2013, 61(3): 919-929.

[8] Yuan B, Parhi K K. Early stopping criteria for energy-efficient low-latency belief-propagation polar code decoders[J]. IEEE Transactions Signal Processing, 2014, 62(24): 6496-6506.

[9] Arkan E. A performance comparison of polar codes and Reed-Muller codes[J]. IEEE Communications Letters, 2008, 12(6): 447-449.

[10] Zhang Y, Liu A, Pan X, et al. A modified belief propagation polar decoder[J]. IEEE Communications Letters, 2014, 18(7): 1091-1094.