一種改進的LDPC碼硬判決譯碼算法

詹 尹，李宏偉

(空軍工程大學信息與導航學院，陜西 西安 710077)

責任編輯:薛 京

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

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

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

本文在已有硬判決算法的基礎之上，對WBF算法進行了改進，改進的算法在前兩輪迭代中可以同時翻轉多個變量節點，使得譯碼的運行時間大大減少。仿真結果表明，改進后的譯碼算法在高信噪比條件下的譯碼性能要好于傳統的算法，并且能夠降低WBF算法的復雜度，減少譯碼的迭代次數，從而兼顧譯碼性能與譯碼效率。

1 傳統硬判決算法

1.1 BF 算法

由Gallager提出的基于判決門限的比特翻轉算法(BF)操作簡單，復雜度較低，且易于硬件實現，在LDPC碼譯碼領域曾經得到廣泛的應用，下面就從BF算法開始，介紹其譯碼原理，以及基于其的改進算法WBF。

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

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

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

BF算法流程如下:

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

2)在每個碼元所參與的校驗方程中，計算其不滿足校驗方程的個數，記作

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

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

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

1.2 WBF 算法

傳統的BF算法只需進行簡單的邏輯運算，易于實現，且操作簡單，但是其性能較差，這是由于其比特翻轉的依據是該比特所對應的不滿足校驗方程的數目，這樣的判決依據并不精確。經過研究分析，Kou Y等人發現，對于一組接收比特 y= ［y0，y1，…，yN－1］中的任意一位比特 yn，其可靠性都可以用自身的絕對值來度量，也就是說，該接收比特的絕對值越大，對其進行的判決值就越可靠。基于這個原理，在傳統的BF算法中引入了每個校驗方程的可信度以及每一個比特的權重等軟信息，提出了加權比特翻轉(WBF)算法。

在每一輪的迭代過程中，WBF算法利用參與每個校驗方程的輸出比特的最小幅值對每個變量節點進行加權，計算翻轉函數，并認為翻轉函數值最大的比特出現了錯誤，應進行翻轉。定義N(m)={n|hmn=1}表示參與第m個校驗方程的比特的集合，M(n)={n|hmn=1}表示第n個比特參與的校驗方程的集合，那么第m個校驗方程的可信度表示為

也就是說，如果一個校驗方程所對應的比特的最小絕對值大于另一個校驗方程所對應的比特的最小絕對值，那么該校驗方程的可信度就更高。

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

對翻轉函數最大的碼元比特進行翻轉，得到新的判決序列，如果新判決序列滿足所有校驗方程，或者譯碼過程達到了最大迭代次數，那么譯碼結束;否則，進入下一輪迭代。

WBF 算法流程如下［10］:

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

2)對于m=0，1，…，M －1，利用式(4)計算每一個校驗方程的可信度。

3)對于n=0，1，…，N －1，利用每個校驗方程的可信度，對相應的碼元進行加權，利用式(5)計算每個碼元的翻轉函數，并將翻轉函數值最大的碼元進行翻轉，得到新的判決序列。

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

與傳統的BF算法相比，WBF算法引入了實數加權處理，可以更加有效地對錯誤比特進行定位，獲得譯碼性能的提高，但是加大了算法復雜度，增加了計算量。此外，該算法還有一個很大的缺陷，由于每一輪迭代只是將翻轉函數最大值所對應的比特翻轉，因此一輪迭代僅僅能翻轉1比特位，這樣必將增大迭代的次數，影響整體譯碼的速度。

2 改進的加權比特翻轉算法

當今的通信系統對于實時性要求越來越高，需要在確保整體譯碼性能較好的基礎上，盡可能實現快速譯碼，通過上述分析可以看出，WBF算法并不能滿足這一要求。

傳統BF算法可以同時翻轉多個比特位，這是因為其引用了判決門限T，因此可以設想，如果對WBF算法也引入判決門限T，將翻轉函En數大于T的比特都進行翻轉，就可以在每一次迭代中同時翻轉多位比特，提高譯碼的效率。此外，為簡化算法的復雜度，更好地兼顧譯碼性能和譯碼效率，僅僅將判決門限應用在改進算法的前兩次迭代過程中。

在WBF算法中，比特翻轉函數的信息僅僅是來自校驗關系，而在改進的RWBF算法中，翻轉函數還考慮了比特自身的信息，即把每個輸出比特的絕對值也引入到其所對應的翻轉函數中，這樣就兼顧了比特自身的信息以及來自校驗關系的信息，使得翻轉函數的定義更加準確，改進后的翻轉函數定義為

需要強調的是，判決門限值T并不是固定的，它將隨著LDPC碼參數的不同而改變，為了獲得最佳的譯碼性能，可以由仿真來確定。

RWBF算法流程如下:

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

2)對于m=0，1，…，M －1，利用式(4)計算每一個校驗方程的可信度。

3)對于n=0，1，…，N －1，利用每個校驗方程的可信度，對相應的碼元進行加權，利用式(6)計算每個碼元的翻轉函數。

4)如果迭代次數是1或者2，那么將所有的翻轉函數值大于判決門限T的比特都進行翻轉;如果迭代次數大于2，那么將翻轉函數值最大的比特進行翻轉。

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

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

3 仿真分析

仿真采用IEEE802.16e標準，LDPC碼碼長N=2 304，碼率R=5/6，調制方式為BPSK，用于觀察傳統的BF、WBF硬判決算法和本文提出的改進型譯碼算法RWBF的誤碼率性能。仿真所采用的是高斯白噪聲信道(AWGN)，仿真平臺為MATLAB，實驗采用蒙特卡洛法，每個信噪比下實驗1 000次，算法仿真結果如圖1、圖2所示。

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

4 結論

LDPC碼是能夠逼近香農限［11］的糾錯碼，它良好的應用前景已經引起學術界以及IT業的高度重視。本文在傳統的硬判決BF算法、WBF算法的基礎之上進行了改進，改進的算法在譯碼的迭代過程中引入了判決門限，可以同時翻轉多個比特，因此，能夠降低譯碼的迭代次數，使得譯碼的運行時間大大減少。此外，考慮到如果讓每一個比特所對應的翻轉函數都與門限T比較，勢必將增加多余的計算，增大算法的復雜度。因此，為了更好地兼顧譯碼性能和譯碼效率，僅僅將判決門限應用在改進算法的前兩次迭代過程中。仿真結果表明，與傳統算法相比，改進算法的譯碼性能不但不會下降，在高信噪比條件下還能得到一定提高。因此，該算法能夠在保持良好譯碼性能的同時降低算法的復雜度，這使得LDPC碼能夠更好地應用在4G移動通信系統［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］朱聯祥，楊士中，汪紀鋒.基于因子圖的Turbo碼譯碼［J］.重慶大學學報:自然科學版，2002(7):40－44.

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

［5］張鵬，楊剛，楊霏，等.基于改進LU分解的CMMB標準中LDPC編碼器設計［J］.電視技術，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，FOSSORIER 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，FOSSORIER 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］.武漢:武漢大學出版社，2008.

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