低密度奇偶校驗碼譯碼算法性能分析及仿真

王繼強 劉翠海 薛蕾蕾 徐濤

摘要：討論了置信傳播（BP）譯碼算法和在該算法基礎(chǔ)上衍生的兩種譯碼算法，對數(shù)似然率（LLR-BP）算法和最小和（Min-sum）算法；分析了三種譯碼算法的性能，并對分析結(jié)果進行了仿真驗證。結(jié)果表明，在譯碼性能上LLR-BP算法與BP算法相當(dāng)，前者比后者算法要簡單，Min-sum算法雖然較BP和LLR-BP算法相比，損失了一定誤碼性能，但易于硬件實現(xiàn)，實用性較強。

關(guān)鍵詞：LDPC碼 信道編碼 差錯控制 糾錯編碼 計算機仿真

中圖分類號：TN91 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）05-0000-00

低密度奇偶校驗碼（LDPC）是一種線性分組糾錯碼，當(dāng)其采用迭代譯碼算法時，如和積（sum-product） 譯碼算法，具有逼近Shannon限的良好性能，其譯碼算法復(fù)雜度隨碼長呈線性增長，非常適合并行實現(xiàn)。正因如此，LDPC碼受到了業(yè)界的廣泛關(guān)注，已廣泛應(yīng)用于移動通信、光纖通信、衛(wèi)星測控通信和數(shù)字視頻等領(lǐng)域[1] [2]。

構(gòu)造LDPC碼時，其校驗矩陣中的非零元素往往很少，正是由于校驗矩陣具有這種稀疏的特性，因此出現(xiàn)了多種高效的譯碼算法，且糾錯能力較強。LDPC譯碼采用的是消息傳遞（MP）算法，其基本算法有比特翻轉(zhuǎn)（BF）算法和置信傳播（BP）算法。BF算法只進行比特位的翻轉(zhuǎn)等幾種簡單的運算，復(fù)雜度較低，因此硬件實現(xiàn)簡單，但其性能相對較低，適用于硬件條件受限而性能要求較低的場合；而BP算法是將接收到的信息在變量節(jié)點和校驗節(jié)點之間進行迭代運算，從而獲得最大編碼增益，因此具有很好的性能，同時復(fù)雜度也較高，廣泛應(yīng)用于對性能有較高要求的場合。

本文在介紹低密度校驗編碼的基礎(chǔ)上，研究了置信傳播（BP）算法、對數(shù)似然率（LLR-BP）算法、最小和（Min-sum）算法等三種譯碼算法，并對各種算法的復(fù)雜度、工程實現(xiàn)的難易度和優(yōu)缺點進行分析，并對分析結(jié)果進行仿真驗證。

1 低密度校驗編碼

LDPC編碼的首要條件是構(gòu)造一個符合條件的稀疏校驗矩陣。根據(jù)校驗矩陣結(jié)構(gòu)不同，通常把LDPC碼分為規(guī)則LDPC碼和不規(guī)則LDPC碼。規(guī)則LDPC碼的校驗矩陣每行每列的非零元素相同，而不規(guī)則LDPC碼不受此規(guī)則限制。無論哪種，好的LDPC碼，必須圍繞無短環(huán)、無低碼重碼字、碼間最小距離盡可能大的原則構(gòu)造校驗矩陣[3]。

傳統(tǒng)的編碼方法是將稀疏奇偶校驗矩陣H經(jīng)過高斯消元處理轉(zhuǎn)換為生成矩陣G，再根據(jù)G來進行編碼。如此的編碼方法其生成矩陣的稀疏性難以保證，且會導(dǎo)致編碼的運算和存儲復(fù)雜性大大增加。對于線性編碼來說，校驗矩陣為H，編碼后碼字為c，則由校驗等式性質(zhì)H·c=0，所以可以用校驗矩陣直接編碼，主要的編碼方法有高斯消去的直接編碼，LU分解編碼，部分迭代編碼算法等。本文仿真采用高斯消去的直接編碼，將m·n校驗矩陣H通過高斯消元和列變換改成如下形式H=[I|P]，I為m·m單位矩陣，P為m·（n-m）矩陣，編碼后碼字c寫成c=[s|u]形式，u為輸入碼字，s為校驗碼字，由校驗等式H·c=0得，I·s+P·u=0，即s=P·u，則由c=[u s]可得編碼后碼字。

2 LDPC碼譯碼算法

LDPC譯碼算法是以迭代運算為主，主要是基于二分圖[6]結(jié)構(gòu)的消息傳遞算法。二分圖與校驗矩陣H相對應(yīng)，包含三種元素，方形節(jié)點、圓形節(jié)點及連接方形節(jié)點和圓形節(jié)點之間的邊，對于M×N的校驗矩陣H，方形節(jié)點Vc=（c0，c1，…，cM-1）稱為校驗節(jié)點，對應(yīng)于校驗矩陣中的列，圓形節(jié)點Vs=（s0，s1，…，sN-1）稱為變量節(jié)點，對應(yīng)于校驗矩陣中的行。如果校驗矩陣中的非零位于第i行第j列，則校驗節(jié)點ci和變量節(jié)點sj之間存在一條邊，如圖1所示，為5×10的校驗矩陣二分圖表示。LDPC譯碼時各個節(jié)點的置信消息需要在變量節(jié)點和校驗節(jié)點之間互相傳遞。

