王繼強(qiáng) 劉翠海 薛蕾蕾 徐濤

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

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

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

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

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

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

1 低密度校驗(yàn)編碼

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

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

2 LDPC碼譯碼算法

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

3 譯碼算法性能分析及計(jì)算機(jī)仿真

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

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

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

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

3.2三種譯碼算法性能比較

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

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

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

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

4 結(jié)語

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

參考文獻(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)航與指揮自動(dòng)化，2009（4）：12-20.

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