劉明山，王亞忠，劉珊珊

(吉林大學(xué)通信工程學(xué)院，長春130022)

LDPC碼改進型LBP 譯碼算法研究

劉明山，王亞忠，劉珊珊

(吉林大學(xué)通信工程學(xué)院，長春130022)

針對LDPC(Low Density Parity Check)碼分層(LBP:Layered Belief-Propagation)譯碼算法計算復(fù)雜度高、不易于硬件實現(xiàn)的問題，提出一種改進算法。該算法首先引入函數(shù)f(x)使LBP譯碼算法的計算復(fù)雜度大大降低;同時引入具體參數(shù)校正因子和偏移因子，提升譯碼性能。仿真結(jié)果表明，改進后的算法相比LBP算法在計算復(fù)雜度降低的同時，也提升了譯碼性能，從而達到了易于硬件實現(xiàn)的目的。

LDPC碼;BP譯碼算法;最小和譯碼算法;分層譯碼算法

0 引 言

低密度奇偶校驗碼［1］(LDPC:Low Density Parity Check)屬于線性分組碼的一種，LDPC碼的校驗矩陣是一種低密度矩陣，可構(gòu)造出低復(fù)雜度、高性能的LDPC碼，由于其描述簡單、吞吐量高并具有優(yōu)越的編譯碼性能［2-8］，已經(jīng)吸引了眾多研究者的目光，成為下一代寬帶移動通信系統(tǒng)的主要備選方案。

因此，高效的硬件實現(xiàn)LDPC譯碼器的設(shè)計已經(jīng)成為一個重要的課題，中國移動多媒體廣播(CMMB:China Mobile Multimedia Broadcasting)中的信道編碼使用的也是LDPC碼。除此之外，LDPC碼將在深空通信、光纖通信、移動和固定無線及聲頻傳播等領(lǐng)域中得到廣泛應(yīng)用。

目前主要有兩大類譯碼方法，第1種是基于校驗和統(tǒng)計迭代的比特翻轉(zhuǎn)譯碼算法，簡稱BF算法;第2種是基于概率的置信傳播迭代譯碼算法，簡稱BP算法。

LDPC碼基于軟消息判決的譯碼算法都是以BP譯碼算法為基礎(chǔ)。BP譯碼算法可以分為兩種:概率BP譯碼算法和對數(shù)似然比(LLR:Log-Likelihood Ratio)BP譯碼算法。這兩種算法的本質(zhì)一樣，只是消息的表現(xiàn)形式不同。后續(xù)研究人們提出多種改進算法，或是降低譯碼算法的計算復(fù)雜度，如最小和(MS:Min-Sum)算法;或是提高譯碼算法的性能，如分層(LBP:Layered Belief-Propagation)算法、Shuffled BP算法［2］，它們都是在BP譯碼算法基礎(chǔ)上的改進。

筆者在LBP算法基礎(chǔ)上提出一種改進算法，首先引入函數(shù)f(x)使LBP算法的計算復(fù)雜度大大降低，這必然會帶來譯碼性能的降低，然后引入具體參數(shù)校正因子和偏移因子，可以降低引入f(x)后因近似計算所帶來的誤差，從而提升譯碼性能。通過仿真表明，改進的算法相比LBP算法在計算復(fù)雜度降低的同時，也提升了譯碼性能，易于硬件實現(xiàn)。

1 LDPC碼

LDPC碼是一種優(yōu)秀的線性分組碼。設(shè)線性分組碼LDPC的碼長為n，k為線性分組碼的信息位長度，n-k為線性分組碼的校驗位長度，H為線性分組碼的校驗矩陣，H矩陣的維數(shù)為m×n。H矩陣的每行和一個校驗方程相對應(yīng)，每列和碼字的位相對應(yīng)［3］。H中只有很少數(shù)的非零元素“1”，其余的都是元素“0”，即非零元素的密度很低，因此稱作低密度校驗碼。

LDPC碼可由其校驗矩陣定義。如果校驗矩陣的碼長為N，其每列都有固定數(shù)量的非零元素，并且每列都有 dv個;其每行也有固定數(shù)量的非零元素，并且每行都有 dc個，則 H可記為(N，dv，dc)。(10，3，6)的規(guī)則LDPC碼

