一種改進的極化碼置信譯碼器

張青雙，劉愛軍

(解放軍理工大學通信工程學院，江蘇南京210007)

0 引言

極化碼是第一種在二進制對稱信道(BSC)條件下被證明能夠達到香農極限的信道編碼方式，并且具有較低的編譯碼復雜度［1］。Arikan在2009年提出極化碼的概念以后，在編碼領域引起巨大反響。然而極化碼的連續(xù)抵消(SC)譯碼算法并不能達到理論上的達到香農極限誤碼性能，為了進一步挖掘極化碼的性能極限，許多高性能的譯碼算法被相繼提出。

序列SC譯碼(SCL)［2］，采用堆棧的 SC譯碼(SCS)［3］以及 CRC 輔助的 SCL 譯碼［4］是基于 SC 譯碼的改進型算法，能夠帶來很大的誤碼性能提升。特別是CRC輔助的SCL算法，在碼長達到2 048時誤碼性能能夠超過部分Turbo碼。然而，上述的算法都是串行譯碼，譯碼輸出效率低，譯碼復雜度高，限制了其在高速通信系統(tǒng)中的應用。置信譯碼(BP)在LDPC譯碼過程中得到成功的應用，同樣可以用于極化碼的譯碼［1］。文獻［5］給出的結果顯示，BP譯碼能夠在低譯碼延遲的條件下獲得比部分SC譯碼改進算法更好的性能。

文中提出了一種極化碼BP譯碼的改進算法，旨在進一步提升其譯碼性能。在極化碼的編碼因子圖中，節(jié)點被分為兩種:確定節(jié)點和信息節(jié)點［6］。確定節(jié)點承載的是已知的比特信息，相應的它的先驗信息也為已知;信息節(jié)點承載的是未知的比特信息。因子圖中的四個節(jié)點形成一個計算單元，每一個節(jié)點的似然信息都可以通過其他三個節(jié)點計算得到。在譯碼迭代的過程中，當確定節(jié)點的似然信息計算錯誤時，可以對其他三個節(jié)點的似然信息做一定的修正。文中給出了一種修正算法，即通過引入一個修正參數(shù)對其他三個節(jié)點似然信息進行修正以提高似然信息的可信度。然后，利用高斯近似的思想，給出了一種修正參數(shù)的計算方法。仿真結果表明，該修正算法能夠在犧牲很小復雜度的條件下獲得0.2 dB左右的性能提升。

文中主要介紹了極化碼的構造，對數(shù)域的BP譯碼算法，改進的BP算法(MBP)以及采用高斯近似的修正參數(shù)計算方法。最后給出了加性高斯白噪聲信道(AWGN)條件下的仿真結果以及算法復雜度分析。

1 極化碼

1.1 極化碼的編碼

極化碼是利用信道極化現(xiàn)象提出的信道編碼方式，最早由Arikan發(fā)現(xiàn)并提出［1］?；谛诺澜M合和分離的理論，N個二進制離散無記憶信道(BDMC)通過模二加的方式組合在一起然后分離后［7］，當N趨于無窮大時，部分信道的信道容量會趨近于1，相應的其他信道的信道容量趨近于0。利用容量較大的子信道傳輸有用信息，剩下的子信道傳輸確定信息，由此可以形成極化碼。極化碼由三個參數(shù)確定:碼長N=2m，m＞0，碼率R=K/N以及一個K維的子集Aa?{1，2，…，N}。Aa表示用于傳輸信息的子信道的序號，在AWGN信道條件下，可以利用密度進化的方式確定［8］。假設=(u1，u2，…，uN)是編碼前的比特組，則由子集Aa確定的的子矢量uAa是需要傳輸?shù)谋忍匦畔ⅲ鳤a的補集Ac確定的子矢量uAc為確定的0或1信息組，這樣編碼后的碼字可以表示為:

圖1 N=8的極化碼編碼因子Fig.1 Factor graph for polar codeswith N=8

1.2 極化碼的對數(shù)域BP譯碼

