一種改進(jìn)的Polar碼的BP譯碼算法

洪銀芳,李 暉,王新梅

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

一種改進(jìn)的Polar碼的BP譯碼算法

洪銀芳,李 暉,王新梅

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

為了減少置信度傳播譯碼算法的計(jì)算復(fù)雜度,提出了一種改進(jìn)的置信度傳播譯碼算法.該算法在節(jié)點(diǎn)更新時(shí),利用等誤差的線性近似函數(shù)來代替算法中的雙曲函數(shù),相比于原始的置信度傳播譯碼算法,改進(jìn)的算法僅僅需要乘法和加法運(yùn)算,因此大大降低了算法的計(jì)算復(fù)雜度,更易于硬件實(shí)現(xiàn).仿真結(jié)果表明,在低信噪比時(shí),改進(jìn)的置信度傳播譯碼算法的性能與原始BP譯碼算法的性能幾乎相同,在高信噪比時(shí),改進(jìn)的置信度傳播譯碼算法的性能比原始置信度傳播譯碼算法的性能略差,在碼長為256,誤碼率是10-6時(shí),改進(jìn)的置信度傳播譯碼算法的誤碼率性能比原始的置信度傳播譯碼算法退化了0.1 dB.

信道極化碼;置信度傳播算法;等誤差;線性近似;計(jì)算復(fù)雜度

文獻(xiàn)[1]提出的信道極化(Polar)碼是惟一被證明能夠達(dá)到容量限的碼且在串行抵消(Successive Cancellation,SC)譯碼下的復(fù)雜度較低.Polar碼在不同通信信道下的設(shè)計(jì)和應(yīng)用研究已經(jīng)取得了一定的成績,如在對稱二進(jìn)制離散無記憶信道、非對稱二進(jìn)制信道、多址接入信道、高斯信道、瑞利信道以及混合信道中都進(jìn)行了拓展研究.

Polar碼在長碼長時(shí)性能良好,但在中短碼長時(shí),性能卻要比低密度奇偶校驗(yàn)碼(Low Density Parity Check,LDPC)和Turbo碼要差.為了改善Polar碼在有限碼長時(shí)的性能,學(xué)者們提出了許多有效的譯碼算法[2-9].文獻(xiàn)[4]將碼的因子圖表示引入Polar碼中,利用置信度傳播(Belief Propagation,BP)算法來譯Polar碼[5].文獻(xiàn)[6]給出了Polar碼的BP譯碼算法的具體實(shí)現(xiàn)方法.文獻(xiàn)[7]提出了一種改進(jìn)的Polar碼的BP譯碼器,相比于SC譯碼算法,BP譯碼算法能達(dá)到較好的性能且能并行計(jì)算而利于硬件實(shí)現(xiàn).文獻(xiàn)[8]提出了一種改進(jìn)的SC譯碼算法,利用線性近似函數(shù)來代替退化轉(zhuǎn)化函數(shù),降低了計(jì)算復(fù)雜度,但是其性能要比原始的SC譯碼算法差.文獻(xiàn)[9-10]將線性近似方法應(yīng)用到LDPC碼的BP譯碼算法中,降低了BP譯碼算法的計(jì)算復(fù)雜度.

Polar碼在對數(shù)域上的BP譯碼算法可看成和積算法,其操作需要雙曲函數(shù)的計(jì)算,計(jì)算復(fù)雜度較高.為了降低BP譯碼算法的復(fù)雜度,筆者提出了一種改進(jìn)的Polar碼的BP譯碼算法.在節(jié)點(diǎn)更新時(shí),改進(jìn)的BP算法利用等誤差的線性近似函數(shù)來代替算法中的雙曲函數(shù),即用乘法和加法運(yùn)算代替了BP算法中的對數(shù)、指數(shù)和除法運(yùn)算,大大降低了算法的計(jì)算復(fù)雜度,易于硬件實(shí)現(xiàn).仿真結(jié)果表明,在低信噪比(Signal-to-Noise Ratio,SNR)時(shí),改進(jìn)的BP譯碼算法的性能與原始BP譯碼算法的性能相同;在高信噪比時(shí),改進(jìn)的BP譯碼算法的性能比原始BP譯碼算法的性能略差;同時(shí),改進(jìn)的BP譯碼算法的性能比SC算法和已知的相似簡化算法[8]的性能要好.

