極化碼改進(jìn)串行抵消比特翻轉(zhuǎn)譯碼算法

王 杰，郭 銳

（杭州電子科技大學(xué)，浙江 杭州 310018）

0 引 言

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

1 極化碼理論

1.1 極化碼編碼

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

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

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

其中：

判決函數(shù)h根據(jù)對應(yīng)的對數(shù)似然比做出譯碼判決，即：

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

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

2 改進(jìn)串行抵消比特翻轉(zhuǎn)譯碼算法

2.1 錯誤傳播的影響

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

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

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

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

2.2 分段校驗極化碼構(gòu)造

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

2.2.1 均勻分段構(gòu)造

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

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

2.2.2 基于極化特性分段構(gòu)造

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

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

以錯誤突發(fā)段進(jìn)行分段的優(yōu)勢為：

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

第二，分段處理增加比特翻轉(zhuǎn)機(jī)會，且分段數(shù)是可翻轉(zhuǎn)比特數(shù)，總體看來可以實現(xiàn)多比特翻轉(zhuǎn)。

2.3 改進(jìn)串行抵消比特翻轉(zhuǎn)譯碼算法

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

根據(jù)上述內(nèi)容，新算法的具體流程如下（針對基于極化特性分段構(gòu)造）：

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

步驟3：當(dāng)SC譯碼進(jìn)行到每一段的截止位時，即完成信道索引i=indp,p∈{1,2,…, p}（假設(shè)此時譯碼進(jìn)行到第p段）所傳輸?shù)谋忍氐淖g碼判決，然后進(jìn)行奇偶校驗，根據(jù)校驗結(jié)果確定判定結(jié)果。如果判定結(jié)果為未出錯，執(zhí)行步驟5；否則，對對應(yīng)索引位置的按升序排列，取其中前T個最小的，以對應(yīng)的信道索引i構(gòu)造待翻轉(zhuǎn)比特集合Flip={F1,F2,…,FT}，執(zhí)行步驟4。

表3 錯誤比特位置判定結(jié)果

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

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

步驟6：按上述方式分段譯碼、多次校驗、執(zhí)行比特翻轉(zhuǎn)，直到譯碼結(jié)束，得到譯碼估計碼字。

3 系統(tǒng)仿真與性能分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

針對極化碼的錯誤傳播特性，本文提出了改進(jìn)SC比特翻轉(zhuǎn)譯碼算法。該算法采取對信息位分段校驗的方式，增加比特翻轉(zhuǎn)次數(shù)，及時糾正錯誤比特，實現(xiàn)了多比特翻轉(zhuǎn)，抑制錯誤傳播的效果更好。仿真結(jié)果表明，文中提出基于極化特性分段構(gòu)造方式，能合理利用極化碼的極化效應(yīng)，使得錯誤比特能盡可能均勻分布于每段，降低段內(nèi)存在多比特錯誤的概率，進(jìn)一步提升譯碼性能。結(jié)合仿真結(jié)果分析，與已有的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差錯控制技術(shù)研究[J].電子與信息學(xué)報,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] 崔茵,袁遼,倪衛(wèi)明.高斯信道下極化碼的子信道錯誤概率計算[J].微型電腦應(yīng)用,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.