LDPC 碼編譯碼原理概述

【摘要】 LDPC 碼是糾錯(cuò)碼，在信道編碼中，與RS 碼和Turbo 碼相比，其糾錯(cuò)能力是最好的，因此，對LDPC 碼的研究有很大的價(jià)值和意義。目前，已經(jīng)廣泛應(yīng)用于深空通信、光纖通信和衛(wèi)星數(shù)字視頻等領(lǐng)域。

【關(guān)鍵詞】 LDPC 編碼 譯碼 BP 算法

一、LDPC 碼概述

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

二、LDPC 碼的基本構(gòu)造方法

2.1 MacKay 和Neal 構(gòu)造的規(guī)則隨機(jī)LDPC 碼

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

MacKay 和Neal 所提出的構(gòu)造方法，應(yīng)用到實(shí)際當(dāng)中是很難的，是由于它的校驗(yàn)矩陣和生成矩陣不具有準(zhǔn)循環(huán)特性。

2.2 π—旋轉(zhuǎn)矩陣構(gòu)造法

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

2.3 準(zhǔn)循環(huán)構(gòu)造法

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

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

準(zhǔn)循環(huán)LDPC 碼的存儲(chǔ)量是原來的1/ Z，需要的存儲(chǔ)量大幅度減少，是由于只需要存儲(chǔ)循環(huán)置換單位子矩陣中第一行元素“1”的位置和準(zhǔn)循環(huán)置換單位子矩陣在校驗(yàn)矩陣中的位置。準(zhǔn)循環(huán)LDPC 碼是具有比較好的應(yīng)用前景的，準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC 碼是一種重要的LDPC 碼，已經(jīng)被IEEE 802.16e 標(biāo)準(zhǔn)和GB20600 標(biāo)準(zhǔn)所采納。

三、LDPC 碼的編碼算法

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

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

四、LDPC 碼的譯碼

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

五、總結(jié)

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