低密度奇偶校驗(yàn)碼譯碼算法及其性能仿真研究

陳靜

（六六ΟΟ八部隊(duì) 天津 300250）

低密度奇偶校驗(yàn)碼 （Low-Density Parity-Check codes，LDPC碼）是目前通信糾錯(cuò)碼領(lǐng)域的熱門研究之一，是第四代移動(dòng)通信系統(tǒng)強(qiáng)有力的競(jìng)爭(zhēng)者[1-3]。它的編碼增益接近香農(nóng)極限，硬件復(fù)雜度又低于turbo碼，因此無(wú)論在理論上還是在未來(lái)通信系統(tǒng)中，低密度奇偶校驗(yàn)碼都有著廣泛的應(yīng)用前景。

LDPC碼譯碼算法中性能最好的是連續(xù)性的 BP（Belief Propagation）算法[4-5]，BP算法本質(zhì)上是并行算法，有利用硬件的并行實(shí)現(xiàn)，減少譯碼時(shí)延。文章對(duì)譯碼方法中的典型算法（BF算法和BP算法）和一種改進(jìn)的對(duì)數(shù)域算法（APP-LLR算法）進(jìn)行了仿真研究，比較并分析了信噪比、碼長(zhǎng)和迭代次數(shù)等參數(shù)對(duì)譯碼性能影響。

1 LDPC碼的譯碼與仿真

LDPC的譯碼算法大體上可以分為兩大類：基于樹形圖的硬判決譯碼算法和軟輸入/軟輸出的軟判決譯碼算法[6]。硬判決算法簡(jiǎn)單可行但性能不夠好，適合校驗(yàn)集比較小的情況；軟判決主要是基于消息傳遞（Message Passing）的置信傳播算法[7]。

1.1 LDPC碼的硬判決譯碼

1.1.1 比特翻轉(zhuǎn)（Bit_Flip ，BF）算法譯碼復(fù)雜度

當(dāng)傳輸中發(fā)生可檢測(cè)錯(cuò)誤時(shí)，反應(yīng)在特征子s=（s1，s2，…，sM）上將有失敗的校驗(yàn)，也就是某些特征子比特等于“1”。比特翻轉(zhuǎn)算法就是基于改變接收信息中的比特來(lái)減少失敗校驗(yàn)的數(shù)目，從而得到正確的譯碼信息。

首先，譯碼器檢驗(yàn)所有的校驗(yàn)位，如果某信息位上不符合校驗(yàn)約束的數(shù)目超過(guò)一個(gè)設(shè)定的固定值δ時(shí)，就改變這個(gè)信息位的值。在重新得到這些新的信息位值之后，重新計(jì)算所有的校驗(yàn)位并改變新的需要改變的比特值。依次重復(fù)直到滿足所有的校驗(yàn)約束條件。顯然，這是一種迭代算法。參數(shù)δ，被稱為BF算法的門限。應(yīng)該優(yōu)化門限使得錯(cuò)誤性能得到改善并減少計(jì)算全部校驗(yàn)特征子的數(shù)目。門限依賴于碼的度分布和信噪比。設(shè)碼字向量x經(jīng)過(guò)BSC信道接收的硬判決值為，s為伴隨式向量，比特反轉(zhuǎn)（BF）譯碼算法可簡(jiǎn)單描述為：

首先計(jì)算方程s=zHT，統(tǒng)計(jì)每位接收值yi不滿足校驗(yàn)方程的個(gè)數(shù)。

找出不滿足校驗(yàn)方程最多的zi，如不滿足的個(gè)數(shù)大于δ，將其翻轉(zhuǎn)，得到新的向量z′。

判斷條件：由向量z′代替計(jì)算方程s=zHT，如s=0則正確譯碼輸出。否則重復(fù)1-3步，反復(fù)迭代，直到迭代至最大迭代次數(shù)。

由于校驗(yàn)矩陣為稀疏矩陣，而且一般為隨機(jī)構(gòu)成，所以參與每個(gè)校驗(yàn)方程的比特很少，且這些比特在碼字上分布很分散，那么任一校驗(yàn)方程所含的比特要么無(wú)錯(cuò)，要么以很高概率出現(xiàn)只有一個(gè)比特錯(cuò)誤，BF算法就可以有效地進(jìn)行糾錯(cuò)。即使某一校驗(yàn)方程發(fā)生多于一個(gè)錯(cuò)誤，糾錯(cuò)仍可以進(jìn)行。如圖1所示為某一比特位d的校驗(yàn)集合的樹型結(jié)構(gòu)。最底層的根節(jié)點(diǎn)表示比特d，從d出發(fā)的每一條邊表示d參與的校驗(yàn)方程。每一層橫線的節(jié)點(diǎn)表示參與該校驗(yàn)方程的其他比特，依次類推到第二層、第三層。假設(shè)節(jié)點(diǎn)d和e出錯(cuò)，那么在第一次譯碼中，第二層正確節(jié)點(diǎn)會(huì)糾正錯(cuò)誤節(jié)點(diǎn)。進(jìn)而在下一步譯碼過(guò)程中節(jié)點(diǎn)d也會(huì)被糾正。由此得出：由于樹形結(jié)構(gòu)，不與節(jié)點(diǎn)d直接相連的比特對(duì)節(jié)點(diǎn)d的糾正也有幫助。