1　Polar碼及其BP譯碼算法

Polar碼可以看成是一個(gè)GN陪集碼,可以表示為其中N是碼長,可以表示成N=2n,n是正整數(shù),K是維數(shù),也可看成是信息集合A的大小,A?{1,2,…,N},信息集合A的選取是由信道極化所決定的.表示固定比特,

圖1　n=3時(shí)Polar碼的因子圖表示

Polar碼的BP譯碼算法基于文獻(xiàn)[4]提出的碼的因子圖表示.一個(gè)(N,K)Polar碼由一個(gè)n階段的因子圖來迭代譯碼,因子圖包括N(n+1)個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)由整數(shù)對(i,j)表示,每個(gè)階段包括N/2個(gè)處理單元(Processing Elements,PE).節(jié)點(diǎn)(i,j)的第1個(gè)元素表示階層,第2個(gè)元素表示行,第1階層的節(jié)點(diǎn)與信源矢量u有關(guān),第n+1階層的節(jié)點(diǎn)與接收到的信道信息有關(guān).在整個(gè)譯碼器中,i和j的取值范圍為1≤i≤n,1≤j≤N,在每個(gè)PE中,1≤i≤n,1≤j≤N/2.圖1描述了n=3時(shí)Polar碼的因子圖表示,在圖中共有3個(gè)階段,每個(gè)階段包括4個(gè)PE,每個(gè)PE的信息傳遞過程見圖2所示.在譯碼器的每個(gè)PE中,節(jié)點(diǎn)(i,j)與兩種類型的信息相關(guān):從右到左的信息Li,j和從左到右的信息Ri,j.Li,j和Ri,j都是在相鄰的節(jié)點(diǎn)間傳遞和迭代更新的,信息更新過程與文獻(xiàn)[6]相同,信息首先從最右邊的節(jié)點(diǎn)傳到最左邊的節(jié)點(diǎn),然后從最左邊的節(jié)點(diǎn)傳到最右邊的節(jié)點(diǎn),這個(gè)過程就是BP譯碼算法中的一輪迭代.在迭代中,傳遞的信息都是對數(shù)似然比形式的,迭代公式為

圖2　BP譯碼算法中PE的信息傳遞過程

其中,1≤i≤n,1≤j≤N/2,且

初始信息R1,j(1≤j≤N)定義為

來自于信道的信息Ln+1,j(1≤j≤N)為

2　改進(jìn)的Polar碼的BP譯碼算法

2.1等誤差線性逼近原理

等誤差線性逼近是指每個(gè)逼近的直線段與曲線之間的誤差相等[11],其原理如圖3所示.

圖3　非圓曲線的等誤差線性逼近原理

已知曲線方程y=f(x),直線逼近曲線的誤差設(shè)為δ,令A(yù)(xa,ya)為曲線的起點(diǎn),首先以A點(diǎn)為圓心,δ為半徑作圓,然后作圓與曲線的公切線PT,切點(diǎn)分別為P(xp,yp),T(xt,yt),然后作一條過A點(diǎn)與PT平行的直線AB,點(diǎn)B(xb,yb)為曲線與直線AB的交點(diǎn),則點(diǎn)B即為分段直線的一個(gè)端點(diǎn).然后以B點(diǎn)為起點(diǎn),重復(fù)前面作誤差圓的過程,可以得到所有逼近直線段的端點(diǎn),將相鄰兩點(diǎn)用直線相連即可得到逼近曲線的所有分段直線.

2.2基于等誤差的線性近似函數(shù)

