極化碼改進串行抵消比特翻轉譯碼算法

王 杰，郭 銳

（杭州電子科技大學，浙江 杭州 310018）

0 引 言

2008年，E.Arikan教授提出極化碼（Polar Codes），是迄今為止唯一一類可以從理論上證明可達香農容限的信道編碼方式。由于固定的編碼結構和較低的編譯碼復雜度，它受到了編碼界的廣泛關注。E.Arikan從理論上證明，在二進制離散無記憶信道（B-DMC）下，當碼長N趨于無窮大時，采用串行抵消（SC）譯碼算法的極化碼可以達到香農容限[1-2]。然而，這卻并不適用于中短碼長極化碼。由于信道極化不完全，極化碼的SC譯碼算法性能不足。因此，需要尋找更優的譯碼方案來彌補這一不足[3-4]。為了改善SC算法的路徑局部最優搜索方式，文獻[5-6]提出SC譯碼的改進算法：串行抵消列表SCL譯碼算法。它的原理是在SC譯碼的基礎上，通過保留多條候選譯碼判決路徑，從候選路徑中選取可靠度最高的路徑作為譯碼結果，提升譯碼性能，其中譯碼復雜度為O(LNlogN)（L為列表寬度）。為了進一步提升極化碼性能，文獻[7]提出循環冗余校驗（Cyclic Redundancy Check，CRC）輔助SCL算法，即在SCL算法基礎上加入CRC校驗用于譯碼路徑判決，令中短碼長的極化碼性能優于LDPC碼和Turbo碼。針對SC譯碼過程的錯誤傳播，文獻[8]提出串行抵消翻轉（SCFlip）算法，使用比特翻轉思想對SC譯碼進行檢錯并糾錯，提升SC譯碼性能，且在信噪比較高時，算法復雜度相對于SC譯碼并沒有較大提高。本文在SCFlip算法的基礎上，提出了基于極化特性分段策略，根據極化子信道的可靠度進行分段比特翻轉，實現了多比特翻轉，進一步提升了SC譯碼算法的性能。

1 極化碼理論

1.1 極化碼編碼

極化碼的編碼過程實質是信道極化（Channel Polarization）過程[1]，即通過信道組合（Channel Combining）和信道分離（Channel Splitting）將相互獨立的N(N=2n)個B-DMC信道W∶X→Y轉化為相互依賴的N個極化子信道∶X→Y×Xi-1。其中，X∈{0.1}表示信道輸入集，Y表示信道輸出集。編碼時，根據各極化子信道的可靠度排列，從中選出可靠度高的K個信道傳輸信息比特序列，剩下N-K個可靠度低的信道傳輸凍結比特（一般為0），那么構造的極化碼碼率為R=K/N。若信息比特用集{1,2,…,N}表示，凍結比特用集合Ac?{b1,b2,…,bk}?{1,2,…,N}表示，其中Ac為A的補集，那么輸入序列可表示為=(uA,uAc)，極化碼的編碼為[8]：

其 中 GN為 生 成 矩 陣，GN=BNF?n,(n=logN)；表示基矩陣F的n次Kronecher積；BN為比特反轉重排矩陣，?{x1,x2,…,xN}表示編碼序列。經過調制和信道傳輸后，得到接收序列? {y1,y2,…,yN}。

1.2 串行抵消（SC）譯碼算法

其中：

判決函數h根據對應的對數似然比做出譯碼判決，即：

可以直接使用迭代公式計算譯碼過程中的似然比：

其中，似然比的初始化條件為：

2 改進串行抵消比特翻轉譯碼算法

2.1 錯誤傳播的影響

由式（6）可知，計算第2i個比特的對數似然比時，需要用到第2i-1個比特的譯碼估計值21?iu-。若21?iu-譯碼判決出錯，則當前比特的估計值將受前一比特估計值的影響，這就是SC譯碼的錯誤傳播特性。在SC譯碼過程中，導致譯碼判決出錯的原因主要是信道噪聲和錯誤傳播。文獻[9]提出了能自動糾錯的SC Oracle譯碼器來探究錯誤傳播對SC譯碼性能的影響。因為這種譯碼器能夠消除錯誤傳播的影響，所以需要糾正的錯誤比特則均是由信道噪聲產生的。為了直觀地統計數據，采用全零碼字傳輸，在500 000次仿真實驗下，統計了各錯誤幀中地誤比特數，結果如表1、表2所示。

