一種改進(jìn)的LDPC碼硬判決譯碼算法

詹 尹，李宏偉

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077)

責(zé)任編輯:薛 京

低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼是一種可以用稀疏校驗(yàn)矩陣或者因子圖［1］來(lái)定義的線性分組碼，該碼最初由羅伯特·克拉克(Robert Gallager)［2］在其博士論文中提出，故亦稱(chēng)Gallager碼。但是由于當(dāng)時(shí)硬件條件有限，計(jì)算機(jī)的存儲(chǔ)能力以及處理數(shù)據(jù)能力較低，LDPC碼在此后相當(dāng)長(zhǎng)的時(shí)間里都未能引起編碼理論界的重視，歷經(jīng)數(shù)十年的沉寂之后，隨著計(jì)算機(jī)的高速發(fā)展，以及相關(guān)理論的出現(xiàn)(如置信傳播算法)，Mackay和Neal等人進(jìn)一步完善了LDPC碼的相關(guān)理論，為信道編碼譯碼領(lǐng)域帶來(lái)了繼Turbo碼后的又一個(gè)突破。在理論上，學(xué)者們發(fā)現(xiàn)LDPC碼與之前的Turbo［3］碼一樣，都是能夠逼近香農(nóng)限的糾錯(cuò)碼，其性能在某些條件下甚至還要好于Turbo碼，這足以說(shuō)明它的價(jià)值。在實(shí)際工程領(lǐng)域，LDPC碼已經(jīng)被成功地應(yīng)用于多種系統(tǒng)，例如，中國(guó)地面數(shù)字電視廣播標(biāo)準(zhǔn)(DTMB)［4］，中國(guó)移動(dòng)多媒體廣播標(biāo)準(zhǔn)(CMMB)［5］等均已將LDPC碼作為其的信道編碼標(biāo)準(zhǔn)。毫無(wú)疑問(wèn)，在不久的將來(lái)，LDPC碼必然會(huì)廣泛地應(yīng)用于各種通信系統(tǒng)中。

根據(jù)譯碼判決準(zhǔn)則的不同，LDPC的譯碼算法可以分為以后驗(yàn)概率為判決標(biāo)準(zhǔn)的軟判決譯碼算法和以判決門(mén)限作為判決標(biāo)準(zhǔn)的硬判決譯碼算法。軟判決譯碼算法方面，Gallager首先提出了置信傳播算法(BP)，Kschischang等人在此基礎(chǔ)上對(duì)該算法進(jìn)行了推廣，提出了和積算法(SPA)［6］，此后學(xué)者們又提出了一些和積算法的改進(jìn)算法，目的主要在于降低算法的復(fù)雜度，例如最佳APP譯碼算法、對(duì)數(shù)域和積算法(LLR－BP)［7］、最小和算法(MS)［7］等。

在硬判決算法方面，最具有代表性的是由Gallager提出的基于判決門(mén)限的比特翻轉(zhuǎn)算法(BF)［2］，該算法操作簡(jiǎn)單、復(fù)雜度較低、易于硬件實(shí)現(xiàn)，但是其性能比較差，因此，為了提高算法的性能，Kou Y等人對(duì)BF算法進(jìn)行了改進(jìn)，提出了加權(quán)比特翻轉(zhuǎn)(WBF)［8－9］算法，該算法在每一輪的迭代中，都對(duì)每個(gè)變量節(jié)點(diǎn)進(jìn)行可靠性計(jì)算，并翻轉(zhuǎn)可靠性最小的變量節(jié)點(diǎn)，大大提高了性能，但是由于每輪迭代只能翻轉(zhuǎn)一個(gè)變量節(jié)點(diǎn)，且需要引入可靠性的計(jì)算，導(dǎo)致算法的復(fù)雜度增加。