相應(yīng)的校驗方程式

LDPC碼可以用二分因子圖［4］表示，二分因子圖可以生動地描述LDPC碼的編譯碼特性。每個Tanner圖和其相應(yīng)的校驗矩陣直接對應(yīng)，式(1)所示校驗矩陣對應(yīng)的Tanner圖如圖1所示。

圖1 規(guī)則LDPC碼二分圖Fig.1 Tanner of regular LDPC

LDPC碼基于軟判決的BP類譯碼算法核心思想是:在每次的迭代過程中得到判決序列，然后開始下一輪的迭代，直到所有校驗方程都滿足，或達到最大迭代次數(shù)，則譯碼結(jié)束。

2 常見譯碼算法

2.1 LLR BP算法

設(shè)信號經(jīng)過信道傳輸和輸入信號經(jīng)過BPSK調(diào)制信號的過程中［5-8］，每個碼字c=(c1，c2，…，cn)映射為序列x=(x1，x2，…，xn)，輸入序列x經(jīng)過傳輸信道，所接收到的序列為y=(y1，y2，…，yn)。再根據(jù)得到的y進行譯碼，最終得到的譯碼序列為^c。

為了便于描述，定義以下符號:M為校驗節(jié)點個數(shù);為變量節(jié)點個數(shù);N(ci)/vj表示與校驗節(jié)點ci相連的比特節(jié)點的集合除以比特節(jié)點表示校驗節(jié)點向比特節(jié)點傳遞的信息;表示比特節(jié)點vj向校驗節(jié)點ci傳遞的信息;mvj表示比特節(jié)點vj的后驗概率信息;Cvj表示比特節(jié)點vj從信道接收的對數(shù)似然信息。

LLR BP譯碼算法［5］步驟如下。

1)初始化。設(shè)定最大迭代次數(shù)Imax

2)迭代處理。

①校驗節(jié)點消息處理。計算變量節(jié)點傳向校驗節(jié)點的消息

②變量節(jié)點的消息處理。計算變量節(jié)點傳向校驗節(jié)點的消息

③譯碼判決。對所有變量節(jié)點計算硬判決消息

如果mvj＞0，則=0，否則，=1。

3)停止。

LLR BP譯碼算法能有效地提高譯碼速度，降低譯碼延時［9-12］。因為其迭代過程是并行實現(xiàn)的。然而該算法引入了tanh函數(shù)，而tanh函數(shù)計算很復(fù)雜，并且要占用很多硬件資源，所以譯碼器電路非常復(fù)雜，不利于硬件實現(xiàn)。

2.2 最小和算法

最小和算法［6］在UP-BP算法的基礎(chǔ)上進行了改進，主要對LLR BP算法中校驗節(jié)點消息處理的公式做了改進，依據(jù)原理是利用tanh(x)、tanh-1(x)奇函數(shù)的性質(zhì)。

最小和算法在處理校驗節(jié)點消息時只含有比較運算和加法運算，特別適合硬件實現(xiàn)，但同時其譯碼性能有所降低［10］。

2．3 分層算法

BP算法是一種并行的迭代譯碼算法，在一次迭代過程中，首先更新所有的校驗節(jié)點信息，然后更新所有的變量節(jié)點信息，而校驗節(jié)點的更新只能利用上一次迭代過程中的變量節(jié)點信息。在這種情況下，分層算法［7］(Layered BP)被提出，分層算法能盡可能早地利用已經(jīng)更新過的變量節(jié)點的信息，從而可以達到加快碼字的收斂迭代速度的目的。

LBP算法譯碼步驟如下。

1)初始化。設(shè)定最大迭代次數(shù)Imax，

2)迭代步驟:i=0，1，…，M-1。

①校驗節(jié)點更新

②后驗概率更新

LBP算法在迭代過程中和BP算法有明顯區(qū)別，LBP算法開始時不更新所有的校驗節(jié)點的信息，而是更新所有校驗節(jié)點中其中一個校驗節(jié)點信息，接著找到所有與這個校驗節(jié)點連接的變量節(jié)點，然后更新找到的變量節(jié)點信息;上述過程結(jié)束后，再更新另一個校驗節(jié)點信息，所有校驗節(jié)點信息都更新完畢，這一次的迭代過程才結(jié)束［13-15］。