表1 不同信噪比下錯誤位數比例（N=1 024）

表2 不同碼長下錯誤位數比例（SNR=2 dB）

根據表1、表2可知，在所有錯誤幀中，單比特錯誤幀占據的比例隨信噪比和碼長的增加越來越大。以碼長N=512為例，信噪比Eb/N0=2時，幀內錯誤比特數均不超過4位，其中單比特錯誤幀的比例為74.6%，2～4比特錯誤幀占據的比例為25.4%。SCFlip算法僅能翻轉單個比特，而沒有多比特糾錯能力，雖然能夠在一定程度上提升譯碼性能，但對于剩余的25.4%的多比特錯誤塊，SCFlip算法無法得到正確的譯碼碼字，這就是SCFlip算法的局限性。因此，在改善SC算法的錯誤傳播特性上，SCFlip算法存在較大的改進空間。

2.2 分段校驗極化碼構造

針對SCFlip算法的局限性，本文提出采用分段策略的改進SCFlip算法。具體地，將信息序列按照一定的方法分段，每段均加入校驗比特用以檢錯，實現段內單比特翻轉和整體多比特翻轉，且翻轉比特數即為分段數，以獲得針對多比特錯誤塊的修正能力，進一步抑制錯誤傳播的影響。本文提出的信息序列的分段方法有均勻分段和基于極化特性分段兩種方式。

2.2.1 均勻分段構造

所謂均勻分段，就是每段的比特數是相等的，即M=K/P，其中K是極化碼的非凍結比特數，P表示均勻分段數。校驗比特一般放在每段的最后，本文選擇3位奇偶校驗，那么每段中的信息序列數為M-3，每段的比特分布則可以表示為：

均勻分段構造雖然可以獲得一定的性能提升，但錯誤比特不一定均勻分布在信息序列中，而此分段依據并沒有考慮錯誤比特數密集的區域。由于本文所提算法每段內僅能翻轉單個比特，故所取分段方式要在最大程度上保證錯誤比特均勻分散在每段內，且保證段內錯誤比特數盡可能少。

2.2.2 基于極化特性分段構造

基于極化特性分段構造，利用極化子信道的不同可靠性，以極化子信道的錯誤概率分布作為分段依據[10]。在本文采用的AWGN信道中，用高斯近似方法計算各極化子信道的錯誤概率[11]，并繪制出碼長N=256、碼率R=0.5、信噪比Eb/NO=1 dB的傳輸非凍結比特信道的錯誤概率分布圖，如圖1所示。從圖1可以觀察到，非凍結比特信道的錯誤概率中存在錯誤突發段。錯誤突發段是由于信道極化過程中部分錯誤概率較高的非凍結比特信道非均勻散落于所有信息信道中，導致某些信道的錯誤概率急劇增加。圖1中虛線右邊的錯誤概率突然急劇增加，如此可以將該信息序列按錯誤突發情況分為4段。一般情況下，錯誤突發段的選擇標準如下：與突發錯誤點鄰接的兩信道的錯誤概率差距遠大于其他相鄰信道之間的錯誤概率差。

基于極化特性分段構造標準，以錯誤突發點為分割線（如圖1中的虛線位置），將信息序列非均勻地分為P段，每段最后3位作為CRC校驗位。假設第p段包含L個信息信道索引，那么每段的比特分布可用式（11）表示：

以錯誤突發段進行分段的優勢為：

第一，避免將錯誤比特密集段分于同一段內，基本保證錯誤比特能均勻分布于每段。又由于本算法段內每次僅能翻轉一位比特，那么段內誤比特數目越少，翻轉成功率越高，譯碼錯誤率也就越低。