本文在已有硬判決算法的基礎(chǔ)之上，對(duì)WBF算法進(jìn)行了改進(jìn)，改進(jìn)的算法在前兩輪迭代中可以同時(shí)翻轉(zhuǎn)多個(gè)變量節(jié)點(diǎn)，使得譯碼的運(yùn)行時(shí)間大大減少。仿真結(jié)果表明，改進(jìn)后的譯碼算法在高信噪比條件下的譯碼性能要好于傳統(tǒng)的算法，并且能夠降低WBF算法的復(fù)雜度，減少譯碼的迭代次數(shù)，從而兼顧譯碼性能與譯碼效率。

1 傳統(tǒng)硬判決算法

1.1 BF 算法

由Gallager提出的基于判決門(mén)限的比特翻轉(zhuǎn)算法(BF)操作簡(jiǎn)單，復(fù)雜度較低，且易于硬件實(shí)現(xiàn)，在LDPC碼譯碼領(lǐng)域曾經(jīng)得到廣泛的應(yīng)用，下面就從BF算法開(kāi)始，介紹其譯碼原理，以及基于其的改進(jìn)算法WBF。

考慮一個(gè)二進(jìn)制的規(guī)則LDPC碼，碼長(zhǎng)為N，信息位的長(zhǎng)度為K，其校驗(yàn)矩陣為一個(gè)M×N的稀疏矩陣，即H={hmn}(0≤m≤M －1，0≤n≤N－1)，“稀疏”體現(xiàn)在校驗(yàn)矩陣中只有極少量的“1”，其余位置由“0”組成。對(duì)于二進(jìn)制的規(guī)則LDPC碼，其校驗(yàn)矩陣每行“1”的個(gè)數(shù)都相同，設(shè)為q，表示每個(gè)校驗(yàn)方程中所包含的碼元數(shù)目相同，這些碼元都受到該校驗(yàn)方程的約束;校驗(yàn)矩陣每列所包含的“1”的個(gè)數(shù)也相同，設(shè)為p，表示每個(gè)碼元都參與了p個(gè)校驗(yàn)方程，即被p個(gè)檢驗(yàn)方程約束。Gallager在提出LDPC碼后，就證明了當(dāng)p≥3時(shí)，這類(lèi)碼的漢明距離特性非常好。

在信息傳輸?shù)倪^(guò)程中，要發(fā)送的信息碼字通過(guò)信道編碼后得到帶有校驗(yàn)碼的二進(jìn)制碼字序列v=［v0，v2，…，vN－1］，該序列通過(guò) BPSK 調(diào)制，按照映射 rn=1 －2vn，得到一個(gè)對(duì)應(yīng)序列 r= ［r0，r1，…，rN－1］;然后該序列進(jìn)入信道，信道為一個(gè)AWGN信道，其均值為0、方差為N0/2;通過(guò)信道后，得到輸出序列 y=［y0，y1，…，yN－1］，根據(jù)輸出序列y進(jìn)行判決，就可以得到每個(gè)比特的二進(jìn)制硬判決值 z= ［z0，z1，…，zN－1］，即

在信息通過(guò)信道進(jìn)行傳輸?shù)倪^(guò)程中，由于噪聲等因素的干擾，會(huì)使得信號(hào)遭到破壞從而導(dǎo)致誤碼，這時(shí)，那些錯(cuò)誤碼元將不再滿足各自所參與的校驗(yàn)方程。比特翻轉(zhuǎn)算法(BF)正是根據(jù)這一性質(zhì)，在每一輪的迭代過(guò)程中，先根據(jù)上一輪每個(gè)比特的硬判決值計(jì)算每個(gè)校驗(yàn)方程的值z(mì)n，如果每一個(gè)校驗(yàn)方程都為0，也就是可以認(rèn)為判決序列滿足所有校驗(yàn)方程，則停止迭代，譯碼成功;否則，需要計(jì)算每位比特所不滿足的校驗(yàn)方程的個(gè)數(shù)，即在其參與的所有校驗(yàn)方程中，校驗(yàn)和為1的方程的個(gè)數(shù)，如果在某些比特所參與的所有檢驗(yàn)方程中，其不滿足校驗(yàn)方程的個(gè)數(shù)大于預(yù)先設(shè)定好的判決門(mén)限T，那么就將這些比特進(jìn)行翻轉(zhuǎn)，由此就能得到一個(gè)新的判決序列，然后進(jìn)入下一輪的迭代，直到所有校驗(yàn)方程都滿足，或者達(dá)到最大的迭代次數(shù)，譯碼失敗。在上述譯碼過(guò)程中，門(mén)限T的選取非常重要，其對(duì)于譯碼性能的影響非常大。

