張青雙，劉愛軍

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

0 引言

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

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

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

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

1 極化碼

1.1 極化碼的編碼

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

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

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

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

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

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

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

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

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

2 修正的BP算法

2.1 似然信息修正

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

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

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

對(duì)于PE(b)、PE(c)，一個(gè)輸入節(jié)點(diǎn)為確定節(jié)點(diǎn)，另一個(gè)為信息節(jié)點(diǎn)。在迭代譯碼的過(guò)程中，當(dāng)確定節(jié)點(diǎn)的似然信息計(jì)算錯(cuò)誤時(shí)，錯(cuò)誤必然來(lái)源于其他三個(gè)節(jié)點(diǎn)的似然信息。對(duì)其他三個(gè)節(jié)點(diǎn)的似然信息做一定量的修正，然后重新計(jì)算信息節(jié)點(diǎn)的似然信息，這樣可以一定程度上提高信息節(jié)點(diǎn)似然信息的可信度。考慮此種類型PE的兩輸入節(jié)點(diǎn)為確定節(jié)點(diǎn)(i，j)和信息節(jié)點(diǎn)(i，j+N/2)，如果被錯(cuò)誤計(jì)算，則進(jìn)行如下修正:

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

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

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

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

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

3 數(shù)值分析

3.1 復(fù)雜度分析

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

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

表1 不同碼長(zhǎng)復(fù)雜度對(duì)比Table 1 Computation complexity for different block lengths

3.2 性能仿真

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

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

4 結(jié)語(yǔ)

文中提出了一種極化碼對(duì)數(shù)域BP譯碼的修正算法，通過(guò)對(duì)錯(cuò)誤計(jì)算的對(duì)數(shù)似然信息進(jìn)行修正以提升譯碼性能。在修正參數(shù)的選擇上，運(yùn)用了密度進(jìn)化的高斯近似思想，通過(guò)把對(duì)數(shù)似然信息近似為高斯分布來(lái)獲得一個(gè)合理的修正參數(shù)。仿真結(jié)果表明，修正的BP算法能夠在復(fù)雜度少量增加的情況下改善0.2 dB左右的誤碼性能。雖然性能提升不大，希望這種修正的思想能夠給后來(lái)的研究者一些啟發(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］ 李斌，王學(xué)東，王繼偉.極化碼原理及應(yīng)用［J］.通信技術(shù) 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.