3 譯碼算法性能分析及計算機仿真

從第二節(jié)對三種譯碼算法的分析來看，LLR-BP譯碼算法雖然與BP算法接近，但是，由于其運算是在對數(shù)域進行，因此復(fù)雜度有所降低；而MIN_SUM算法則通過采用近似運算來降低復(fù)雜度，但是，近似運算導(dǎo)致了該算法性能會有所損耗。

3.1三種譯碼算法復(fù)雜度比較

文獻(xiàn)[6]對概率域BP譯碼算法、LLR_BP譯碼算法和Min-sum譯碼算法的計算復(fù)雜度進行了對比，各種算法都是針對碼率為1/2的（n，2p，p）規(guī)則LDPC碼進行分析的。如表1所示。

由表1可以看出，在計算復(fù)雜度方面，BP算法最為復(fù)雜，LLR-BP算法次之，Min-sum算法計算量是最小的。

3.2三種譯碼算法性能比較

為了對BP算法、LLR_BP算法和MIN_SUM三種譯碼算法的性能進行分析，本文建立了BPSK系統(tǒng)仿真模型，如圖2所示，并以此模型為基礎(chǔ)，分析三種譯碼算法在仿真系統(tǒng)中的性能。

基于圖2的系統(tǒng)仿真模型，對三種譯碼算法性能進行分析。信源部分隨機生成，生成的數(shù)據(jù)u={u1，u2， …，uk}經(jīng)基于刪除信道的迭代算法進行LDPC編碼，碼長為512，碼率為1/2，最大迭代次數(shù)為100，編碼后得到的碼字c={c1，c2， …，cn }進行BPSK調(diào)制，調(diào)制后將碼字c映射成傳輸碼字x={x1，x2， …，xn }。

若信噪比取值為SNR = （0：0.2：2），運行系統(tǒng)，可以繪制出采取三種不同譯碼算法解碼后系統(tǒng)的誤碼率曲線。圖3給出了在加性高斯白噪聲信道下系統(tǒng)誤碼率圖。

從圖3可以看出，BP譯碼算法和LLR_BP譯碼算法誤碼率基本一致，最小和譯碼算法誤碼率相對較差。由此可以看出，三種算法中BP算法是基礎(chǔ)算法，其譯碼復(fù)雜度最高，但具有最優(yōu)的譯碼性能。LLR-BP算法是由BP算法簡化而來，通過將原來的運算簡化到對數(shù)域進行，從而降低了譯碼復(fù)雜度。就譯碼性能來說，LLR-BP算法最接近BP算法，從圖中也可以看出，BP算法與LLR-BP算法的曲線幾乎一致。Min-sum算法復(fù)雜度最低，與其它兩種算法比較譯碼性能較差，但性能損失不大。所以Min-sum算法復(fù)雜度降低，易于硬件實現(xiàn)，實用性較強。因此在實際運用中，我們需要在性能和復(fù)雜度上進行整體考慮。

4 結(jié)語

低密度校驗編碼在高速數(shù)據(jù)傳輸中有著較好的應(yīng)用，但是其采用不同譯碼算法所表現(xiàn)出的譯碼性能有著較大差異。為此，本文討論了置信傳播（BP）譯碼算法和在該譯碼算法基礎(chǔ)上衍生的兩種譯碼算法，對數(shù)似然率（LLR-BP）算法和最小和（Min-sum）算法；分析了三種譯碼算法的性能，并對分析結(jié)果進行了仿真驗證。雖然LLR-BP算法譯碼性能與BP算法相當(dāng)，但簡化了算法，Min-sum算法雖然較BP和LLR-BP算法相比，損失了一定誤碼性能，但易于硬件實現(xiàn)，實用性較強。因此，在實際應(yīng)用中，要根據(jù)系統(tǒng)性能要求和硬件條件等因素綜合考慮，在譯碼性能和復(fù)雜度之間需要全面衡量，選擇合適的LDPC碼譯碼方法，開發(fā)相應(yīng)的硬件產(chǎn)品。本文只是對LDPC碼的基礎(chǔ)譯碼算法進行了分析，對不同碼長的選擇，以及在不同的調(diào)制方式和通信環(huán)境下系統(tǒng)性能的比較分析未曾考慮，因此還需要進一步完善。

參考文獻(xiàn)

[1]沈倩.LDPC碼編譯碼技術(shù)研究及其在LTE—A系統(tǒng)中的應(yīng)用[D].武漢理工大學(xué)碩士論文，2012.

[2]彭世章.LDPC編譯碼技術(shù)研究及其在遙測系統(tǒng)中的應(yīng)用[D].杭州電子科技大學(xué)碩士論文，2011.

[3]袁東風(fēng)，張海剛.LDPC碼理論與應(yīng)用[M].北京：人民郵電出版社，2008.

[4]肖楊.Turbo與LDPC編解碼及其應(yīng)用[M].北京：人民郵電出版社，2010.

[5]劉濤，馬沛川.LDPC編譯碼技術(shù)原理及其性能分析[J].通信導(dǎo)航與指揮自動化，2009（4）：12-20.

[6]徐智勇.LDPC碼編譯碼算法的仿真研究[D].東北大學(xué)碩士論文，2009.