第二，分段處理增加比特翻轉機會，且分段數是可翻轉比特數，總體看來可以實現多比特翻轉。

2.3 改進串行抵消比特翻轉譯碼算法

本文所提的改進SCFlip算法，以分段構造的方式增加校驗次數和比特翻轉次數，降低了極化碼譯碼的突發錯誤概率和錯誤傳播的影響。新算法編碼階段加入的奇偶校驗位，能夠在譯碼階段對譯碼估計序列進行檢錯，根據奇偶校驗結果，判定錯誤比特可能的位置，判定結果見表3。

根據上述內容，新算法的具體流程如下（針對基于極化特性分段構造）：

步驟1：通過高斯近似法計算極化子信道錯誤概率，并根據錯誤概率劃分信息序列，從而確定分段數目P和待翻轉比特位數T，同時記錄每段截止位的信道索引集合，記為：Ind={ind1,ind2,…,indp}。按照2.2.2中方法添加奇偶校驗位進行極化碼編碼，得到編碼碼字。

步驟3：當SC譯碼進行到每一段的截止位時，即完成信道索引i=indp,p∈{1,2,…, p}（假設此時譯碼進行到第p段）所傳輸的比特的譯碼判決，然后進行奇偶校驗，根據校驗結果確定判定結果。如果判定結果為未出錯，執行步驟5；否則，對對應索引位置的按升序排列，取其中前T個最小的，以對應的信道索引i構造待翻轉比特集合Flip={F1,F2,…,FT}，執行步驟4。

表3 錯誤比特位置判定結果

步驟4：比特翻轉階段，從集合Flip中選取F1位對應的比特進行翻轉，并對F1+1位到indp位的比特重新執行SC譯碼和奇偶校驗。若譯碼結果仍未通過奇偶校驗，先還原F1位對應的比特值，選取Flip中F2位對應的比特執行翻轉操作。后續過程同前。若遍歷集合Flip仍未得到有效碼字，則說明翻轉失敗，以初始SC譯碼作為本段譯碼結果，然后執行步驟5；若存在一次譯碼結果通過奇偶校驗，則停止翻轉，執行步驟5。

步驟5：對信道索引i∈(indp,indp+1)之間的比特繼續進行SC譯碼，在對indp+1位比特判決后進行奇偶校驗，后續比特翻轉操作同步驟3。

步驟6：按上述方式分段譯碼、多次校驗、執行比特翻轉，直到譯碼結束，得到譯碼估計碼字。

3 系統仿真與性能分析

對本文提出的改進SC比特翻轉算法（分別采用均勻構造和基于極化特性構造）進行仿真分析，主要分析誤比特率、誤幀率，并與文獻[1]中提出的SC算法、文獻[5-6]中提出的SCL算法（L=2）、

文獻[8]中提出的SCFlip算法進行比較。本仿真在AWGN信道下進行，設碼字的有效碼率為0.5，SCFlip算法，待翻轉比特數T1=16，新算法的每段待翻轉比特數T2=8。圖2、圖3分別為碼長N=256時的誤比特率和誤幀率曲線，新算法分段數P=4；圖4、圖5分別為碼長N=256時的誤比特率和誤幀率曲線，新算法分段數P=6；圖6、圖7分別為碼長N=1 024時的誤比特率和誤幀率曲線。新算法分段數P=8。

圖2 N=256各譯碼算法誤比特率

圖3 N=256各譯碼算法誤幀率

圖4 N=512各譯碼算法誤比特率

圖5 N=512各譯碼算法誤幀率

圖6 N=1 024各譯碼算法誤比特率

圖7 N=1 024各譯碼算法誤幀率

