磁記錄中極化碼低復雜迭代SCAN譯碼算法研究

李桂萍, 李聰娜

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

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

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

(1)

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

當φ為偶數(shù)時

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

(2)

當φ為奇數(shù)時

(3)

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

(4)

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

(5)

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

(6)

圖1 碼長為8的極化碼對應的因子圖

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

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

圖2 因子圖一個極化單元中各節(jié)點相關(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 極化碼低復雜迭代SCAN譯碼算法

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

2.1 通信傳輸模型設計

圖3 本文通信傳輸模型

2.2 本文算法基本原理

本文提出的改進SCAN算法的基本原理如下：

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

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

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

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

若令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ù)的基礎上，本文提出的改進算法包括如下幾個重要的步驟：

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

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

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

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

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

輸入：j,L,R0,Re

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

圖6 低復雜改進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é)點對應的左向LLR值依次進行更新。更新規(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é)點對應的左向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個下標為奇數(shù)的節(jié)點對應的右向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個下標為偶數(shù)的節(jié)點按式(15)和式(16)更新其對應的右向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 復雜度分析

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

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譯碼算法相當?shù)男阅埽覂?yōu)于相同迭代次數(shù)的原SCAN譯碼算法；隨著迭代次數(shù)的增加，極化碼在本文算法下的性能優(yōu)于SC譯碼算法，如當?shù)螖?shù)為4時，性能增益大約為0.15 dB。與BP譯碼算法相比，極化碼在本文譯碼算法下的性能也明顯較優(yōu)，這是因為極化碼因子圖上存在大量的短環(huán)，導致BP不能有效收斂。

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

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

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

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

4 結(jié) 語

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

[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.