低密度奇偶校驗碼譯碼算法及其性能仿真研究

陳靜

（六六ΟΟ八部隊 天津 300250）

低密度奇偶校驗碼 （Low-Density Parity-Check codes，LDPC碼）是目前通信糾錯碼領域的熱門研究之一，是第四代移動通信系統強有力的競爭者[1-3]。它的編碼增益接近香農極限，硬件復雜度又低于turbo碼，因此無論在理論上還是在未來通信系統中，低密度奇偶校驗碼都有著廣泛的應用前景。

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

1 LDPC碼的譯碼與仿真

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

1.1 LDPC碼的硬判決譯碼

1.1.1 比特翻轉（Bit_Flip ，BF）算法譯碼復雜度

當傳輸中發生可檢測錯誤時，反應在特征子s=（s1，s2，…，sM）上將有失敗的校驗，也就是某些特征子比特等于“1”。比特翻轉算法就是基于改變接收信息中的比特來減少失敗校驗的數目，從而得到正確的譯碼信息。

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

首先計算方程s=zHT，統計每位接收值yi不滿足校驗方程的個數。

找出不滿足校驗方程最多的zi，如不滿足的個數大于δ，將其翻轉，得到新的向量z′。

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

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

圖1 校驗集合樹Fig.1 Check-collection tree

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

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

1.1.2 LDPC碼的軟判決譯碼算法

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

假定一個校驗矩陣H來決定一個LDPC碼字。集合M（n）表示與比特節點n相連的校驗節點的集合。M（n）m表示集合M（n）中不包含校驗節點m的集合；N（m）表示與校驗節點m相連的比特節點的集合。N（m） 表示N（m）集合不包含比特節點n的集合。

1.1.3 對數域BP譯碼算法

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

則LLR-BP算法譯碼過程如下：

初始化：計算信道傳遞給變量節點的初始概率似然比消息 L（Pi），i=1，2，3，…N。 然后對每一個變量節點 i∈C（i）和其相鄰的校驗節點，設定變量節點傳向校驗節點的初始消息：

迭代處理

步驟1：校驗節點消息處理。

對所有的校驗節點j和其相鄰的變量節點i∈R（j），第 l次迭代時，計算變量節點傳向校驗節點的消息

或：

步驟2：變量節點消息處理

對所有的變量節點i和其相鄰的校驗節點 i∈R（j），第 l次迭代時，計算校驗節點傳向變量節點的消息

步驟3：譯碼判決。

對所有變量節點計算硬判決消息

停止迭代

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

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

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

1.1.4 迭代APP算法

在對數域BP算法變量節點的處理中，雖然只有加法運算，但可以進一步降低算法的實現復雜度。

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

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

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

從圖4可看出當信噪比大于2.5 dB時，此種算法的優越性逐漸體現出來，當信噪比為3 dB時，用此種算法譯碼得出的結果誤碼率在10-4數量級以下，而對數域BP算法譯碼的結果誤碼率要大于10-4數量級。

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

圖5 對數域BP、APP算法譯碼仿真結果對比Fig.5 Contrast between BF algorithm in log-domain and APP algorithm decoding simulation results

2 參數對LDPC碼譯碼算法性能影響的仿真分析

以迭代APP算法為例，考慮了影響算法性能的兩個參數：碼長和迭代次數對譯碼性能的影響。如圖6所示，是編碼碼長分別為 L=126，L=256，L=512，L=1024時 LDPC 碼譯碼的性能對比。

圖6 不同編碼長度的LDPC碼的性能對比Fig.6 The performance of the different length coding of LDPC codes

由圖6中不同碼長的仿真結果可以看出，碼長是影響LDPC碼性能的一個重要因素，隨著碼長的增長，LDPC碼的誤碼性能越來越好。在信噪比為3 dB時，碼長為1024的碼比長為126的碼在誤碼率上低了差不多一個數量級。同時也可以看到，當信噪比比較小的時候，增加碼長對誤碼性能改善不大。碼長的增加在一定程度上提高了誤碼性能，但也不能無限增大，因為譯碼復雜度是和碼長有關的，隨著碼長增加，譯碼復雜度勢必會增大。而且由于LDPC碼是分組碼，只有整個序列都譯完才能得到譯碼輸出，故增大編碼碼長會使譯碼時間延長。

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

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

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

從圖7中觀察到，開始隨著迭代次數的增加 （1次到5次），LDPC碼的性能顯著改善，這是因為經過迭代，比特節點和校驗節點更充分地利用了外部信息，從而做出了更準確的判斷，但是隨著迭代次數不斷增多（10次到20次），譯碼性能提高的趨勢越來越緩慢。這是因為經過多次迭代后，外部信息具有很強的相關性，不能提供更新的糾錯信息。但LDPC譯碼時，并不是每次都要達到譯碼迭代次數的上限，在滿足校驗等式就可以終止迭代，盡管如此在譯碼時，仍應權衡迭代次數和復雜度，以便能夠在可接受的復雜度下取得較好的譯碼性能。

3 結束語

文中針對LDPC碼譯碼算法進行仿真，比較了不同算法、不同碼長和不同迭代次數情況下譯碼效果。結果表明，硬判決譯碼算法的誤碼性能對比軟判決算法效果相差很大，但由于其譯碼復雜度和對硬件要求低，所以它仍會被使用。仿真還表明，誤碼率會隨著碼長和迭代次數的增加而減小，但它們都會增加譯碼的復雜度，故在譯碼時應權衡誤碼率和復雜度的關系。

[1]張用宇，吳東偉，左麗芬，等.低密度奇偶校驗碼構造及編譯碼研究進展[J].電訊技術.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]陳為剛，殷柳國，陸建華.低密度奇偶校驗碼迭代譯碼算法的誤碼平臺特性[J].清華大學學報：自然科學版，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]董磊.低密度奇偶校驗碼編譯碼原理及實現 [D].西安：西安電子科技大學，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]李晉.低密度奇偶校驗碼及其并行級聯構造的研究[D].南京:東南大學，2006.

[7]徐進廷.LDPC碼譯碼算法研究與仿真[D].蘭州:蘭州大學，2009.

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