基于BP算法的LDPC碼性能仿真

淮南師范學院 王千春

前言

1965年Gallager在他提出了Gallager碼，當時人們對他的發現沒有任何重視，認為他是天方夜譚，以至于這么偉大的發現在當時被忽視了，由于科學技術的進步和相關理論的發展，后人發現他在和其他譯碼相結合的情況下可以接近于香農極限，因為LDPC碼有著劃時代的意義。LDPC碼的特點是，比之前的譯碼方法更加靈活，接近于香農極限，在即將到來的5G時代，LDPC碼必將通過它獨特的優勢，為人類進入新的信息時代做出貢獻[1]。

1.LDPC碼的原理

LDPC代碼是一個非常特殊的線性分組碼。通過生成矩陣G，必須將線性分組碼的信息s轉換為轉移碼t，并且對應于G的校驗矩陣H滿足H×t = 0。LDPC碼驗證矩陣的0個元素分量的個數大于非零元素的個數，屬于稀疏矩陣范疇[2]。

LDPC碼包括常規和非常規兩種編碼形式。假設LDPC碼的驗證矩陣B是J×K的滿秩矩陣，則LDPC碼長度為J，驗證位K，則信息位是H= j-k，碼率r= h/ k。用Tanner圖表示如圖1所示。所謂的信息點（比特點）即是下邊N個節點所代表的N個碼字。因此，非規則碼包括規則碼，是它的一個特例。

圖1 校驗矩陣對應的Tanner圖

2.LDPC碼校驗矩陣構造

在介紹LDPC碼校驗矩陣的構造之前，首先闡述一下girth的概念。圖2中，粗線部分構成了長度為6的環，其中最短環的環長稱為該圖的girth。girth是構造校驗矩陣的非常重要的指標[3]。二部圖中girth的值越大，校驗矩陣的性能就越好，一般要求girth最小為6。

圖2 校驗矩陣的隨機構造

本文采用Gallager構造法，Gallager基于GF（2）域上定義的（n，j，k）LDPC碼，其校驗矩陣H的構造如下：

（1）將Gallager碼的監督矩陣按行劃分成j個部分（每部分包含相同的行數），每一部分的每一列中只包含一個“1”。

（2）第一部分構造的矩陣中，“1”比特在行中按降冪排列，在第一行中，第1到k個元素為“1”，其余為0；在第2行中，從第k+1到2k個元素為“1”，其余為0；如此安排，第i行中，從第k+1到第i個元素為“1”，其余為0。

（3）其余j-1部分的構造是對第一部分進行列的隨機重排。

該構造法可以保證每列有j個“1”，每行有k個“1”。圖3給出了由Gallager構造法構造的（20，3，4）的LDPC碼校驗矩陣，碼長為20，j=3，k=4。

圖3 Gallager構造的（30，5，6）的LDPC碼校驗矩陣

3.LDPC碼的編碼

本文采用隨機構造的LDPC碼的LU分解法[4]。對于LU分解法的想法，在I是非特異性隊伍的情況下，I可以分解為上三角隊U和下三角隊L的積，L和U也是MxN維的稀疏排列。

基本步驟如下：

（1）對H矩陣進行LU分解，得到重排后的H、B、L、U。

（2）計算Z=BS。

（3）解方程得到Y，其中Y是M維列向量。

（4）通過反向消除法求解UC = Y，得到C。

LU分解的一個基本算法如下所示：

（1）設U和L為全零矩陣。

（2）設F=H。

（3）for i=1 to m

在F矩陣中找到同一列的非零元素。

對矩陣F和H的行列進行重新組合，注意此元素必須位于他之前的位置，不可變化。

（4）把B矩陣設置為重排后的H矩陣最后N-M列。

4.LDPC碼的譯碼

LDPC碼的迭代譯碼方法是LDPC碼能夠得以迅速發展的主要原因，該譯碼方法使得LDPC碼不僅描述簡單，譯碼復雜度低，而且可以并行操作，便于硬件實現，具有接近Shannon極限的優異性能。

譯碼采用UMP BP-Based算法（最小和或最大積），LLR BP算法中節點[5]可變化為：

由于：

所以：

UMP（Uniformly Most Powerful）BP-Based算法又稱為最小和（Min Sum）算法或最大積（Max Product）算法，該算法是用式來處理LLR BP算法中校驗節點的消息，此時校驗節點的迭代只有比較算法和加法運算，計算的復雜度就大大降低了。對于加性高斯白噪聲信道，該算法不需要信道估計。

5.LDPC碼的仿真

在其他條件一定時，將碼長設置為300、500以及1000，列重和迭代次數分別設置為2和20，進行仿真，得到的結果如圖4所示。

圖4 碼長不同時的仿真結果

從圖4的仿真圖像可以清楚地看出：在相同的SNR件下，LDPC碼的性能與代碼成正比，但與具有任何數值的情況相比，誤碼率不會根據代碼長度的變化而改變，但是如果信噪比是與高于特定數值的情況相比，誤碼率開始顯明顯著上升。這是因為代碼具有上限，隨著碼長的增加，編碼的繁瑣程度也不斷提高，此時性能的增加便不會很明顯。

簡言之，在相同的信噪比下，LDPC碼的性能與碼長成正比，但是一旦信噪比低于某個值，誤碼率不會隨著代碼長度而改變。但當信噪比高于某個值時，誤碼率開始迅速增加。這是因為任何代碼長度都有其自己理論上的編碼上限。

當列重和代碼長度選擇一定值時，Matlab軟件選擇三次不同的迭代次數進行多次迭代。20，40，列重選擇2，代碼長度選擇500，仿真結果如圖7所示。

圖5 迭代次數不同時的影響

從圖5所示的仿真結果可以看出：在相同的信噪比下，LDPC碼的性能與迭代次數成正比。然而，雖然誤碼率和迭代次數之間的關系成正比，但是實驗發現，當迭代次數已經改變到上限時，繼續增加，誤碼率不改變，在這種情況下，系統延時變長，并且即使LDPC碼的性能不受影響，系統的準確度也會降低。