LDPC 碼編譯碼原理概述

【摘要】 LDPC 碼是糾錯碼，在信道編碼中，與RS 碼和Turbo 碼相比，其糾錯能力是最好的，因此，對LDPC 碼的研究有很大的價值和意義。目前，已經廣泛應用于深空通信、光纖通信和衛星數字視頻等領域。

【關鍵詞】 LDPC 編碼 譯碼 BP 算法

一、LDPC 碼概述

LDPC 碼是一種低密度奇偶校驗碼。LDPC 碼的譯碼比較簡單，具有逼近香農極限的特點。LDPC 碼是一種線性分組碼的一種，其校驗矩陣中非零元素的個數是很少的。由于校驗矩陣H 的這種稀疏性，從而保證了譯碼復雜度和最小碼距都只隨碼長的增大而呈線性增加的趨勢。

二、LDPC 碼的基本構造方法

2.1 MacKay 和Neal 構造的規則隨機LDPC 碼

LDPC 碼的這種構造方法，是通過檢查其校驗矩陣H 的任意兩列，同一位置是否都為1，通過這種方法可以避免最短四環的出現。對于碼長比較大的LDPC 碼，其校驗矩陣會非常稀疏，出現最短4 環的可能性會非常小。在LDPC 碼的碼長較短的情況下，也可以構造出無4 環的校驗矩陣。

MacKay 和Neal 所提出的構造方法，應用到實際當中是很難的，是由于它的校驗矩陣和生成矩陣不具有準循環特性。

2.2 π—旋轉矩陣構造法

旋轉矩陣構造法就是根據單位置換矩陣來構造校驗矩陣的。它是由子矩陣構成校驗矩陣，但是π—旋轉矩陣構造法中的子矩陣為單位置換矩陣，其列重和行重都為1。校驗矩陣是由多個子矩陣在橫向和縱向排列得到的，所以具有更大的靈活性。子矩陣的大小的設計是要根據校驗矩陣的列重、行重和碼率、碼長而決定的，并且子矩陣的大小對LDPC 碼性能有很大的影響。

2.3 準循環構造法

校驗矩陣是由零矩陣和循環置換單位子矩陣構成的。有如下定義，循環置換子矩陣Zi 是z×z 階單位陣循環移動i 次得到的，其中，Z 是尺寸為z×z 的零矩陣。則校驗矩陣H 為mz×nz 階，可構造如下：

其中α11 的取值范圍是｛0,1，…，z-1，∞｝。

準循環LDPC 碼的存儲量是原來的1/ Z，需要的存儲量大幅度減少，是由于只需要存儲循環置換單位子矩陣中第一行元素“1”的位置和準循環置換單位子矩陣在校驗矩陣中的位置。準循環LDPC 碼是具有比較好的應用前景的，準循環結構的LDPC 碼是一種重要的LDPC 碼，已經被IEEE 802.16e 標準和GB20600 標準所采納。

三、LDPC 碼的編碼算法

1、LU 分解編碼算法。LU 分解法就是，首先對校驗矩陣H 的子矩陣H2 進行LU 分解，可以得到上三角矩陣U 和下三角矩陣L，然后再用前向迭代法就可以根據信息位來得到校驗位，從而完成編碼，LU 分解編碼算法運算的復雜度與碼長n 是成線性關系的。

2、部分迭代譯碼算法。LU 分解法的缺點是預處理的復雜度比較高，最重要的是經過預處理之后，新得到的校驗矩陣有很大可能不是稀疏矩陣，所以會導致編碼的運算量非常大。所以，我們想找到其他的編碼算法，要求這種編碼算法的運算得復雜度和碼長成線性關系。部分迭代譯碼算法就具有這樣的特點，這種方法對校驗矩陣H 只做列置換和行置換， 這樣，矩陣的右上角會出現下三角形式，然后對矩陣進行分塊處理，把上述的下三角矩陣獨立出來，使其成為一個子矩陣，最后根據這個子矩陣的結構來進行迭代編碼。

四、LDPC 碼的譯碼

1、消息傳遞算法。在消息傳遞算法中，其中概率信息是根據兩部圖在校驗節點和變量節點之間的傳遞，逐步進行迭代譯碼。節點的沿邊所發送的信息與上次接收到的信息是沒有關系的，而是取決于與其相連的其他邊上所接收到的信息。就是為了使任意一條邊上，只有外來信息的傳遞，這樣可以保證其譯碼性能的良好性。2、置信傳播算法。置信傳播算法就是，當消息傳遞算法中的譯碼過程中所發送的信息的符號集和信道所輸出的符號集相同時，也就是采用連續性的消息時，適當選擇信息映射函數。這種算法主要就是，根據接收到的軟信息在變量節點和校驗節點之間進行迭代運算，來獲得最大編碼增益，因此具有良好的性能，在性能要求比較高的場合是適用的。3、最小和譯碼算法。最小和譯碼算法是根據對數域BP 譯碼算法所提出的一種簡化算法，最小和譯碼算法根據求最小值的運算從而簡化了函數運算， 不再需要估計信道噪聲，而且運算復雜度也很大程度上降低了，但是它的性能也是有所下降的。4、BP 迭代譯碼算法。基于BP 算法的迭代譯碼算法，就是在給定接收信號和信道估計的條件下，在迭代的每一步中，對于有噪序列的每一個符號，都要進行后驗概率的估計，然后把所估計到的值輸入下一次迭代，這樣可以獲得更好的結果。

五、總結

LDPC 碼是一種接近香農極限的碼，其校驗矩陣是稀疏矩陣，譯碼具有線性復雜度。BP 譯碼算法的錯誤是可以檢測的；MS 算法雖然降低了函數的復雜度, 但是性能也是下降的；BF 算法復雜度低、硬件實現簡單, 不需要復雜的計算， 操作方便。但性能較BP 算法有一定程度的降低, 適用于對譯碼性能不高的場合。