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

鄭偉，馬曉越，趙成晨

(河北大學(xué) 電子信息工程學(xué)院 河北省數(shù)字醫(yī)療工程重點實驗室，河北 保定 071002)

?

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

鄭偉，馬曉越，趙成晨

(河北大學(xué) 電子信息工程學(xué)院 河北省數(shù)字醫(yī)療工程重點實驗室，河北 保定 071002)

通過對LDPC碼經(jīng)典的BP譯碼算法進(jìn)行研究，針對算法譯碼復(fù)雜度非常大、迭代次數(shù)多、不利于硬件實現(xiàn)的問題，提出了一種改進(jìn)的BP譯碼算法.改進(jìn)算法通過實時監(jiān)控在連續(xù)3次迭代中譯碼是否穩(wěn)定來減少在信噪比低于譯碼閾值時的迭代次數(shù).同時，在變量消息更新過程中對傳遞的校驗信息進(jìn)行數(shù)據(jù)約束,防止由于數(shù)據(jù)溢出而導(dǎo)致的譯碼失敗.仿真結(jié)果表明，改進(jìn)的BP算法，在性能損失不大的情況下可以有效地降低譯碼的復(fù)雜度，從而更利于硬件的實現(xiàn).

LDPC碼；BP譯碼算法；迭代次數(shù)；數(shù)據(jù)約束

深空通信一般是指地球上的實體與處于月球及月球以外的宇宙空間中的航天器之間的通信，其難點是信息傳輸距離遠(yuǎn)，時延大，信號衰減嚴(yán)重.采用信道編碼，尤其是高性能的信道編碼可以提高信號接收能力，帶來較高的編碼增益，其中低密度奇偶校驗碼(low density parity check code,LDPC)和Turbo碼就是2種優(yōu)秀的信道編碼，而且深空探測裝置價格一般比較昂貴，為了獲得較好的譯碼性能，往往采用復(fù)雜度較高譯碼算法，雖然這種算法也許只帶來很少的編碼增益，但這對于深空通信來說是必然的選擇[1].

LDPC碼是Gallager于20世紀(jì)60年代提出的一種性能接近Shannon極限的線性分組碼[2].但是由于當(dāng)時硬件條件和計算機(jī)條件的限制，使LDPC碼在此后的很長時間內(nèi)并未受到應(yīng)有的重視.后來隨著計算機(jī)技術(shù)的快速發(fā)展，以及眾多學(xué)者重新對它進(jìn)行了研究發(fā)現(xiàn)LDPC碼與Turbo碼相比具有以下優(yōu)勢：譯碼為并行迭代，運算量較低；結(jié)構(gòu)并行，在硬件上易實現(xiàn)；碼率可任意構(gòu)造，靈活性更高；錯誤平層低，可應(yīng)用于深空通信、磁盤存儲工業(yè)等對誤碼率要求苛刻的場合；同時進(jìn)一步完善了LDPC碼的相關(guān)理論，使得LDPC碼成為編碼界繼Turbo碼之后最受關(guān)注的焦點.

LDPC碼的譯碼方法主要有2種: 基于硬判決的比特翻轉(zhuǎn)譯碼算法，簡稱BF算法和基于軟判決的置信傳播迭代譯碼(Belief propagation)算法，簡稱BP算法[3].BP算法根據(jù)消息在傳遞過程中的不同表現(xiàn)形式可以分為概率域BP算法和對數(shù)似然比(Log-likelihood Ratio,LLR)BP算法.概率域BP算法的消息用概率形式表示，相應(yīng)的LLR-BP算法的消息用對數(shù)似然比表示.目前研究比較廣泛的是BP譯碼算法和在此基礎(chǔ)上改進(jìn)的各種算法[4-9].對數(shù)域的BP算法(LLR-BP)相較于概率域的BP譯碼算法將大量的乘法運算變?yōu)榧臃ㄟ\算；最小和算法(Min-Sum)減少了節(jié)點更新的計算復(fù)雜度；Normalized Min-Sum算法和Offset Min-Sum算法[10]主要用于補(bǔ)償Min-Sum算法由于降低復(fù)雜度所引起的性能損失.

