LDPC碼編譯碼原理概述

楊柳 佟首峰

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

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

一、LDPC碼概述

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

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

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

LDPC碼的這種構(gòu)造方法，是通過(guò)檢查其校驗(yàn)矩陣H的任意兩列，同一位置是否都為1，通過(guò)這種方法可以避免最短四環(huán)的出現(xiàn)。對(duì)于碼長(zhǎng)比較大的LDPC碼，其校驗(yàn)矩陣會(huì)非常稀疏，出現(xiàn)最短4環(huán)的可能性會(huì)非常小。在LDPC碼的碼長(zhǎng)較短的情況下，也可以構(gòu)造出無(wú)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ù)單位置換矩陣來(lái)構(gòu)造校驗(yàn)矩陣的。它是由子矩陣構(gòu)成校驗(yàn)矩陣，但是π—旋轉(zhuǎn)矩陣構(gòu)造法中的子矩陣為單位置換矩陣，其列重和行重都為1。校驗(yàn)矩陣是由多個(gè)子矩陣在橫向和縱向排列得到的，所以具有更大的靈活性。子矩陣的大小的設(shè)計(jì)是要根據(jù)校驗(yàn)矩陣的列重、行重和碼率、碼長(zhǎng)而決定的，并且子矩陣的大小對(duì)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)造如下：

準(zhǔn)循環(huán)LDPC碼的存儲(chǔ)量是原來(lái)的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分解法就是，首先對(duì)校驗(yàn)矩陣H的子矩陣H2進(jìn)行LU分解，可以得到上三角矩陣U和下三角矩陣L，然后再用前向迭代法就可以根據(jù)信息位來(lái)得到校驗(yàn)位，從而完成編碼，LU分解編碼算法運(yùn)算的復(fù)雜度與碼長(zhǎng)n是成線性關(guān)系的。

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

四、LDPC碼的譯碼

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

五、總結(jié)

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