圖1 校驗(yàn)集合樹Fig.1 Check-collection tree

圖2為在不同信噪比下采用比特翻轉(zhuǎn)（BF）算法譯碼的誤碼率性能仿真結(jié)果。此處采用的是碼型為（512，3，6）碼。BF算法容易實(shí)現(xiàn)，對(duì)硬件復(fù)雜度要求不高，但是譯碼性能較差，當(dāng)翻轉(zhuǎn)次數(shù)增多時(shí)，易產(chǎn)生誤翻轉(zhuǎn)的現(xiàn)象。從圖2可以看出，BF算法整體性能較差，當(dāng)信噪比從0~3 dBm時(shí)，誤碼率變化范圍比較小，而且比較大。但誤碼率整體隨信噪比增大而減小，實(shí)際情況也應(yīng)該如此。

圖2 BF算法譯碼信噪比性能仿真Fig.2 BF algorithm decoding SNR performance simulation

1.1.2 LDPC碼的軟判決譯碼算法

LDPC碼軟譯碼算法譯碼復(fù)雜度較高，但可以獲得更好的譯碼性能，并且可以通過(guò)基于置信傳播（Belief Propagation，BP）算法的迭代譯碼來(lái)實(shí)現(xiàn)。由于BP算法中涉及到許多非線性的運(yùn)算，為減小運(yùn)算復(fù)雜度，一些簡(jiǎn)化的軟譯碼算法被陸續(xù)的提出，其中包括迭代后驗(yàn)概率 （after iteration posterior probability，APP）譯碼算法、基于BP的最小和或最大積譯碼算法（UMP BP）、歸一化的BP譯碼算法以及改進(jìn)的BP譯碼算法（Improved BP）等[8]。

假定一個(gè)校驗(yàn)矩陣H來(lái)決定一個(gè)LDPC碼字。集合M（n）表示與比特節(jié)點(diǎn)n相連的校驗(yàn)節(jié)點(diǎn)的集合。M（n）m表示集合M（n）中不包含校驗(yàn)節(jié)點(diǎn)m的集合；N（m）表示與校驗(yàn)節(jié)點(diǎn)m相連的比特節(jié)點(diǎn)的集合。N（m） 表示N（m）集合不包含比特節(jié)點(diǎn)n的集合。

1.1.3 對(duì)數(shù)域BP譯碼算法

概率域譯碼需要大量的乘法，復(fù)雜度較高，如果概率消息用似然比表示，則得到基于對(duì)數(shù)域的置信傳播算法（Loglikehood-ratio-based-progration，LLR BP算法），即將譯碼轉(zhuǎn)化到對(duì)數(shù)域中進(jìn)行，大量的乘法運(yùn)算可以變化為加法運(yùn)算，從而減少運(yùn)算時(shí)間。

則LLR-BP算法譯碼過(guò)程如下：

初始化：計(jì)算信道傳遞給變量節(jié)點(diǎn)的初始概率似然比消息 L（Pi），i=1，2，3，…N。 然后對(duì)每一個(gè)變量節(jié)點(diǎn) i∈C（i）和其相鄰的校驗(yàn)節(jié)點(diǎn)，設(shè)定變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的初始消息：

迭代處理

步驟1：校驗(yàn)節(jié)點(diǎn)消息處理。

對(duì)所有的校驗(yàn)節(jié)點(diǎn)j和其相鄰的變量節(jié)點(diǎn)i∈R（j），第 l次迭代時(shí)，計(jì)算變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的消息

或：

步驟2：變量節(jié)點(diǎn)消息處理

對(duì)所有的變量節(jié)點(diǎn)i和其相鄰的校驗(yàn)節(jié)點(diǎn) i∈R（j），第 l次迭代時(shí)，計(jì)算校驗(yàn)節(jié)點(diǎn)傳向變量節(jié)點(diǎn)的消息

步驟3：譯碼判決。

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

停止迭代

若Hc^i=0或者達(dá)到最大迭代次數(shù)，則運(yùn)算結(jié)束，否則從步驟1繼續(xù)迭代。圖3為在不同信噪比下采用對(duì)數(shù)域BP算法譯碼的誤碼率性能仿真結(jié)果。此處采用的碼型為（512，3，6）LDPC碼。