采用上述的基于等誤差線性逼近原理對雙曲正切函數(shù)y=tanh x進(jìn)行等誤差直線逼近.當(dāng)x≥7時(shí),逼近直線取為y=0.999 998,當(dāng)x≤-7時(shí),逼近直線取為y=-0.999 998.當(dāng)選取誤差為δ=0.02,得出雙曲正切函數(shù)y=tanh x的等誤差線性逼近的所有節(jié)點(diǎn)坐標(biāo)為:(-7.0,-0.999 998),(-3.68,-0.998 7), (-1.82,-0.948 8),(-1.24,-0.845 5),(-0.66,-0.5784),(0,0),(0.66,0.5784),(1.24,0.8455), (1.82,0.9488),(3.68,0.9987),(7.0,0.999998).根據(jù)兩點(diǎn)間直線公式求得所有相鄰兩點(diǎn)間的直線方程,由于在點(diǎn)(0,0)兩邊的兩段直線的斜率都是0.876 4,因此可將其合為一段直線.雙曲正切函數(shù)y=tanh x的分段線性近似方程y1(x)=ax+b為

根據(jù)反函數(shù)的性質(zhì),可以得到函數(shù)y=arctanh x的所有分段線性近似方程y2(x)=cx+d為

將算法中的雙曲函數(shù)分別用分段的線性近似函數(shù)代替,則式(2)可以轉(zhuǎn)化為

其中,a,b,c,d是線性近似函數(shù)的系數(shù).

2.3改進(jìn)的Polar碼的BP譯碼算法

在改進(jìn)的Polar碼的BP譯碼算法中,在節(jié)點(diǎn)更新規(guī)則中所傳遞的信息的更新公式為

其中,1≤i≤n,1≤j≤N/2,h(x1,x2)由式(7)定義.

基于等誤差的改進(jìn)的Polar碼的BP譯碼算法步驟如下:

(1)初始化:計(jì)算式(4)中的Ln+1,j的值作為初始信道信息,其中1≤j≤N;

(2)在每輪迭代中,根據(jù)Polar碼的BP譯碼算法的迭代規(guī)則,利用式(8)更新每個(gè)階段的每個(gè)PE的節(jié)點(diǎn)信息;

(3)當(dāng)達(dá)到設(shè)定的迭代次數(shù)T時(shí),進(jìn)行判決:如果j∈Ac或者j∈A&L1,j＞0,則判j=0;否則,判j=1.

3　復(fù)雜度分析和計(jì)算機(jī)仿真

3.1復(fù)雜度分析

SC譯碼算法的時(shí)間復(fù)雜度是O(N log N)[1],其中N是Polar碼的碼長.文獻(xiàn)[5]給出的Polar碼的BP譯碼算法的時(shí)間復(fù)雜度也是O(N log N),其性能要優(yōu)于SC譯碼算法.相比于SC譯碼算法,BP譯碼算法能并行計(jì)算,因此更利于硬件實(shí)現(xiàn).

改進(jìn)的Polar碼的BP譯碼算法只是對原始BP譯碼算法中的雙曲函數(shù)進(jìn)行替代,并沒有改變節(jié)點(diǎn)之間循環(huán)交換信息的規(guī)則以及算法的迭代次數(shù),因此,改進(jìn)的BP譯碼算法和原始的BP譯碼算法的時(shí)間復(fù)雜度是一樣的,它們的運(yùn)算復(fù)雜度的不同主要是由于節(jié)點(diǎn)更新時(shí)的計(jì)算規(guī)律不同而造成的.在原始的BP譯碼算法中,雙曲函數(shù)的計(jì)算中包含了指數(shù)、對數(shù)及除法等運(yùn)算,運(yùn)算復(fù)雜度是指數(shù)的,因此造成的時(shí)延會(huì)比較大,硬件實(shí)現(xiàn)上比較困難;而改進(jìn)的BP譯碼算法中的線性近似函數(shù)僅僅需要乘法和加法運(yùn)算,運(yùn)算復(fù)雜度是線性的,時(shí)延較小,硬件實(shí)現(xiàn)上相對比較簡單.表1給出了雙曲函數(shù)和線性近似函數(shù)的核心運(yùn)算的運(yùn)算復(fù)雜度.

表1　雙曲函數(shù)和線性近似函數(shù)的運(yùn)算復(fù)雜度