深空通信領(lǐng)域?qū)幋a增益具有較高的要求，其中BP譯碼算法在所有算法中譯碼性能最好，但是其譯碼復(fù)雜度比較高,不利于硬件的實現(xiàn).本文針對以上問題，在BP算法的基礎(chǔ)上提出了一種改進(jìn)的BP算法，該算法通過引入校驗子實時監(jiān)控譯碼是否穩(wěn)定.同時，在變量消息更新過程中對傳遞的校驗信息進(jìn)行數(shù)據(jù)約束，防止由于數(shù)據(jù)溢出而導(dǎo)致的譯碼失敗.通過實驗仿真表明，改進(jìn)的算法能夠在譯碼性能損失不大的情況下，降低譯碼復(fù)雜度，易于硬件實現(xiàn).

1 LDPC碼

LDPC碼是一種具有稀疏性的線性分組碼，所謂稀疏性是指校驗矩陣中只有數(shù)量很少的元素為“1”，大部分都為“0”.LDPC碼可以用校驗矩陣H表示，若H的維數(shù)為(m,n)且為滿秩，那么LDPC碼的碼長為n，信息位為前k=n-m個，校驗位為后m個.LDPC碼一般可以表示為(n,k)，其碼率為R=k/n.

LDPC碼可以由其校驗矩陣H唯一確定，式(1)、(2)為(8，2，4)LDPC碼的校驗矩陣，從式(1)、(2)看出H矩陣的行重和列重分別為4和2.

(1)

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

(2)

除了用矩陣形式來表示LDPC碼外，利用Tanner圖表示也是一種較為方便的方法，它可以生動形象地描述LDPC碼的編譯碼的性能.Tanner圖是一種雙向圖，可用節(jié)點的集合來表示.其中，H矩陣的行向量對應(yīng)Tanner圖中的校驗節(jié)點；H矩陣的列向量對應(yīng)于Tanner圖中的變量節(jié)點.式(1)所示校驗矩陣對應(yīng)的Tanner圖如圖1所示，c1～c4表示校驗節(jié)點，v1～v8表示變量節(jié)點.

2 BP譯碼算法

BP譯碼算法的主要思想就是在每一次的迭代過程中，利用從信道中接收到的信息，通過在變量節(jié)點和校驗節(jié)點之間不斷地進(jìn)行信息的傳遞和迭代運算進(jìn)行譯碼.BP算法的大致過程包括：初始化、信息處理和硬判決，其中信息的處理過程包括校驗節(jié)點的信息處理和變量節(jié)點的信息處理.

圖1 (8，2，4)LDPC碼的Tanner圖Fig.1 (8,2,4)Tanner graph of the LDPC codes

在信息傳輸?shù)倪^程中，信道編碼后得到二進(jìn)制碼字序列x=(x1,x2,…，xn)，該序列采用BPSK調(diào)制y=2x-1映射為y=(y1,y2,…，yn)，然后再輸入高斯白噪聲(AWGN)信道后得到輸出序列z=(z1,z2,…，zn).在譯碼過程中，為簡單定義如下：c=(c1,c2,…，cn)為譯碼得到的序列；rij(x)(x=0,1)表示校驗節(jié)點j傳遞給變量節(jié)點i的信息；qij(x)(x=0,1)表示變量節(jié)點i傳遞給校驗節(jié)點j的信息；R(j)表示與校驗節(jié)點j相連的變量節(jié)點i的集合.C(i)表示與變量節(jié)點i相連的校驗節(jié)點j的集合；R(j)/i表示除i外與校驗節(jié)點j相連的變量節(jié)點的集合；C(i)/j表示除j外與變量節(jié)點i相連的校驗節(jié)點的集合.

BP譯碼算法的大致步驟如下.

1)初始化

在已知信道先驗知識的情況下，計算信道傳遞給變量節(jié)點的初始概率Pi(1)=P(xi=1)和Pi(0)=1-Pi(1)(i=1,2,…，n)，然后設(shè)定變量節(jié)點i傳向校驗節(jié)點j的初始消息：

qij(0)=Pi(0),

(3)

qij(1)=Pi(1).

(4)

2)校驗節(jié)點的信息處理 計算變量節(jié)點傳向校驗節(jié)點的后驗概率.

(5)

(6)

3)變量節(jié)點的信息處理 由校驗節(jié)點的后驗概率計算變量節(jié)點的后驗概率.

利用步驟2)的rij(0)和rij(1)更新qij(0)和qij(1)，其計算公式為

(7)

(8)

其中，αij為校正因子，滿足qij(0)+qij(1)=1.

4)硬判決 對所有變量節(jié)點計算硬判決信息為

(9)

(10)

其中，αi為校正因子，滿足qi(0)+qi(1)=1.

