王 杰，郭 銳

（杭州電子科技大學(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趨于無窮大時(shí)，采用串行抵消（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)冗余校驗(yàn)（Cyclic Redundancy Check，CRC）輔助SCL算法，即在SCL算法基礎(chǔ)上加入CRC校驗(yàn)用于譯碼路徑判決，令中短碼長的極化碼性能優(yōu)于LDPC碼和Turbo碼。針對(duì)SC譯碼過程的錯(cuò)誤傳播，文獻(xiàn)[8]提出串行抵消翻轉(zhuǎn)（SCFlip）算法，使用比特翻轉(zhuǎn)思想對(duì)SC譯碼進(jìn)行檢錯(cuò)并糾錯(cuò)，提升SC譯碼性能，且在信噪比較高時(shí)，算法復(fù)雜度相對(duì)于SC譯碼并沒有較大提高。本文在SCFlip算法的基礎(chǔ)上，提出了基于極化特性分段策略，根據(jù)極化子信道的可靠度進(jìn)行分段比特翻轉(zhuǎn)，實(shí)現(xiàn)了多比特翻轉(zhuǎn)，進(jìn)一步提升了SC譯碼算法的性能。

1 極化碼理論

1.1 極化碼編碼

極化碼的編碼過程實(shí)質(zhì)是信道極化（Channel Polarization）過程[1]，即通過信道組合（Channel Combining）和信道分離（Channel Splitting）將相互獨(dú)立的N(N=2n)個(gè)B-DMC信道W∶X→Y轉(zhuǎn)化為相互依賴的N個(gè)極化子信道∶X→Y×Xi-1。其中，X∈{0.1}表示信道輸入集，Y表示信道輸出集。編碼時(shí)，根據(jù)各極化子信道的可靠度排列，從中選出可靠度高的K個(gè)信道傳輸信息比特序列，剩下N-K個(gè)可靠度低的信道傳輸凍結(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ù)對(duì)應(yīng)的對(duì)數(shù)似然比做出譯碼判決，即：

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

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

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

2.1 錯(cuò)誤傳播的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)本文提出的改進(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)比特?cái)?shù)T1=16，新算法的每段待翻轉(zhuǎn)比特?cái)?shù)T2=8。圖2、圖3分別為碼長N=256時(shí)的誤比特率和誤幀率曲線，新算法分段數(shù)P=4；圖4、圖5分別為碼長N=256時(shí)的誤比特率和誤幀率曲線，新算法分段數(shù)P=6；圖6、圖7分別為碼長N=1 024時(shí)的誤比特率和誤幀率曲線。新算法分段數(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算法。因?yàn)樾滤惴軌驅(qū)崿F(xiàn)多次翻轉(zhuǎn)，在SCFlip算法的基礎(chǔ)上能更大程度抑制SC譯碼中出現(xiàn)的錯(cuò)誤傳播特性和突發(fā)錯(cuò)誤。另外，在信噪比不大于1 dB時(shí)，新算法性能提升有限。這是由于信道條件差會(huì)導(dǎo)致錯(cuò)誤比特較多，導(dǎo)致新算法無法取得較好的翻轉(zhuǎn)效果。仿真結(jié)果也表明，基于極化特性分段構(gòu)造的改進(jìn)SC比特翻轉(zhuǎn)算法性能略優(yōu)于基于均勻構(gòu)造的改進(jìn)SC比特翻轉(zhuǎn)算法性能。這是因?yàn)樵谛畔⑿蛄械姆侄紊?，基于極化特性分段方式能夠從錯(cuò)誤比特出現(xiàn)位置角度考慮分段位置，而不是從信息序列整體角度考慮，并結(jié)合極化碼的信道極化特性，將譯碼出錯(cuò)比特盡可能均勻分布到各段中，并保證每段內(nèi)的錯(cuò)誤比特?cái)?shù)盡可能少，以提高比特翻轉(zhuǎn)的糾錯(cuò)能力。

表4給出碼長N=1 024、在誤幀率為10-4時(shí)，本文提出的新算法相比于其他已有算法獲得的增益。由表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時(shí)，新算法獲得的性能增益統(tǒng)計(jì)

4 結(jié) 語

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