3 改進算法

筆者提出了一種改進型譯碼算法，新的譯碼算法把分層譯碼算法和改進的最小和算法相結(jié)合，使校驗節(jié)點的更新過程簡化，降低譯碼的復(fù)雜度，并且提升譯碼性能。

類似最小和譯碼算法對LLR BP譯碼算法的改進，由于tanh函數(shù)本身的計算復(fù)雜度較高，所以首先引入函數(shù)=-ln(tanh(x/2))降低函數(shù)的計算復(fù)雜度。由于采用了近似計算，使譯碼性能降低，因此，筆者又引入?yún)?shù)α，為了方便起名為校正因子。對式(9)進行簡化

從式(11)可以看出，校驗節(jié)點更新公式只需進行兩個運算:第1個是符號乘積的運算;第2個是最小值的計算。所以類似最小和算法，引入函數(shù)的算法雖然能降低計算復(fù)雜度且使計算簡化，但由于引入了近似計算，必然會使譯碼性能降低。

為了解決近似計算所帶來的性能損失，筆者引入?yún)?shù)校正因子α，由于近似算法使檢驗節(jié)點公式的幅度變大，這里取值0＜α＜1，這樣就可以減小校驗節(jié)點更新時的幅度，使與真實的幅度更加接近。從而使檢驗節(jié)點的更新公式在較低的復(fù)雜度和好的性能之間取得一個平衡。

筆者還提出另一種改進算法，在引入f(x)的基礎(chǔ)上，引入?yún)?shù)β，為了方便稱其為偏移因子，則校驗節(jié)點的更新公式可以化簡為

這種改進方法使模值小于β的校驗節(jié)點信息為0。為了獲得相對最好的譯碼性能。校正因子和偏移因子應(yīng)該隨著不同的迭代過程以及信噪比的不同做出相應(yīng)的變化，但實現(xiàn)相當復(fù)雜，雖然可以達到最好的譯碼性能，但是極大地增加了譯碼復(fù)雜度。因此綜合權(quán)衡，在仿真實驗中對所有的校正因子α和偏移因子β都采取統(tǒng)一的參數(shù)。為了仿真方便，筆者把改進的譯碼算法分別稱為NLBP和OLBP譯碼算法。

NLBP、OLBP譯碼算法和LBP算法在譯碼過程中僅僅是水平過程不一樣，為了比較改進后的算法和LBP算法在計算復(fù)雜度上的區(qū)別，只需要比較水平過程，NLBP、OLBP譯碼算法和LBP算法的計算復(fù)雜度之間的區(qū)別見表1所示。

表1 NLBP、OLBP和LBP算法運算復(fù)雜度比較Tab.1 NLBP、OLBP and LBP algorithm computational complexity

表1中僅僅列出了NLBP、OLBP和LBP算法校驗節(jié)點更新時的計算復(fù)雜度，因為NLBP、OLBP算法和LBP算法的其他運算過程一樣，把比較運算當作加法運算對待，其中dc表示校驗矩陣中每行非零個數(shù)，符號「?表示取整。通過比較發(fā)現(xiàn)，改進后的NLBP、OLBP算法的計算復(fù)雜度大大小于改進之前的LBP算法。

4 NLBP、OLBP算法仿真分析

為了驗證改進譯碼算法的性能，以Matlab軟件作為平臺進行實驗仿真，采用BPSK調(diào)制、AWGN信道;選用規(guī)則LDPC碼，它的碼長為256，碼率R=1/2。對最小和算法(MS)、分層算法(LBP)以及筆者中改進的算法(NLBP、OLBP)進行仿真，比較譯碼性能。

4.1 α和β對算法性能的影響

信噪比分別取2．0以及3．0時，在α和β取不同值時分別對兩種改進的算法(NLBP、OLBP)在最大迭代次數(shù)為20時做了算法仿真，得到了誤碼率性能曲線。圖2表示了α在取不同值時(0.65～1.0)對NLBP算法性能的影響，圖3表示了β取不同值時(0～0.40)對OLBP算法性能的影響。

圖2 α對算法性能影響Fig.2 Effect ofαto algorithm performance