由于BP算法是基于軟判決和消息傳遞設(shè)計(jì)的，它們的性能相對(duì)上圖的BF算法而言，性能有了非常明顯的提高。從圖2可以看出的確如此，信噪比在0~3 dB變化中，BF算法誤碼率下降程度低，且比較大。BP算法在信噪比為3 dB時(shí)，誤碼率基本達(dá)到了10-4數(shù)量級(jí)，這樣的譯碼效果是以前許多糾錯(cuò)碼型無(wú)法達(dá)到的，完全體現(xiàn)了LDPC碼的優(yōu)越性能。

圖3 對(duì)數(shù)域BP算法譯碼信噪比性能仿真Fig.3 BP algorithm in log-domain decoding SNR performance simulation

1.1.4 迭代APP算法

在對(duì)數(shù)域BP算法變量節(jié)點(diǎn)的處理中，雖然只有加法運(yùn)算，但可以進(jìn)一步降低算法的實(shí)現(xiàn)復(fù)雜度。

在LLR-BP算法，迭代處理過(guò)程中，將步驟1：校驗(yàn)節(jié)點(diǎn)消息處理中的 L（qij）用 L（qi）代替，即 L（qi）不僅用于硬判決，而且用于求解校驗(yàn)消息，其他步驟同LLR-BP算法。此時(shí)BP算法簡(jiǎn)化為迭代的APP（A Posteriori Probability）算法。這樣計(jì)算，傳遞的變量消息之間引進(jìn)了相關(guān)性，傳遞的變量消息就不再是外部消息，但是此時(shí)僅僅需要計(jì)算和存儲(chǔ)一個(gè)變量消息的數(shù)值，可以大大降低算法的復(fù)雜度。

圖4為在不同信噪比下采用迭代APPBP算法譯碼的誤碼率性能仿真結(jié)果。此處采用的碼型為（512，3，6）LDPC碼。

圖4 APPBP算法譯碼信噪比性能仿真Fig.4 APP BP algorithm decoding SNR performance simulation

從圖4可看出當(dāng)信噪比大于2.5 dB時(shí)，此種算法的優(yōu)越性逐漸體現(xiàn)出來(lái)，當(dāng)信噪比為3 dB時(shí)，用此種算法譯碼得出的結(jié)果誤碼率在10-4數(shù)量級(jí)以下，而對(duì)數(shù)域BP算法譯碼的結(jié)果誤碼率要大于10-4數(shù)量級(jí)。

圖5是以上3種算法譯碼仿真結(jié)果對(duì)比示意圖，由于BF算法誤碼率隨信噪比的增加下降幅度小，故在圖中趨于一條直線，而迭代APP算法在信噪比較大時(shí)對(duì)比對(duì)數(shù)域BP算法才有了一定優(yōu)勢(shì)。

圖5 對(duì)數(shù)域BP、APP算法譯碼仿真結(jié)果對(duì)比Fig.5 Contrast between BF algorithm in log-domain and APP algorithm decoding simulation results

2 參數(shù)對(duì)LDPC碼譯碼算法性能影響的仿真分析

以迭代APP算法為例，考慮了影響算法性能的兩個(gè)參數(shù)：碼長(zhǎng)和迭代次數(shù)對(duì)譯碼性能的影響。如圖6所示，是編碼碼長(zhǎng)分別為 L=126，L=256，L=512，L=1024時(shí) LDPC 碼譯碼的性能對(duì)比。

圖6 不同編碼長(zhǎng)度的LDPC碼的性能對(duì)比Fig.6 The performance of the different length coding of LDPC codes

由圖6中不同碼長(zhǎng)的仿真結(jié)果可以看出，碼長(zhǎng)是影響LDPC碼性能的一個(gè)重要因素，隨著碼長(zhǎng)的增長(zhǎng)，LDPC碼的誤碼性能越來(lái)越好。在信噪比為3 dB時(shí)，碼長(zhǎng)為1024的碼比長(zhǎng)為126的碼在誤碼率上低了差不多一個(gè)數(shù)量級(jí)。同時(shí)也可以看到，當(dāng)信噪比比較小的時(shí)候，增加碼長(zhǎng)對(duì)誤碼性能改善不大。碼長(zhǎng)的增加在一定程度上提高了誤碼性能，但也不能無(wú)限增大，因?yàn)樽g碼復(fù)雜度是和碼長(zhǎng)有關(guān)的，隨著碼長(zhǎng)增加，譯碼復(fù)雜度勢(shì)必會(huì)增大。而且由于LDPC碼是分組碼，只有整個(gè)序列都譯完才能得到譯碼輸出，故增大編碼碼長(zhǎng)會(huì)使譯碼時(shí)間延長(zhǎng)。