BF算法流程如下:

1)根據(jù)硬判決序z=［z0，z1，…，zN－1］列以及校驗(yàn)矩陣H，利用式(2)計(jì)算錯(cuò)誤伴隨圖樣s= ［s1，s2，…，sm］，如果s為0，則迭代停止，輸出判決序列;否則，進(jìn)入步驟2)。

2)在每個(gè)碼元所參與的校驗(yàn)方程中，計(jì)算其不滿足校驗(yàn)方程的個(gè)數(shù)，記作

3)如果fn＞T，那么翻轉(zhuǎn)zn，得到新的比特值。

4)重復(fù)前3步直至譯碼成功，即s=0，或者達(dá)到最大迭代次數(shù)，即譯碼失敗。

從算法步驟可以看出，BF算法只需要在二進(jìn)制域進(jìn)行簡(jiǎn)單的邏輯運(yùn)算，實(shí)現(xiàn)非常簡(jiǎn)單，但其性能和軟判決譯碼算法相比較差，因此，應(yīng)用于對(duì)LDPC碼進(jìn)行粗略的譯碼，或者是信道條件很好的情況下。

1.2 WBF 算法

傳統(tǒng)的BF算法只需進(jìn)行簡(jiǎn)單的邏輯運(yùn)算，易于實(shí)現(xiàn)，且操作簡(jiǎn)單，但是其性能較差，這是由于其比特翻轉(zhuǎn)的依據(jù)是該比特所對(duì)應(yīng)的不滿足校驗(yàn)方程的數(shù)目，這樣的判決依據(jù)并不精確。經(jīng)過(guò)研究分析，Kou Y等人發(fā)現(xiàn)，對(duì)于一組接收比特 y= ［y0，y1，…，yN－1］中的任意一位比特 yn，其可靠性都可以用自身的絕對(duì)值來(lái)度量，也就是說(shuō)，該接收比特的絕對(duì)值越大，對(duì)其進(jìn)行的判決值就越可靠?；谶@個(gè)原理，在傳統(tǒng)的BF算法中引入了每個(gè)校驗(yàn)方程的可信度以及每一個(gè)比特的權(quán)重等軟信息，提出了加權(quán)比特翻轉(zhuǎn)(WBF)算法。

在每一輪的迭代過(guò)程中，WBF算法利用參與每個(gè)校驗(yàn)方程的輸出比特的最小幅值對(duì)每個(gè)變量節(jié)點(diǎn)進(jìn)行加權(quán)，計(jì)算翻轉(zhuǎn)函數(shù)，并認(rèn)為翻轉(zhuǎn)函數(shù)值最大的比特出現(xiàn)了錯(cuò)誤，應(yīng)進(jìn)行翻轉(zhuǎn)。定義N(m)={n|hmn=1}表示參與第m個(gè)校驗(yàn)方程的比特的集合，M(n)={n|hmn=1}表示第n個(gè)比特參與的校驗(yàn)方程的集合，那么第m個(gè)校驗(yàn)方程的可信度表示為

也就是說(shuō)，如果一個(gè)校驗(yàn)方程所對(duì)應(yīng)的比特的最小絕對(duì)值大于另一個(gè)校驗(yàn)方程所對(duì)應(yīng)的比特的最小絕對(duì)值，那么該校驗(yàn)方程的可信度就更高。

WBF算法首先依據(jù)上一輪的判決序列計(jì)算每個(gè)校驗(yàn)方程的值，驗(yàn)證是否滿足校驗(yàn)方程，如果所有的校驗(yàn)方程都滿足，那么停止迭代，譯碼成功;否則，根據(jù)式(4)計(jì)算每個(gè)校驗(yàn)方程的可信度，并且對(duì)每個(gè)碼元進(jìn)行加權(quán)，計(jì)算每個(gè)碼元的翻轉(zhuǎn)函數(shù)，即