表2總結(jié)了各種算法的校驗(yàn)節(jié)點(diǎn)更新的核心運(yùn)算的運(yùn)算復(fù)雜度.原始的BP譯碼算法的節(jié)點(diǎn)更新公式中,式(2)的計(jì)算需要計(jì)算2次tanh x,1次arctanh x,4次乘法;而改進(jìn)的BP譯碼算法的節(jié)點(diǎn)更新公式中,式(7)的計(jì)算僅僅需要3次乘法和3次加法運(yùn)算.

表2　各算法校驗(yàn)節(jié)點(diǎn)更新的運(yùn)算復(fù)雜度

綜合表1和表2可以很容易得出,相比于原始的BP譯碼算法,改進(jìn)的BP譯碼算法大大降低了的校驗(yàn)節(jié)點(diǎn)更新的核心運(yùn)算的運(yùn)算復(fù)雜度,更利于硬件實(shí)現(xiàn).文獻(xiàn)[8]的節(jié)點(diǎn)更新的運(yùn)算復(fù)雜度要比改進(jìn)的BP譯碼算法的運(yùn)算復(fù)雜度略高.

3.2計(jì)算機(jī)仿真

為了驗(yàn)證算法性能,分別對改進(jìn)的BP譯碼算法、原始的BP譯碼算法、原始SC譯碼算法和文獻(xiàn)[8]中的譯碼算法進(jìn)行了對比仿真實(shí)驗(yàn).仿真中采用的信道都是二進(jìn)制輸入的加性高斯白噪聲(Additive White Gaussian Noise,AWGN)信道,調(diào)制方式是基帶二進(jìn)制相移鍵控(Binary Phase Shift Keying,BPSK)調(diào)制,為檢驗(yàn)Polar碼的性能,分別選取了幾種不同碼長、不同碼率的Polar碼進(jìn)行了仿真實(shí)驗(yàn).Polar碼的信息集合A是利用Tal-Vardys方法來選取的[12].

圖4和圖5的參數(shù)設(shè)置為:碼長N為256,碼率R為0.5,迭代次數(shù)T設(shè)置為60次.圖4比較了改進(jìn)的BP譯碼算法、原始的BP譯碼算法、原始SC譯碼算法和文獻(xiàn)[8]中的譯碼算法的誤碼率(Bit Error Rate, BER)性能.從圖4中可以看出,相比于BP譯碼算法,當(dāng)信噪比小于4.5 dB時(shí),改進(jìn)的BP譯碼算法與原始的譯碼算法的BER性能幾乎相同;當(dāng)信噪比大于4.5 d B時(shí),改進(jìn)的BP譯碼算法比原始的譯碼算法的BER性能略差,當(dāng)誤碼率達(dá)到10-6時(shí),改進(jìn)的BP譯碼算法比原始BP譯碼算法的性能差0.1 d B左右.相比于基于SC譯碼算法,改進(jìn)的BP譯碼算法的BER性能要比原始SC譯碼算法和文獻(xiàn)[8]的譯碼算法的BER性能好,當(dāng)誤碼率為10-4時(shí),改進(jìn)的BP譯碼算法比原始SC譯碼算法的BER性能要好0.5 dB,比文獻(xiàn)[8]中的譯碼算法的BER性能要好1.1 d B.

圖4　(256,128)時(shí)Polar碼多種算法的BER性能比較

圖5　(256,128)時(shí)Polar碼多種算法的FER性能比較

圖5比較了各算法的誤幀率(Frame Error Rate,FER)性能.從圖5中可以看出,相比于BP譯碼算法,當(dāng)信噪比小于3 dB時(shí),改進(jìn)的BP譯碼算法與原始的譯碼算法的FER性能差不多;當(dāng)信噪比大于3 dB時(shí),改進(jìn)的BP譯碼算法比原始的譯碼算法的FER性能略差;當(dāng)誤碼率達(dá)到10-5時(shí),改進(jìn)的BP譯碼算法比原始BP譯碼算法的性能差0.2 d B左右.相比于基于的SC譯碼算法,改進(jìn)的BP譯碼算法的FER性能要比SC譯碼算法和文獻(xiàn)[8]的譯碼算法的FER性能好;當(dāng)誤碼率為10-3時(shí),改進(jìn)的BP譯碼算法比原始SC譯碼算法的FER性能好0.4 dB;比文獻(xiàn)[8]中的譯碼算法的FER性能好1.0 dB.由圖4和圖5中可知,在同等條件下,基于BP譯碼算法的性能要比基于SC算法的性能好,因此在下面的圖6和圖7中,主要只比較了基于BP譯碼算法的BER性能.