圖3 β對算法性能影響Fig.3 Effect ofβto algorithm performance

從圖2可以看出，無論在信噪比為2 dB或為3 dB，NLBP算法的誤碼率都是隨著α的逐漸增大先減小后增大，并且α取0.75時算法的性能達到最佳，系統(tǒng)的誤碼率達到最低。

從圖3可以看出，無論在信噪比為2 dB或3 dB，OLBP算法的誤碼率都是隨著β的逐漸增大先減小后增大，并且β取0．10時，算法的性能達到最佳，系統(tǒng)的誤碼率達到最低。而在β＞0．25時，算法的性能不如改進前的性能，這是因為如果偏移量β取值較大，檢驗節(jié)點的更新公式的幅度會比改進前小。故在NLBP和OLBP算法中，可以將校正因子α和偏移因子β看作常數(shù)，其中α=0．75，β=0.10。

4.2 改進后的算法性能比較

最小和算法、分層算法、NLBP(α=0.75)譯碼算法和OLBP(β=0.10)譯碼算法在最大迭代次數(shù)為10時的誤碼率性能曲線如圖4所示，在最大迭代次數(shù)為20時的誤碼率性能曲線如圖5所示。

圖4 最大迭代次數(shù)10Fig.4 Maximum iteration 10

圖5 最大迭代次數(shù)20Fig.5 Maximum iteration 20

從圖4，圖5可以看出，無論最大迭代次數(shù)是10還是20，分層算法的性能都要優(yōu)于最小和算法，而改進后的NLBP和OLBP兩種算法的性能都要優(yōu)于分層算法和最小和算法。而最大迭代次數(shù)的不同算法仿真的性能也有所差別，隨著最大迭代次數(shù)從10增加到20，4種仿真算法的性能都有所提高。

在最大迭代次數(shù)為10時，OLBP算法的性能一直優(yōu)于分層算法，NLBP在性能上一直優(yōu)于其他3種算法，而最小和算法一直是BBER性能最差的。在BBER=10-2時，NLBP算法比分層算法性能提高了約0.3 dB，OLBP算法也比分層算法性能提高了約0.1 dB;在BBER=10-3時，NLBP算法比分層算法性能提高了約0.5 dB，OLBP算法也比分層算法性能提高了約0.3 dB。在最大迭代次數(shù)為20時，NLBP算法和OLBP算法的性能都要優(yōu)于分層算法和最小和算法，當信噪比小于3.5時，OLBP算法在性能上優(yōu)于NLBP算法，而在信噪比大于3.5 dB后，NLBP算法在性能上又優(yōu)于OLBP算法，在BBER=10-3時，NLBP算法比分層算法性能提高了約0.2 dB，OLBP算法也比分層算法性能提高了約0.3 dB;在BBER=10-4時，NLBP算法和OLBP算法的性能相近，都比分層算法的性能提高約0.3 dB。

5 結(jié) 語

LDPC碼是一種線性分組碼，具備很強的糾錯能力，當LDPC碼的譯碼算法為并行算法時，在硬件實現(xiàn)時可以實現(xiàn)完全并行的操作。筆者在分層算法和最小和算法的基礎(chǔ)上進行了算法的改進，改進的算法通過引入?yún)?shù)改變校驗節(jié)點消息的更新數(shù)據(jù)，能有效地降低由于近似計算所帶來的誤差。改進后的算法和分層算法相比，硬件上只增加了少量的加法器和乘法器，所以解碼電路較為簡單，易于實現(xiàn)。仿真結(jié)果表明，改進的NLBP和OLBP算法相比LBP算法在計算復(fù)雜度大大降低的同時，也提升了譯碼性能，從而達到了易于硬件實現(xiàn)的目的，這使LDPC碼具有更好的應(yīng)用潛力，能更好地應(yīng)用在光纖通信、衛(wèi)星數(shù)字視頻、移動和固定無線等領(lǐng)域中。

［1］GALLAGER R G.Low-Density Parity-Check Codes［J］.IRE Transactions on Information Theory，1962，8(1):21-28.

［2］KSCHISCHANG FR，F(xiàn)REY B J，LOELIGERH A.Factor Graphs and the Sum-Product Algorithm［J］.IEEE Transactions on Information Theory，2001，47(2):498-519.