對(duì)翻轉(zhuǎn)函數(shù)最大的碼元比特進(jìn)行翻轉(zhuǎn)，得到新的判決序列，如果新判決序列滿足所有校驗(yàn)方程，或者譯碼過(guò)程達(dá)到了最大迭代次數(shù)，那么譯碼結(jié)束;否則，進(jìn)入下一輪迭代。

WBF 算法流程如下［10］:

1)根據(jù)硬判決序列z=［z0，z1，…，zN－1］以及校驗(yàn)矩陣H，利用式(2)計(jì)算錯(cuò)誤伴隨圖樣 s= ［s0，s1，…，sm］，如果s=0，則迭代停止，輸出判決序列;否則，進(jìn)入步驟2)。

2)對(duì)于m=0，1，…，M －1，利用式(4)計(jì)算每一個(gè)校驗(yàn)方程的可信度。

3)對(duì)于n=0，1，…，N －1，利用每個(gè)校驗(yàn)方程的可信度，對(duì)相應(yīng)的碼元進(jìn)行加權(quán)，利用式(5)計(jì)算每個(gè)碼元的翻轉(zhuǎn)函數(shù)，并將翻轉(zhuǎn)函數(shù)值最大的碼元進(jìn)行翻轉(zhuǎn)，得到新的判決序列。

4)重復(fù)前3步，直到所有校驗(yàn)方程都被滿足，輸出判決序列，譯碼成功;或者達(dá)到最大迭代次數(shù)，譯碼失敗。

與傳統(tǒng)的BF算法相比，WBF算法引入了實(shí)數(shù)加權(quán)處理，可以更加有效地對(duì)錯(cuò)誤比特進(jìn)行定位，獲得譯碼性能的提高，但是加大了算法復(fù)雜度，增加了計(jì)算量。此外，該算法還有一個(gè)很大的缺陷，由于每一輪迭代只是將翻轉(zhuǎn)函數(shù)最大值所對(duì)應(yīng)的比特翻轉(zhuǎn)，因此一輪迭代僅僅能翻轉(zhuǎn)1比特位，這樣必將增大迭代的次數(shù)，影響整體譯碼的速度。

2 改進(jìn)的加權(quán)比特翻轉(zhuǎn)算法

當(dāng)今的通信系統(tǒng)對(duì)于實(shí)時(shí)性要求越來(lái)越高，需要在確保整體譯碼性能較好的基礎(chǔ)上，盡可能實(shí)現(xiàn)快速譯碼，通過(guò)上述分析可以看出，WBF算法并不能滿足這一要求。

傳統(tǒng)BF算法可以同時(shí)翻轉(zhuǎn)多個(gè)比特位，這是因?yàn)槠湟昧伺袥Q門(mén)限T，因此可以設(shè)想，如果對(duì)WBF算法也引入判決門(mén)限T，將翻轉(zhuǎn)函En數(shù)大于T的比特都進(jìn)行翻轉(zhuǎn)，就可以在每一次迭代中同時(shí)翻轉(zhuǎn)多位比特，提高譯碼的效率。此外，為簡(jiǎn)化算法的復(fù)雜度，更好地兼顧譯碼性能和譯碼效率，僅僅將判決門(mén)限應(yīng)用在改進(jìn)算法的前兩次迭代過(guò)程中。

在WBF算法中，比特翻轉(zhuǎn)函數(shù)的信息僅僅是來(lái)自校驗(yàn)關(guān)系，而在改進(jìn)的RWBF算法中，翻轉(zhuǎn)函數(shù)還考慮了比特自身的信息，即把每個(gè)輸出比特的絕對(duì)值也引入到其所對(duì)應(yīng)的翻轉(zhuǎn)函數(shù)中，這樣就兼顧了比特自身的信息以及來(lái)自校驗(yàn)關(guān)系的信息，使得翻轉(zhuǎn)函數(shù)的定義更加準(zhǔn)確，改進(jìn)后的翻轉(zhuǎn)函數(shù)定義為