圖6　R=0.5,T=60時(shí)不同碼長Polar碼的BER性能比較

圖7　N=1 024時(shí)Polar碼的BER性能比較

圖6比較了Polar碼在不同碼長時(shí)改進(jìn)的BP譯碼算法、原始的BP譯碼算法和SC算法的BER性能.

其中碼率R為0.5,迭代次數(shù)T為60次.從圖6中可以看出,當(dāng)碼長N=1 024時(shí),相比于原始的BP譯碼算法,當(dāng)信噪比小于3.5 dB時(shí),改進(jìn)的BP譯碼算法與原始的BP譯碼算法的性能幾乎相同;當(dāng)信噪比大于3.5 d B時(shí),改進(jìn)的BP譯碼算法比原始的BP譯碼算法的性能略差;當(dāng)誤碼率達(dá)到10-6時(shí),改進(jìn)的BP譯碼算法比原始的BP譯碼算法的性能要差0.15 dB左右;碼長相同時(shí)的BP算法的性能要優(yōu)于SC算法的.當(dāng)Polar碼的碼長選取為256時(shí),算法的性能最差;碼長為2 048時(shí)算法的性能最好;即碼長越長,算法的性能越好.

圖7比較了碼率和迭代次數(shù)不同時(shí),碼長N=1 024的Polar碼的改進(jìn)的BP譯碼算法的BER性能.首先考察碼率對BER性能的影響,固定碼長N=1 024,迭代次數(shù)T為60次,選取的碼率分別為0.375、0.5和0.75.從圖7中可知,當(dāng)R=0.375時(shí),改進(jìn)的BP譯碼算法的性能最好;當(dāng)R=0.75時(shí),算法的性能最差;當(dāng)誤碼率達(dá)到10-4時(shí),碼率為0.375時(shí)的性能比碼率為0.5時(shí)的性能好0.4 dB左右;碼率為0.5時(shí)的性能比碼率為0.75時(shí)的性能好1.2 dB左右.其次考察迭代次數(shù)T對BER性能的影響,固定碼長N=1 024,碼率R=0.5,選取了3組不同的迭代次數(shù)分別為60次、40次、30次.從圖7中可以看出,當(dāng)信噪比小于3.0 d B時(shí),迭代次數(shù)大的性能略好,且信噪比越低,其性能的差異越明顯;當(dāng)信噪比大于3.0 d B時(shí),算法所選取的3種不同的迭代次數(shù)對BER性能幾乎沒有影響.由Polar的BP譯碼過程可知,當(dāng)改變碼率時(shí),并沒有改變算法中需要運(yùn)算的節(jié)點(diǎn)的數(shù)目,因此,改變碼率對算法的復(fù)雜度并沒有影響.迭代次數(shù)越大,其運(yùn)算的節(jié)點(diǎn)的數(shù)目越多,因此算法的復(fù)雜度越高.

4　結(jié)束語

筆者提出了一種改進(jìn)的Polar碼的BP譯碼算法,在節(jié)點(diǎn)更新時(shí),改進(jìn)的BP譯碼算法利用等誤差的線性近似函數(shù)來代替算法中的雙曲函數(shù),即用乘法和加法運(yùn)算代替了原始BP譯碼算法中的對數(shù)、指數(shù)和除法運(yùn)算,大大降低了算法的計(jì)算復(fù)雜度,易于硬件實(shí)現(xiàn).仿真結(jié)果表明,在低信噪比時(shí),改進(jìn)的BP譯碼算法的性能與原始BP譯碼算法的性能相同;在高信噪比時(shí),改進(jìn)的BP譯碼算法的性能比原始BP譯碼算法的性能略差;當(dāng)碼長為256,誤碼率為10-6時(shí),改進(jìn)的BP譯碼算法的誤碼率性能比原始的BP譯碼算法退化了0.1 d B;同時(shí),改進(jìn)的BP譯碼算法的性能要比SC算法和已知的相似簡化算法[8]的性能要好.