［3］BERROU A，GLAVIEUX PTHITIMAJSHIMA.Near Shannon Limit Error-Correcting Coding and Decoding:Turbo-Codes［C］∥IEEE International Conference on Communications，1993.ICC 93.Nagaoka，Japan:［s.n.］，1993，2:1064-1070.

［4］TANNER R M.A Recursive Approach to Low Complexity Codes［J］.IEEE Tran on Inform Theory，1981，27(5):533-547.

［5］MACKAY D JC，NEALR M.Near Shannon Limit Performance of Low-Density Parity-Check Codes［J］.Electronics Letters，1996，32(18):1645-1646.

［6］袁東風，張海剛.LDPC碼理論與應(yīng)用［M］.北京:人民郵電出版社，2008. YUAN Dongfeng，ZHANG Haigang. LDPC Code Theory and Application［M］. Beijing: People's Posts and Telecommunications Press，2008.

［7］HOCEVAR D.A Reduced Complexity Decoder Architecture via Layered Decoding of LDPC Codes［C］∥Proc Signal Processing Systems SIPS 2004.Seoul，Korea:［s.n.］，2004:107-112.

［8］HAMMING RW.Error Detecting and Error Correcting Codes［J］.Bell System Technical Journal，1950，29(7):147-160.

［9］傅祖蕓.信息論基礎(chǔ)理論與應(yīng)用［M］.北京:電子工業(yè)出版社，2001. FU Zuyun.Information Theory-Fundamental Theory and Application［M］.Beijing:Publishing House of Electronics Industry，2001.

［10］王眾，祝宇鴻.基于LDPC碼的HARQ系統(tǒng)仿真［J］.吉林大學(xué)學(xué)報:信息科學(xué)版，2011，29(5):395-400. WANG Zhong，ZHU Yuhong.HARQ System Simulation Based on LDPC Code［J］.Journal of Jilin University:Information Science Edition，2011，29(5):395-400.

［11］LIU Yuanhua，ZHANG Meiling.Quasi-Cyclic LDPC Codes with High-Rate and Low Error Floor Based on Euclidean Geometries［J］.Journal of China Universities of Posts and Telecommunications，2012，19(2):96-99.

［12］MING Yangyang，YANG Bo.Rate Estimate for Regular LDPCA Codec in Distributed Video Coding［J］.Journal of China Universities of Posts and Telecommunications，2012，19(1):50-54.

［13］WANG Xiuni，MA Xiao.Design of Efficiently Encodable Nonbinary LDPCCodes for Adaptive Coded Modulation［J］.Science China:Information Sciences，2014，57(2):1-11.

［14］LIU Bin，GAO Jun.Weighted Symbol-Flipping Decoding Algorithm for Nonbinary LDPC Codes with Flipping Patterns［J］. Journal of Systems Engineering and Electronics，2011，22(5):848-855.

［15］ZHANG Lijun，LI Bing.Constructions of QC LDPC Codes Based on Integer Sequences［J］.Science China:Information Sciences，2014，57(4):1-14.

(責任編輯:劉東亮)

Research on Modified LBPDecoding Algorithm of LDPC Codes

LIU Mingshan，WANG Yazhong，LIU Shanshan

(College of Communication Engineering，Jilin University，Changchun 130022，China)

To solve the problem of high complexity and difficult implementation in hardware of LBP(Layered Belief-Propagation)algorithm.A modified decoding algorithm is proposed based on LBP algorithm，a function

low density parity check(LDPC)codes;belief propagation(BP)algorithm;min sum algorithm; layered belief propagation algorithm

TN911.22

A

1671-5896(2015)04-0367-06

2014-10-09

劉明山(1965— )，男，山東掖縣人，吉林大學(xué)副教授，主要從事無線通信、智能信息處理研究，(Tel)86-13504314285 (E-mail)liums@jlu.edu.cn。

f(x)is introduced in the first step in order to reduce its complexity.Specific parameters correction factor and offset factor are introduced in the second step in order to improve its decoding performance.The simulation results demonstrate that the modified decoding algorithm reduces the complexity and improves the decoding performance compared to LBP algorithm which facilitates the hardware.