考慮到LDPC的BP譯碼算法是基于其二分圖，極化碼的BP譯碼算法的似然信息傳遞方式可以由其因子圖導出?？紤]碼長N=2m，m＞0的極化碼，其因子圖共有(m+1)×N個節(jié)點，每四個節(jié)點形成一個基本計算單元(PE)。設整數(shù)對(i，j)，0≤i≤m+1，1≤j≤N 表示第 i層(stage)的第 j個節(jié)點，則每一個PE(Process Element)中四個節(jié)點似然信息傳播方式如圖2所示。

圖2 BP譯碼的基本處理單元Fig.2 Basic PE for BP decoding

信息，t為迭代次數(shù)，其定義為

代過程中，對數(shù)似然信息的更新過程為［7］:

式中，f(x，y)=2a tan h(tan h(x/2)·tan h(y/2))。當?shù)螖?shù)t達到給定的迭代閾值m Iter時，完成譯碼輸出。

發(fā)送的信息比特可以由子集Aa?{1，2，…，N}確定。

2 修正的BP算法

2.1 似然信息修正

圖3給出了N=8的因子圖中四種不同的PE，圓形節(jié)點為信息節(jié)點，方形節(jié)點為確定節(jié)點。根據(jù)輸入節(jié)點類型的不同，因子圖包含四種不同的PE。一般的BP算法除了在初始化的時候，對不同類型的節(jié)點賦予的初值不同，譯碼過程中不會考慮到因子圖中節(jié)點的差異性，這樣就會丟失部分有用的信息。修正算法正是基于節(jié)點的差異性而提出來的。

由圖3可以看到，可以根據(jù)PE的輸入節(jié)點的類型將其分為4類，分別表示為(a)、(b)、(c)、(d)。對于PE(a)，輸入節(jié)點均為確定節(jié)點，如果其對數(shù)似然信息計算錯誤，不會對譯碼結果造成影響，因此不需要對其做任何的修正。對于PE(d)，兩輸入節(jié)點均為信息節(jié)點，似然信息的對錯無法判斷，對其同樣不做任何修正。

圖3 因子圖中四種不同的PEFig.3 Four different PEs in factor graph

對于PE(b)、PE(c)，一個輸入節(jié)點為確定節(jié)點，另一個為信息節(jié)點。在迭代譯碼的過程中，當確定節(jié)點的似然信息計算錯誤時，錯誤必然來源于其他三個節(jié)點的似然信息。對其他三個節(jié)點的似然信息做一定量的修正，然后重新計算信息節(jié)點的似然信息，這樣可以一定程度上提高信息節(jié)點似然信息的可信度?？紤]此種類型PE的兩輸入節(jié)點為確定節(jié)點(i，j)和信息節(jié)點(i，j+N/2)，如果被錯誤計算，則進行如下修正:

2.2 參數(shù)選擇的高斯近似算法

只有合理的參數(shù)選擇才會帶來誤碼性能的提升。很顯然，過大的修正參數(shù)會帶來性能更大的惡化，而太小的值又不會有足夠的效果，文中考慮采用高斯近似的方法給出一組修正參數(shù)。

在AWGN信道條件下，接受信息的對數(shù)似然信息為均值為 2/σ2，方差為 4/σ2的高斯分布，σ2為信道的噪聲方差。這樣，根據(jù)高斯近似的思想的分布可以近似為高斯分布，設其均值為，1≤i≤m+1，1≤j≤N。根據(jù)文獻［9 － 10］可以利用遞歸計算得到

式中，截止條件為 am+1，k=2/σ2，k=1，2，…，N。函數(shù)g(x)具有如下形式:

式中，pe表示發(fā)生錯誤的概率，本算法中假設三個對數(shù)似然信息錯誤的概率相等為1/3。Ee［Lti，j］表示發(fā)生錯誤條件下的條件均值。利用高斯分布的特性，可以得到

3 數(shù)值分析

3.1 復雜度分析

在工程實現(xiàn)的過程中，函數(shù)tan h(x)和a tan h(x)可以用查表的方式實現(xiàn)。根據(jù)式(5)，每一個對數(shù)似然信息的更新需要1次加法，1次乘法和3次查表。每一個PE需要四次似然信息的更新。對于碼長為N=2m，m＞0的極化碼，因子圖包含m×個PE，每次迭代過程則需要m××4次加法，m××4次乘法以及 m ××12次查表。