需要強(qiáng)調(diào)的是，判決門(mén)限值T并不是固定的，它將隨著LDPC碼參數(shù)的不同而改變，為了獲得最佳的譯碼性能，可以由仿真來(lái)確定。

RWBF算法流程如下:

1)根據(jù)硬判決序列z=［z0，z1，…，zN－1］以及校驗(yàn)矩陣H，利用式(2)計(jì)算錯(cuò)誤伴隨圖樣 s= ［s0，s1，…，sm］，如果s=0，則迭代停止，輸出判決序列;否則，進(jìn)入步驟2)。

2)對(duì)于m=0，1，…，M －1，利用式(4)計(jì)算每一個(gè)校驗(yàn)方程的可信度。

3)對(duì)于n=0，1，…，N －1，利用每個(gè)校驗(yàn)方程的可信度，對(duì)相應(yīng)的碼元進(jìn)行加權(quán)，利用式(6)計(jì)算每個(gè)碼元的翻轉(zhuǎn)函數(shù)。

4)如果迭代次數(shù)是1或者2，那么將所有的翻轉(zhuǎn)函數(shù)值大于判決門(mén)限T的比特都進(jìn)行翻轉(zhuǎn);如果迭代次數(shù)大于2，那么將翻轉(zhuǎn)函數(shù)值最大的比特進(jìn)行翻轉(zhuǎn)。

5)重復(fù)前4步，直到所有校驗(yàn)方程都被滿足，輸出判決序列，譯碼成功;或者達(dá)到最大迭代次數(shù)，譯碼失敗。

從上述的譯碼流程可以看出，RWBF算法在迭代次數(shù)大于2之后，其復(fù)雜度以及計(jì)算量與WBF算法完全相同，但是在前2次迭代中，該算法可以翻轉(zhuǎn)多個(gè)比特，而WBF算法每一次迭代都只能翻轉(zhuǎn)1位比特，因此RWBF算法具有比WBF算法更快的譯碼速度。

3 仿真分析

仿真采用IEEE802.16e標(biāo)準(zhǔn)，LDPC碼碼長(zhǎng)N=2 304，碼率R=5/6，調(diào)制方式為BPSK，用于觀察傳統(tǒng)的BF、WBF硬判決算法和本文提出的改進(jìn)型譯碼算法RWBF的誤碼率性能。仿真所采用的是高斯白噪聲信道(AWGN)，仿真平臺(tái)為MATLAB，實(shí)驗(yàn)采用蒙特卡洛法，每個(gè)信噪比下實(shí)驗(yàn)1 000次，算法仿真結(jié)果如圖1、圖2所示。

圖1、圖2中分別仿真了LDPC譯碼過(guò)程中最大迭代次數(shù)分別為5次和10次時(shí)，BF，WBF和RWBF算法的性能。從圖中可以看出，隨著最大迭代次數(shù)從5次增大到10次，3種算法的性能都得到了一定的提高。當(dāng)信噪比小于5 dB時(shí)，3種算法的性能相差不大，而在性噪比大于5 dB的高信噪比下，最大迭代次數(shù)的選取將會(huì)影響到算法的性能:最大迭代次數(shù)為5次，RWBF譯碼算法(β=0.5)性能明顯好于BF以及WBF算法;最大迭代次數(shù)為10次，當(dāng)信噪比大于6.5 dB時(shí)，RWBF譯碼算法在性能上比BF以及WBF算法好，在BER=10－5，RWBF算法比WBF算法性能提高近1 dB，但是信噪比在5～6.5 dB之間時(shí)，RWBF算法性能與WBF算法相比略有下降。此外，RWBF算法的最大譯碼迭代次數(shù)從10次變?yōu)?次時(shí)，性能并沒(méi)有明顯降低，而B(niǎo)F和WBF算法迭代次數(shù)變少時(shí)，譯碼性能惡化較為明顯。因此，對(duì)于RWBF算法而言，可以在保證譯碼性能的前提下，適當(dāng)減少迭代次數(shù)，兼顧算法的性能和復(fù)雜度。