由仿真結果可知，本文提出的改進SC比特翻轉譯碼算法性能明顯優于SC譯碼、SCL（L=2）算法和SCFlip算法。因為新算法能夠實現多次翻轉，在SCFlip算法的基礎上能更大程度抑制SC譯碼中出現的錯誤傳播特性和突發錯誤。另外，在信噪比不大于1 dB時，新算法性能提升有限。這是由于信道條件差會導致錯誤比特較多，導致新算法無法取得較好的翻轉效果。仿真結果也表明，基于極化特性分段構造的改進SC比特翻轉算法性能略優于基于均勻構造的改進SC比特翻轉算法性能。這是因為在信息序列的分段上，基于極化特性分段方式能夠從錯誤比特出現位置角度考慮分段位置，而不是從信息序列整體角度考慮，并結合極化碼的信道極化特性，將譯碼出錯比特盡可能均勻分布到各段中，并保證每段內的錯誤比特數盡可能少，以提高比特翻轉的糾錯能力。

表4給出碼長N=1 024、在誤幀率為10-4時，本文提出的新算法相比于其他已有算法獲得的增益。由表4可知，相比SCFlip算法，本文提出的算法（基于極化特性構造）獲得了約0.28 dB的增益；相比SCL（L=2）算法，獲得了約0.33 dB的增益；相比SC算法，獲得了約0.74 dB的增益。此外，基于基于極化特性構造的新算法性能略好于基于均勻構造的新算法的性能，獲得了約0.13 dB的增益。

表4 FER=10-4時，新算法獲得的性能增益統計

4 結 語

針對極化碼的錯誤傳播特性，本文提出了改進SC比特翻轉譯碼算法。該算法采取對信息位分段校驗的方式，增加比特翻轉次數，及時糾正錯誤比特，實現了多比特翻轉，抑制錯誤傳播的效果更好。仿真結果表明，文中提出基于極化特性分段構造方式，能合理利用極化碼的極化效應，使得錯誤比特能盡可能均勻分布于每段，降低段內存在多比特錯誤的概率，進一步提升譯碼性能。結合仿真結果分析，與已有的SC算法、SCL（L=2）算法、SCFlip算法相比，本文提出的算法可分別獲得約0.74 dB、0.33 dB、0.28 dB的增益。

[1] Arikan E.Channel Polarization:A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels[J].IEEE Transactions on Information Theory,2008,55(07):3051-3073.

[2] Tal I,Vardy A.How to Construct Polar Codes[J].IEEE Transactions on Information Theory,2013,59(10):6562-6582.

[3] Trifonov P,Miloslavskaya V.Polar Subcodes[J].IEEE Journal on Selected Areas in Communicatio ns,2015,34(02):254-266.

[4] Trifonov P.Efficient Design and Decoding of Polar Codes[J].IEEE Transactions on Communicatio ns,2012,60(11):3221-3227.

[5] Chen K,Niu K,Lin J R.List Successive Cancellation Decoding of Polar Codes[J].Electronics Letters,2012,48(09):500-501.

[6] T a l I,V a r d y A.L i s t D e c o d i n g o f P o l a r Codes[J].IEEE Transactions on Information Theory,2012,61(05):2213-2226.

[7] Niu K,Chen K.CRC-Aided Decoding of Polar Codes[J].IEEE Communications Letters,2012,16(10):1668-1671.

[8] 郭銳,王美潔,王杰.基于縮短極化碼的MLC NAND Flash差錯控制技術研究[J].電子與信息學報,2017,39(07):1658-1665.GUO Rui,WANG Mei-jie,WANG Jie.Research on the MLC Nand Flash Error Control Technology Based on Polar Codes[J].Journal of Electronics & Information Tech nology,2017,39(07):1658-1665.

[9] Afisiadis O,Balatsoukas-Stimming A,Burg A.A Low-complexity Improved Successive Cancellation Decoder for Polar Codes[C].Signals,Systems and Computers,2014:2116-2120.

[10] Wang T,Qu D,Jiang T.Parity-Check-Concatenated Polar Codes[J].IEEE Communications Letters,2016(99):1.

[11] 崔茵,袁遼,倪衛明.高斯信道下極化碼的子信道錯誤概率計算[J].微型電腦應用,2017,33(02):58-61.CUI Yin,YUAN Liao,NI Wei-ming.Calculation of Sub-Channel’s Error Probability of Polar Code under AWGN Channel[J].Microcomputer Applications,2017,33(02):58-61.