修正的BP算法會帶來額外的復雜度。根據(jù)式(8)，每次修正需要3次加法，修正以后還需要重新計算。假設所有確定節(jié)點的似然信息都計算錯誤，表1給出了不同碼長，碼率為1/2的條件下，每次迭代BP和修正的BP算法復雜度數(shù)值。其中加法用‘+’表示，乘法用‘*’表示，查表用‘LUT’表示。從表1中可以看出，修正算法帶來的額外復雜度與原復雜度的比值分別不會超過17.86%、7.14%、7.14%，且隨著碼長的增加逐漸遞減。

表1 不同碼長復雜度對比Table 1 Computation complexity for different block lengths

3.2 性能仿真

為了驗證修正的BP譯碼算法的性能，下面給出了AWGN信道條件下的誤碼率Monte Carto仿真，碼率為 1/2，碼長分別為 128，256，512，迭代次數(shù)為50。編碼方式采用文獻［1］的方式，譯碼分別為對數(shù)域BP算法和修正的BP算法。圖4給出了兩種算法的誤碼性能對比，可以看出在相同誤碼率條件下，修正算法能夠帶來0.2 dB左右的比特信噪比的提升。因此，修正的算法能夠在犧牲少量復雜度條件下?lián)Q取較好的性能。

圖4 BP及其修正算法誤碼率曲線Fig.4 Bit error rate curve for BP and MBP with different block lengths

4 結語

文中提出了一種極化碼對數(shù)域BP譯碼的修正算法，通過對錯誤計算的對數(shù)似然信息進行修正以提升譯碼性能。在修正參數(shù)的選擇上，運用了密度進化的高斯近似思想，通過把對數(shù)似然信息近似為高斯分布來獲得一個合理的修正參數(shù)。仿真結果表明，修正的BP算法能夠在復雜度少量增加的情況下改善0.2 dB左右的誤碼性能。雖然性能提升不大，希望這種修正的思想能夠給后來的研究者一些啟發(fā)，找到性能更加優(yōu)異的極化碼譯碼算法。

［1］ ARIKAN E.Channel Polarization:a Method for Constructing Capacity Achieving Codes for Symmetric Binary－input Memoryless Channels［J］.IEEE Trans.Inf.Theory，2009，55(07):3051 －3073.

［2］ TAL I，VARDY A.List Decoding of Polar Codes［C］//Proc.2011 IEEE Int.Symp.Inform.Theory.St.Petersburg:［s.n.］，2011:1 －5.

［3］ CHEN K，NIU K，LIN JR.Improved Successive Cancellation Decoding of Polar Codes［J］.IEEE Trans.Comm.2013，61(08):3100 －3107.

［4］ NIU K，CHEN K.CRC －Aided Decoding of Polar Codes［J］.IEEE Communication Letters，2012，16(10):1668 －1671.

［5］ HUSSAMIN，KORADA S，URBANKE R.Performance of Polar Codes for Channel and Source Coding［C］//IEEE International Symposium on Information Theory，2009.Seoul，South Korea:IEEE，2009:1493 －1495.

［6］ ALPTEKIN P.An FPGA Implementation Architecture for Decoding of Polar Codes［C］//International Symposium on Wireless Communication Systems(ISWCS2011).Aachen，Germany:［s.n.］，2011:437 －441.

［7］ 李斌，王學東，王繼偉.極化碼原理及應用［J］.通信技術 2012，45(10):21 －23.LIBin，WANG Xue－dong，WANG Ji－wei.Theory and Application of Polar Code［J］.Communications Technology，2012，45(10):21 －23.

［8］ TRIFONOV P.Efficient Design and Decoding of Polar Codes［J］.IEEE Transaction on Communication，60(11)，2012:3221 －3227.

［9］ LIHui－ jun，YUAN Jin － hong.A Practical Construction Method For Polar Codes in AWGN Channels［C］//IEEE Tencon.Sydney，:［s.n.］，2013:223 －226.

［10］ CHUNG S，RICHARDSON T J，URBANKER L.Analysis of Sum Product Decoding of Low－density paritycheck Codes Using A Gaussian Approximation［J］.IEEE Transaction on Information Theory，47(02)，2001:657－670.