4 結(jié)論

LDPC碼是能夠逼近香農(nóng)限［11］的糾錯(cuò)碼，它良好的應(yīng)用前景已經(jīng)引起學(xué)術(shù)界以及IT業(yè)的高度重視。本文在傳統(tǒng)的硬判決BF算法、WBF算法的基礎(chǔ)之上進(jìn)行了改進(jìn)，改進(jìn)的算法在譯碼的迭代過(guò)程中引入了判決門(mén)限，可以同時(shí)翻轉(zhuǎn)多個(gè)比特，因此，能夠降低譯碼的迭代次數(shù)，使得譯碼的運(yùn)行時(shí)間大大減少。此外，考慮到如果讓每一個(gè)比特所對(duì)應(yīng)的翻轉(zhuǎn)函數(shù)都與門(mén)限T比較，勢(shì)必將增加多余的計(jì)算，增大算法的復(fù)雜度。因此，為了更好地兼顧譯碼性能和譯碼效率，僅僅將判決門(mén)限應(yīng)用在改進(jìn)算法的前兩次迭代過(guò)程中。仿真結(jié)果表明，與傳統(tǒng)算法相比，改進(jìn)算法的譯碼性能不但不會(huì)下降，在高信噪比條件下還能得到一定提高。因此，該算法能夠在保持良好譯碼性能的同時(shí)降低算法的復(fù)雜度，這使得LDPC碼能夠更好地應(yīng)用在4G移動(dòng)通信系統(tǒng)［12］中。

［1］LOELIGER H A.An introduction to factor graphs［J］.IEEE Signal Processing Magazine，2004，21(1):28－41.

［2］GALLAGER R C.Low－density parity－check codes［M］.Cambridge，MA:MIT Press，1963.

［3］朱聯(lián)祥，楊士中，汪紀(jì)鋒.基于因子圖的Turbo碼譯碼［J］.重慶大學(xué)學(xué)報(bào):自然科學(xué)版，2002(7):40－44.

［4］楊知行，王昭城.下一代地面數(shù)字電視廣播系統(tǒng)關(guān)鍵技術(shù)［J］.電視技術(shù)，2011，35(8):22－27.

［5］張鵬，楊剛，楊霏，等.基于改進(jìn)LU分解的CMMB標(biāo)準(zhǔn)中LDPC編碼器設(shè)計(jì)［J］.電視技術(shù)，2010，34(4):33－35.

［6］CAMPELLO J，MODHA D S.Extended bit－filling and LDPC code design［C］//Proc.IEEE Global Telecommunications Conference.［S.l.］:IEEE Press，2001:985－989.

［7］FOSSORIER M P C，MIHALJEVIC M，IMAI H.Reduced complexity iterative decoding of low－density parity check codes based on belief propagation［J］.IEEE Trans.Communications，1999，47(5):673－680.

［8］KOU Y，LIN S，F(xiàn)OSSORIER M P C.Low density parity check codes based on finite geometries:a rediscovery and new results［J］.IEEE Trans.Information Theory，2001，47(7):2711－2736.

［9］ZEIDAN H R，ELSABROUTY M M.Modified iterative two－stage hybrid decoding algorithm for low－density parity－check(LDPC)codes［C］//Proc.IEEE 69th Vehicular Technology Conference.［S.l.］:IEEE Press，2009:1－5.

［10］ZHANG J，F(xiàn)OSSORIER M P C.A modified weight bit－flipping decoding of low－density parity－check codes［J］.IEEE Communications Letters，2004，8(3):165－167.

［11］彭代淵，蔣華，郭春生，等.信息論與編碼理論［M］.武漢:武漢大學(xué)出版社，2008.

［12］楊宇良.穿越20年:通信技術(shù)進(jìn)化論［J］.軟件工程師，2011(11):14－20.