根據(jù)判決條件做出硬判決，當(dāng)qi(1)>qi(0)時，令ci=1；反之令ci=0.得到全部譯碼輸出序列c.若此時滿足

HcTmod 2=0，

(11)

則譯碼停止，否則繼續(xù)進(jìn)行上述步驟，直至達(dá)到預(yù)先設(shè)定最大迭代次數(shù)，譯碼結(jié)束.BP譯碼算法流程圖如圖2所示.

圖3為BP、LLR-BP、Min-Sum 3種不同譯碼算法性能比較，仿真中利用IEEE802.16e標(biāo)準(zhǔn)LDPC碼的校驗矩陣的準(zhǔn)雙對角線結(jié)構(gòu)進(jìn)行快速編碼，再分別利用上述3種不同算法進(jìn)行譯碼，其中選用的碼長為580，碼率為R=1/2，迭代次數(shù)為15.從圖3可以看出，BP算法、LLR-BP算法、Min-Sum算法的譯碼性能是依次降低的，3種算法在相同信噪比(Signal-noise ratio,SNR)的情況下，誤碼率(bit error rate,BER)依次升高，這是因為LLR-BP算法是BP算法在對數(shù)域的計算，Min-Sum是在對數(shù)域的基礎(chǔ)上取近似，故譯碼性能依次降低.由于在深空通信領(lǐng)域?qū)ψg碼性能要求比較高，故本文選用BP算法進(jìn)行研究和改進(jìn).

圖2 BP譯碼算法流程Fig.2 Flowchart of BP decoding algorithm

圖3 BP、LLR-BP、Min-Sum譯碼算法性能比較Fig.3 Comparison of BP，LLR-BP，Min-Sum decoding algorithm performance

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

當(dāng)信道中信噪比較低時，隨著迭代次數(shù)的增加節(jié)點之間交換的有效信息越來越少，當(dāng)?shù)_(dá)到一定次數(shù)后，節(jié)點之間不再交換有效信息，再增加迭代次數(shù)并不能使誤碼率降低，即迭代次數(shù)不需要達(dá)到最大就可使譯碼輸出的誤碼率穩(wěn)定，因此，需要設(shè)置終止準(zhǔn)則來停止譯碼.本文通過引入校驗子在連續(xù)3次迭代過程中是否穩(wěn)定來判定是否結(jié)束循環(huán)[6，11].現(xiàn)定義校驗子為z=HcTmod2，在每次迭代過程中，若式(11)滿足條件，則表示譯碼正確；若式(11)不滿足條件的話，判斷校驗子在連續(xù)3次迭代過程中非零元素的數(shù)目是否保持不變,若不變，則譯碼錯誤停止迭代；若變化，則繼續(xù)進(jìn)行迭代，直到達(dá)到最大迭代次數(shù).

同時考慮到在信息傳遞過程中有很多接近0的小數(shù)存在，故在進(jìn)行連乘等運算時很容易出現(xiàn)數(shù)據(jù)的溢出，導(dǎo)致譯碼失敗，故改進(jìn)的算法在上述的基礎(chǔ)上加入了數(shù)據(jù)約束[12].在變量節(jié)點更新過程中存儲的浮點信息均為單精度32位的浮點數(shù)，即在式(7)、(8)校驗節(jié)點信息乘積過程中產(chǎn)生的浮點數(shù)很容易超出32位的表示范圍，使數(shù)據(jù)溢出，導(dǎo)致譯碼失敗.針對此問題，在進(jìn)行乘積之前對rij(0)和rij(1)進(jìn)行數(shù)據(jù)約束：若rij(0)和rij(1)的絕對值小于10-N則令其為10-N，以保證相乘的信息在其表示范圍內(nèi)，從而避免了數(shù)據(jù)溢出的問題.改進(jìn)BP算法的程序流程如圖4所示.

圖5為當(dāng)N取不同值時對BP算法性能的影響，從圖5中可以看出，加入數(shù)據(jù)約束后的譯碼性能稍有降低，但由于對數(shù)據(jù)進(jìn)行了約束，才能有效地防止數(shù)據(jù)溢出，保證譯碼的正確性.當(dāng)為4時譯碼性能最接近BP算法，故取10-4作為數(shù)據(jù)約束值.

圖4 改進(jìn)BP譯碼算法流程Fig.4 Flowchart of improvement BP decoding algorithm

圖5 N的不同取值對譯碼性能的影響Fig.5 Effect of different values of N on decoding performance

4 性能仿真

