LDPC碼改進(jìn)型LBP 譯碼算法研究

劉明山，王亞忠，劉珊珊

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

LDPC碼改進(jìn)型LBP 譯碼算法研究

劉明山，王亞忠，劉珊珊

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

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

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

0 引 言

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

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

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

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

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

1 LDPC碼

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

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

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

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

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

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

2 常見(jiàn)譯碼算法

2.1 LLR BP算法

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

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

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

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

2)迭代處理。

①校驗(yàn)節(jié)點(diǎn)消息處理。計(jì)算變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的消息

②變量節(jié)點(diǎn)的消息處理。計(jì)算變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的消息

③譯碼判決。對(duì)所有變量節(jié)點(diǎn)計(jì)算硬判決消息

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

3)停止。

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

2.2 最小和算法

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

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

2．3 分層算法

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

LBP算法譯碼步驟如下。

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

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

①校驗(yàn)節(jié)點(diǎn)更新

②后驗(yàn)概率更新

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

3 改進(jìn)算法

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

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

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

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

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

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

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

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

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

4 NLBP、OLBP算法仿真分析

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

4.1 α和β對(duì)算法性能的影響

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

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

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

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

從圖3可以看出，無(wú)論在信噪比為2 dB或3 dB，OLBP算法的誤碼率都是隨著β的逐漸增大先減小后增大，并且β取0．10時(shí)，算法的性能達(dá)到最佳，系統(tǒng)的誤碼率達(dá)到最低。而在β＞0．25時(shí)，算法的性能不如改進(jìn)前的性能，這是因?yàn)槿绻屏喀氯≈递^大，檢驗(yàn)節(jié)點(diǎn)的更新公式的幅度會(huì)比改進(jìn)前小。故在NLBP和OLBP算法中，可以將校正因子α和偏移因子β看作常數(shù)，其中α=0．75，β=0.10。

4.2 改進(jìn)后的算法性能比較

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

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

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

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

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

5 結(jié) 語(yǔ)

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

(責(zé)任編輯:劉東亮)

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é)副教授，主要從事無(wú)線通信、智能信息處理研究，(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.