[1]ARIKAN E.Channel Polarization:a Method for Constructing Capacity Achieving Codes for Symmetric Binary-input Memoryless Channels[J].IEEE Transactions on Information Theory,2009,55(7):3051-3073.

[2]TRIFONOV P.Efficient Design and Decoding of Polar Codes[J].IEEE Transactions on Communications,2012,60 (11):3221-3227.

[3]CHEN K,NIU K,LIN J R.Improving Successive Cancellation Decoding of Polar Codes[J].IEEE Transactions on Communications,2013,61(8):3100-3107.

[4]Jr FORNEY G D.Codes on Graphs:Normal Realizations[J].IEEE Transactions on Information Theory,2001,47(2): 520-548.

[5]ARIKAN E.A Performance Comparison of Polar Codes and Reed-Muller Codes[J].IEEE Communications Letters, 2008,12(6):447-449.

[6]PAMUK A.An FPGA Implementation Architecture for Decoding of Polar Codes[C]//Proceedings of 8th International Symposium on Wireless Communications Systems.Piscataway:IEEE,2011:437-441.

[7]ZHANG Y,LIU A,PAN X,et al.A Modified Belief Propagation Polar Decoder[J].IEEE Communications Letters, 2014,18(7):1091-1094.

[8]XING C,WANG B,ZHAO S M.A Reduced-complexity Successive-cancellation Decoding Algorithm for Polar Codes [C]//The 6th International Congress on Image and Signal Processing.Piscataway:IEEE,2013:1221-1225.

[9]YUAN B,PARHI K K.Architectures for Polar BP Decoders Using Folding[C]//Proceedings of the IEEE International Symposium on Circuits and Systems.Piscataway:IEEE,2014:205-208.

[10]PAPAHARALABOS S,SWEENEY P,EVANS B G,et al.Modified Sum-product Algorithms for Decoding Lowdensity Parity-check Codes[J].IET Communications,2007,1(3):294-300.

[11]侯軍奎.LDPC碼譯碼算法的研究和簡化[D].西安:西安電子科技大學(xué),2014.

[12]TAL I,VARDY A.How to Construct Polar Code[J].IEEE Transactions on Information Theory,2013,59(10):6562 -6582.

(編輯:王 瑞)

Improved BP decoding algorithm for Polar codes

HONG Yinfang,LI Hui,WANG Xinmei
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

In the decoding algorithm for Polar codes,the belief propagation(BP)decoding algorithm in the loglikelihood ratio domain incurs high computation complexity due to the computation of the hyperbolic functions Motivated by this observation we propose an improved BP decoding algorithm.In the node update rules,our method replaces the hyperbolic functions with the linear approximation functions based on the principle of equal error.Compared with the original BP decoding algorithm,the modified BP decoding algorithm is only implemented by addition and multiplication operations,which greatly reduces computation complexity,and simplifies hardware implementation.Simulation results show that the performance of the modified BP decoding algorithm is almost the same as that of the original BP decoding algorithm in the low Signal to Noise Ratio(SNR)region,and in the high SNR region the performance of our method is slightly worse.Compared with the original BP decoding algorithm, the bit error rate(BER)performance of the modified BP decoding algorithm has about 0.1 dB degradation when the length of Polar codes is 256 and the BER is 10-6.

Polar codes;belief propagation(BP)algorithm;equal error;linear approximation; computation complexity

TN911

A

1001-2400(2016)04-0039-06

10.3969/j.issn.1001-2400.2016.04.008

2015-04-09 網(wǎng)絡(luò)出版時(shí)間：2015-10-21

國家973計(jì)劃資助項(xiàng)目(2010CB328300,2012CB316100);國家自然科學(xué)基金資助項(xiàng)目(61201138,61372072)

洪銀芳(1984-),女,西安電子科技大學(xué)博士研究生,E-mail:yfhong@stu.xidian.edu.cn.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.016.html