為了驗證碼長對譯碼算法性能的影響，在迭代次數(shù)固定為30時，分別選用碼長為150、310、630、1 270的LDPC碼進(jìn)行仿真，實驗結(jié)果如圖6所示.從圖6可以看出，碼長為150的LDPC碼譯碼性能最差，碼長為1 270的LDPC碼譯碼性能最好，即在相同碼率與迭代次數(shù)的情況下，隨著碼長的增加，LDPC碼的譯碼性能越來越好.

為了驗證迭代次數(shù)對譯碼性能的影響，在碼長固定為1 270時，選用不同迭代次數(shù)對譯碼性能進(jìn)行比較，實驗結(jié)果如圖7所示.從圖7可以看出，當(dāng)?shù)螖?shù)為5時，譯碼性能最差，隨著迭代次數(shù)的增加曲線的收斂速度越快，譯碼性能越好，即在相同碼率與碼長的情況下，隨著迭代次數(shù)的增加，譯碼性能越來越好.

為了驗證改進(jìn)BP算法的性能，以matlab作為實驗平臺進(jìn)行仿真，仿真選用的是IEEE802.16e標(biāo)準(zhǔn)中的碼長為1 270，碼率為R=1/2的規(guī)則LDPC碼.圖8為改進(jìn)的BP算法、原始BP算法、文獻(xiàn)[6]BP算法3者譯碼性能比較，圖9為3者迭代次數(shù)比較.

圖6 碼長對譯碼性能的影響Fig.6 Effect of code length to decoding performance

圖7 迭代次數(shù)對譯碼性能的影響Fig.7 Effect of iterations to decoding performance

從圖8可以看出，當(dāng)處于較低SNR條件下時，改進(jìn)的BP算法與上述2種算法的收斂速度幾乎完全一致，而當(dāng)SNR較高時，改進(jìn)BP算法收斂速度相比于其他2種算法稍有下降.

從圖9可以看出當(dāng)信噪比較低時，改進(jìn)BP算法與文獻(xiàn)[6]BP算法的迭代次數(shù)相同且比原始BP算法相比有大幅的下降；當(dāng)信噪比較高時,改進(jìn)BP算法與原始BP算法的迭代次數(shù)相同且比文獻(xiàn)[6]BP算法的低.所以改進(jìn)的BP算法能夠以較低的迭代次數(shù)滿足性能的要求，從而在譯碼性能和復(fù)雜度上取得一個良好的折衷.

圖8 3者譯碼性能比較Fig.8 Three decoding performance comparison

圖9 3者迭代次數(shù)比較Fig.9 Comparison of three methods of iterations

5 結(jié)束語

經(jīng)過仿真驗證,本文提出的LDPC碼的改進(jìn)BP譯碼算法相對于原始的BP譯碼算法,可以降低在信噪比較低的條件下的譯碼迭代次數(shù)，同時有效地防止了由于數(shù)據(jù)溢出導(dǎo)致的譯碼失敗.BP譯碼算法的迭代次數(shù)的多少和譯碼的正確與否直接影響著其實際應(yīng)用.改進(jìn)的算法在保證譯碼性能和譯碼正確性的前提下，降低了譯碼的復(fù)雜度，在一定程度上解決了硬件難以實現(xiàn)的問題，尤其對于深空通信中信噪比較低的情況下改進(jìn)的算法具有一定的應(yīng)用價值.

[1] 竇金芳，王楠，周宇昌，等.LDPC碼在深空通信中的應(yīng)用[J].遙測遙控，2009，30(1):30-34. DOU J F，WANG N，ZHOU Y C,et al.Application of LDPC codes in the deep space communication[J].Journal of Telemetry，Tracking and Command，2009,30(1):30-34.DOI:10.13435/j.cnki.ttc.002191.

[2] GALLAGER R G. Low-density parity-check code[J].IRE Transactions on Information Theory,1962,8(1):21-28.DOI:10.1109/TIT.1962.1057683.

[3] 劉明山，王亞忠，劉珊珊.LDPC碼改進(jìn)型LBP譯碼算法研究[J].吉林大學(xué)學(xué)報(信息科學(xué)版),2015,33(4):367-372.DOI:10.3969/j.issn.1671-5896.2015.04.004. LIU M S，WANG Y Z，LIU S S.Research on modified LBP decoding algorithm of LDPC codes[J].Journal of Jilin University(Information Science Edition),2015,33(4):367-372.DOI:10.3969/j.issn.1671-5896.2015.04.004.