在譯碼環(huán)節(jié)中一個(gè)重要的參數(shù)就是迭代次數(shù)。對(duì)于不同的LDPC碼，除了要考慮其誤碼率性能，另外也要考慮其譯碼的復(fù)雜度。由于LDPC碼的譯碼算法都是并行的迭代譯碼算法，所以譯碼的迭代次數(shù)是衡量譯碼復(fù)雜度、影響譯碼性能的一個(gè)重要參數(shù)，最好能取得譯碼性能和復(fù)雜度之間的均衡。

圖7為不同迭代數(shù)的LDPC碼迭代APP譯碼算法的性能。 選用的碼型為（256，3，6），迭代次數(shù)分別為 1、2、5、10 和20次。從圖7可以看出，隨著迭代次數(shù)增加，誤碼性能會(huì)逐漸提高，迭代次數(shù)為1的性能最差，為20的性能最好。在信噪比為3 dB時(shí)，只有20次迭代譯碼的誤碼率達(dá)到了10-3數(shù)量級(jí)，而其他迭代次數(shù)都大于這個(gè)數(shù)量級(jí)。

圖7 不同譯碼迭代次數(shù)的誤碼性能Fig.7 The ber performance of different decoding iterations

從圖7中觀察到，開始隨著迭代次數(shù)的增加 （1次到5次），LDPC碼的性能顯著改善，這是因?yàn)榻?jīng)過(guò)迭代，比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)更充分地利用了外部信息，從而做出了更準(zhǔn)確的判斷，但是隨著迭代次數(shù)不斷增多（10次到20次），譯碼性能提高的趨勢(shì)越來(lái)越緩慢。這是因?yàn)榻?jīng)過(guò)多次迭代后，外部信息具有很強(qiáng)的相關(guān)性，不能提供更新的糾錯(cuò)信息。但LDPC譯碼時(shí)，并不是每次都要達(dá)到譯碼迭代次數(shù)的上限，在滿足校驗(yàn)等式就可以終止迭代，盡管如此在譯碼時(shí)，仍應(yīng)權(quán)衡迭代次數(shù)和復(fù)雜度，以便能夠在可接受的復(fù)雜度下取得較好的譯碼性能。

3 結(jié)束語(yǔ)

文中針對(duì)LDPC碼譯碼算法進(jìn)行仿真，比較了不同算法、不同碼長(zhǎng)和不同迭代次數(shù)情況下譯碼效果。結(jié)果表明，硬判決譯碼算法的誤碼性能對(duì)比軟判決算法效果相差很大，但由于其譯碼復(fù)雜度和對(duì)硬件要求低，所以它仍會(huì)被使用。仿真還表明，誤碼率會(huì)隨著碼長(zhǎng)和迭代次數(shù)的增加而減小，但它們都會(huì)增加譯碼的復(fù)雜度，故在譯碼時(shí)應(yīng)權(quán)衡誤碼率和復(fù)雜度的關(guān)系。

[1]張用宇，吳東偉，左麗芬，等.低密度奇偶校驗(yàn)碼構(gòu)造及編譯碼研究進(jìn)展[J].電訊技術(shù).2012，52（8）:1395-1343.ZHANG Yong-yu，WU Dong-wei，ZUO Li-fen，et al.Survey on construction，encoding and eecoding of low-density parity-check codes[J].Telecommunication Engineering，2012，52（8）:1395-1343.

[2]陳為剛，殷柳國(guó)，陸建華.低密度奇偶校驗(yàn)碼迭代譯碼算法的誤碼平臺(tái)特性[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，49（1）:61-64.CHEN Weig-ang，YIN Liu-guo，LU Jian-hua.Error floor properties of low-density parity-check codes using iterative decoding algorithms[J].J Tsinghua Univ （Sci&Tech ），2009，49（1）:61-64.

[3]Fossorier M.Iterative reliablity-based decoding of low density parity check codes[J].IEEE J.Selcet.Areas Commun，2001（19）:908-917.

[4]董磊.低密度奇偶校驗(yàn)碼編譯碼原理及實(shí)現(xiàn) [D].西安：西安電子科技大學(xué)，2007.

[5]Jilei Hou，Paul H.Siegel，Laurence B.Performance Analysis and Code Optimization of Low Density Parity-Check Codes Codes on Rayleigh Fading Channels[J].IEEE Journal Select Areas in Communications.2001，19（5）:924-934.

[6]李晉.低密度奇偶校驗(yàn)碼及其并行級(jí)聯(lián)構(gòu)造的研究[D].南京:東南大學(xué)，2006.

[7]徐進(jìn)廷.LDPC碼譯碼算法研究與仿真[D].蘭州:蘭州大學(xué)，2009.

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