一種改進的Polar碼的BP譯碼算法

洪銀芳,李 暉,王新梅

(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071)

一種改進的Polar碼的BP譯碼算法

洪銀芳,李 暉,王新梅

(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071)

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

信道極化碼;置信度傳播算法;等誤差;線性近似;計算復雜度

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

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

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

1　Polar碼及其BP譯碼算法

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

圖1　n=3時Polar碼的因子圖表示

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

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

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

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

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

2　改進的Polar碼的BP譯碼算法

2.1等誤差線性逼近原理

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

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

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

2.2基于等誤差的線性近似函數

采用上述的基于等誤差線性逼近原理對雙曲正切函數y=tanh x進行等誤差直線逼近.當x≥7時,逼近直線取為y=0.999 998,當x≤-7時,逼近直線取為y=-0.999 998.當選取誤差為δ=0.02,得出雙曲正切函數y=tanh x的等誤差線性逼近的所有節點坐標為:(-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).根據兩點間直線公式求得所有相鄰兩點間的直線方程,由于在點(0,0)兩邊的兩段直線的斜率都是0.876 4,因此可將其合為一段直線.雙曲正切函數y=tanh x的分段線性近似方程y1(x)=ax+b為

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

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

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

2.3改進的Polar碼的BP譯碼算法

在改進的Polar碼的BP譯碼算法中,在節點更新規則中所傳遞的信息的更新公式為

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

基于等誤差的改進的Polar碼的BP譯碼算法步驟如下:

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

(2)在每輪迭代中,根據Polar碼的BP譯碼算法的迭代規則,利用式(8)更新每個階段的每個PE的節點信息;

(3)當達到設定的迭代次數T時,進行判決:如果j∈Ac或者j∈A&L1,j＞0,則判j=0;否則,判j=1.

3　復雜度分析和計算機仿真

3.1復雜度分析

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

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

表1　雙曲函數和線性近似函數的運算復雜度

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

表2　各算法校驗節點更新的運算復雜度

綜合表1和表2可以很容易得出,相比于原始的BP譯碼算法,改進的BP譯碼算法大大降低了的校驗節點更新的核心運算的運算復雜度,更利于硬件實現.文獻[8]的節點更新的運算復雜度要比改進的BP譯碼算法的運算復雜度略高.

3.2計算機仿真

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

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

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

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

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

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

圖7　N=1 024時Polar碼的BER性能比較

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

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

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

4　結束語

筆者提出了一種改進的Polar碼的BP譯碼算法,在節點更新時,改進的BP譯碼算法利用等誤差的線性近似函數來代替算法中的雙曲函數,即用乘法和加法運算代替了原始BP譯碼算法中的對數、指數和除法運算,大大降低了算法的計算復雜度,易于硬件實現.仿真結果表明,在低信噪比時,改進的BP譯碼算法的性能與原始BP譯碼算法的性能相同;在高信噪比時,改進的BP譯碼算法的性能比原始BP譯碼算法的性能略差;當碼長為256,誤碼率為10-6時,改進的BP譯碼算法的誤碼率性能比原始的BP譯碼算法退化了0.1 d B;同時,改進的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].西安:西安電子科技大學,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 網絡出版時間：2015-10-21

國家973計劃資助項目(2010CB328300,2012CB316100);國家自然科學基金資助項目(61201138,61372072)

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

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.016.html