[4] CHEN J，F(xiàn)OSSORIER M.Density evolution for two improved BP-based decoding algorithms of LDPC codes[J].IEEE on Communication Letters,2002,6(5):208-210.DOI:10.1109/4234.1001666.

[5] WANG L A，LIU X.Improved BP decoding Algorithm for LDPC codes[J].Advanced Materials Research，2013,846-847: 925-928.DOI:10.4028/www.scientific.net/AMR.846-847.925.

[6] 郭永富，周傲松.一種改進(jìn)的LDPC碼BP譯碼算法[J].宇航學(xué)報,2009,30(1):240-243.DOI:10.3873 j.issn.1000-1328.2009.00.042. GUO Y F,ZHOU A S.An improved BP decoding algorithm of LDPC codes[J].Journal of Astronautics,2009,30(1): 240-243.DOI:10.3873 j.issn.1000-1328.2009.00.042.

[7] 李秀花，高永安，馬雯.LDPC碼譯碼算法及性能分析[J].現(xiàn)代電子技術(shù)，2014，37(1):1-4.DOI:10.3969/j.issn.1004-373X.2014.01.001. LI X H，GAO Y A，MA W.Decoding algorithm and performance analysis of LDPC codes[J].Modern Electronics Technique,2014,37(1):1-4.DOI:10.3969/j.issn.1004-373X.2014.01.001.

[8] ZHANG Q H,ZHANG J W,BAO J R.FPGA-Based improved decoding algorithm of LDPC codes[J].Applied Mechanics and Materials,2014,519-520:993-997.DOI:10.4028/www.scientific.net/AMM.519-520.995.

[9] SUN Z Y，LI H H.Improvement of LDPC codes decoding algorithm in the application of the rotational OFDM system[J].Advanced Materials Research,2014,934:235-238.DOI:10.4028/www.scientific.net/AMR.934.235.

[10] ZHAO J,ZARKESHVARI F，BANIHASHCMI A H.On implementation of min-sum algorithm and its modifications for decoding Low-density parity-check(LDPC)codes[J].IEEE Transactions on Communications,2005,53(4):549-554.DOI:10.1109/TCOMM.2004.836563.

[11] 孫斌，王鋼，楊文超，等.一種改進(jìn)型LLR BP算法的LDPC譯碼研究[J].無線電工程，2015，45(3):4-6,18.DOI:10.3969/j.issn.1003-3106.2015.0302. SUN B，WANG G，YANG W C,et al.A new modified LLR BP algorithm research for LDPC decoders[J].Radio Engineering,2015,45(3):4-6,18.DOI:10.3969/j.issn.1003-3106.2015.0302.

[12] 張霖，趙旦峰，薛睿，等.基于BP算法的QC-LDPC譯碼器的DSP實現(xiàn)[J].應(yīng)用科技，2011，38(3):34-37.DOI:10.3969/j.issn.1009-671X.2011.03.008. ZHANG L，ZHAO D F，XUE R,et al.The DSP implementation of QC-LDPC decoder based on BP algorithm[J].Applied Science and Technology,2011,38(3):34-37.DOI:10.3969/j.issn.1009-671X.2011.03.008.

(責(zé)任編輯：王蘭英)

An improved BP decoding algorithm of LDPC codes

ZHENG Wei,MA Xiaoyue,ZHAO Chengchen

(Key Laboratory of Digital Medical Engineering in Hebei Province Electronic Information Engineering College,Hebei University,Baoding 071002,China)

In BP decoding algorithm of LDPC codes decoding algorithm complexity is usually very high，more iterations is not conducive to the realization of hardware.We proposed an improved BP decoding algorithm.The improved decoding algorithm for real-time monitoring through three consecutive iterations is stable to reduce the number of iterations in the decoding when the SNR is below the threshold value，at the same time the variable message updates to check information transmission constraints.Simulation results demonstrate that the improved BP algorithm，in the case of almost no performance loss,can effectively reduce the complexity of decoding，thus more conducive to the realization of the hardware.

LDPC codes;BP decoding algorithm;iterations;data constraints

10.3969/j.issn.1000-1565.2016.05.016

2015-12-05

河北大學(xué)醫(yī)工交叉研究中心開放基金項目(BM201103)

鄭偉(1972—)，女，黑龍江蘭西人，河北大學(xué)教授，博士，主要從事圖像處理、圖像安全通信的研究． E-mail:147685650@qq.com

TN911

A

1000-1565(2016)05-0547-07