LDPC 碼的改進迭代比特翻轉(zhuǎn)譯碼算法?

劉原華，張美玲

（西安郵電學院通信與信息工程學院，西安710121）

LDPC 碼的改進迭代比特翻轉(zhuǎn)譯碼算法?

劉原華，張美玲

（西安郵電學院通信與信息工程學院，西安710121）

為提高低密度奇偶校驗（LDPC）碼的低復雜度硬判決譯碼算法的性能，提出了一種改進的比特翻轉(zhuǎn)（BF）譯碼算法，在迭代時利用一個交替的門限模式對多個比特進行翻轉(zhuǎn)，降低了每次迭代時比特被錯誤翻轉(zhuǎn)的概率，從而有效提高了譯碼性能。仿真結(jié)果表明，與BF算法相比，該算法在保持低復雜度的基礎上獲得了更好的譯碼性能和更快的收斂速度。

低密度奇偶校驗碼；比特翻轉(zhuǎn)；迭代譯碼

1 引言

早在1962年，Gallager就提出了低密度奇偶校驗碼（LDPC碼）［1］，但由于當時計算能力的限制該類碼一直未得到重視，直到1996年，Mackay和Neal重新發(fā)現(xiàn)了LDPC碼，指出其具有逼近Shannon限的糾錯性能。近年來，LDPC碼因其優(yōu)異的糾錯性能成為編碼領域的研究熱點，目前已廣泛應用于深空通信、光纖通信和衛(wèi)星數(shù)字視頻廣播等領域。

LDPC碼最有效的譯碼算法是迭代置信傳播（BP）譯碼，在迭代過程中傳遞的是概率消息，將接收比特信號的幅度表示成一定精度下的浮點數(shù)，迭代過程中通過進行大量的實數(shù)運算，可獲得逼近Shannon限的性能，然而計算復雜度非常高。為降低計算復雜度，提出了很多替代算法，如最小和算法等，當然帶來了性能上的一定損失。

LDPC碼的另一種譯碼算法是Gallager提出的比特翻轉(zhuǎn)（BF）算法［1］，其只涉及硬判決邏輯運算，而不考慮與接收比特信號的幅度有關的可靠性信息。若某一比特所參與的不滿足的校驗方程的個數(shù)超過某一固定的門限值時，將該比特進行翻轉(zhuǎn)。盡管BF算法僅適用于信噪比較高的系統(tǒng)，但該算法簡單快速且非常易于硬件實現(xiàn)，極有潛力應用于現(xiàn)代高速可靠的通信網(wǎng)絡。BF算法復雜度非常低，但性能較差，為改善譯碼性能，文獻［2］中提出了一種改進的BF算法，在每輪迭代中以一定的概率對部分不滿足的比特進行翻轉(zhuǎn)，而不是翻轉(zhuǎn)所有不滿足的比特，獲得了性能的提高，但譯碼速度有所降低。為加快譯碼速度，在低復雜度的基礎上獲得良好的譯碼性能，有很多學者對各種改進BF算法［3-6］進行了深入研究，使LDPC碼更適于實際應用。

在實時性要求較高的高速通信系統(tǒng)中，需要盡可能加快編譯碼速度，降低編譯碼復雜度。為了使LDPC碼能夠在保證一定糾錯性能的基礎上適于高速通信系統(tǒng)，本文提出了一種改進的BF算法，在迭代過程中利用一個交替變化的門限模式進行比特翻轉(zhuǎn)，在低復雜度的基礎上既改善了譯碼性能又提高了譯碼收斂速度。與BF算法相比，改進BF算法在復雜度不變的同時獲得了更好的性能，非常適用于設計高吞吐量的硬件譯碼器。

2 BF算法

LDPC碼由其稀疏的校驗矩陣H所確定，若H的維數(shù)為M×N，且H的每一列均有γ個“1”，每一行均有ρ個“1”，其余元素均為“0”，則H的零空間即為碼長為N的二進制規(guī)則LDPC碼。

假設信道采用均值為0、方差為σ2=N0／2的加性高斯白噪聲信道（AWGN），調(diào)制方式為二進制相移鍵控（BPSK）調(diào)制。二進制碼字c=［c0，c1，…，cN-1］經(jīng)調(diào)制后映射為序列x=［x0，x1，…，xN-1］，其中xn=1-2cn（0≤n≤N-1），信道的輸出序列為r=［r0，r1，…，rN-1］，其中rn=xn+vn（0≤n≤N-1），vn為高斯噪聲變量，接收序列r對應的硬判決序列為z=［z0，z1，…，zN-1］。

BF算法在每輪迭代中，首先根據(jù)上一輪的硬判決序列計算校正子的值。如果校正子為全0向量，則停止譯碼，并顯示譯碼成功；否則對硬判決序列中的每一比特，計算其參與的不滿足的校驗方程的個數(shù)，即校正子中1的數(shù)目，記為fn，若fn超過某個預先設定的門限T，則對該碼元比特zn進行翻轉(zhuǎn)，從而得到一個新的硬判決序列。然后進入下一輪迭代，直至校正子為全0向量或者達到最大迭代次數(shù)。BF譯碼算法的具體步驟如下。

（3）重復執(zhí)行第1步和第2步直至譯碼成功，或者達到最大迭代次數(shù)。

BF算法是一種硬判決譯碼算法，迭代過程中僅涉及邏輯運算，實現(xiàn)非常簡單。雖然BF算法只在高信噪比時具有好的性能，但非常有潛力應用于功率有限的移動通信或者超高速通信網(wǎng)絡。

3 改進BF算法

為了降低譯碼實現(xiàn)復雜度，提高譯碼速度，使LDPC碼適合于高速通信系統(tǒng)，本文提出了一種改進的BF算法，在迭代過程中利用一個交替的門限模式來判定是否對比特進行翻轉(zhuǎn)，改進算法的譯碼復雜度與BF算法一樣低，只涉及邏輯運算，可實現(xiàn)快速有效的譯碼。

BF算法所依據(jù)的本質(zhì)思想是，對每一碼元比特來說，參與的不滿足的校驗方程越多，則該碼元比特出錯的可能性就越大。最佳門限T的選擇不僅取決于校驗矩陣的結(jié)構(gòu)參數(shù)，同時還取決于信噪比的大小以及錯誤比特的數(shù)目。如果門限T取得太小，則將導致很多正確的比特被錯誤地翻轉(zhuǎn)，致使譯碼無法向正確碼字收斂。另一方面，門限T必須選取得足夠小，才能使參與較少不滿足的校驗方程的錯誤比特能夠被正確翻轉(zhuǎn)。反之，如果門限T取得太大，則將會使譯碼向正確碼字收斂速度減慢，并有可能陷入死循環(huán)使得某些錯誤比特無法翻轉(zhuǎn)。

基于以上分析，本文提出一種可有效利用門限提高糾錯性能的改進BF譯碼算法。首先給出翻轉(zhuǎn)門限模式的概念?；贐F算法，將第1次迭代、第2次迭代、第3次迭代…使用的翻轉(zhuǎn)門限值組成的序列T1-T2-T3-…定義為翻轉(zhuǎn)門限模式。若門限模式的長度小于所需要的迭代次數(shù)，則重復使用該門限模式進行迭代譯碼。例如，若翻轉(zhuǎn)門限模式為T1-T2，則在迭代過程中，奇數(shù)次迭代以T1作為門限，偶數(shù)次迭代以T2作為門限。由上述分析可知，通過對門限模式的精心選取，在迭代過程中可有效降低比特被錯誤翻轉(zhuǎn)的概率，從而提高糾錯性能。

以LDPC碼（1008，3，6）為例，每一碼元比特參與3個校驗方程，翻轉(zhuǎn)門限應該選為3或2。在前幾次迭代時，錯誤比特較多，應該選擇較大的值3作為門限，當錯誤比特的數(shù)目降低到一定程度時，門限應降為2，用來翻轉(zhuǎn)參與大于等于2個不滿足校驗方程的比特。由于門限低，很有可能會使碼元比特的出錯率增大，此時應將門限增大為3來糾正錯誤的比特以降低錯誤比特的數(shù)目。如此交替使用3和2作為門限值直至達到最大迭代次數(shù)可有效提高糾錯性能。最佳門限模式的確定可通過仿真來實現(xiàn)，以達到最佳的糾錯性能。

改進BF算法的具體步驟如下：

（1）由硬判決z根據(jù)式（1）計算校正子s=［s0，s1，…，sM-1］，如果s=0，則停止迭代；否則執(zhí)行第2步；

（2）第i次迭代時，對于每一硬判決比特zn，根據(jù)式（2）計算其參與的不滿足的校驗方程的個數(shù)fn，如果fn≥Ti，則翻轉(zhuǎn)zn；

（3）重復第1步和第2步直至校正子為全0向量，或者達到預先設定的最大迭代次數(shù)。

由上述譯碼步驟容易看出，改進BF算法與BF算法的計算復雜度相同，每輪迭代時僅需要邏輯運算，實現(xiàn)非常簡單，可以節(jié)省大量的能量以及硬件空間。理論分析表明，改進BF算法可通過優(yōu)化門限模式有效降低比特被錯誤翻轉(zhuǎn)的概率，從而獲得糾錯性能的提高。需要指出的是，若LDPC碼校驗矩陣的列重較小，則改進BF算法能夠很容易通過仿真選取最佳的門限模式。而當LDPC碼校驗矩陣的列重較大時，最佳門限模式的選取變得稍微復雜，主要原因是此時所能夠選擇的門限模式較多。眾所周知，LDPC碼是以其校驗矩陣的稀疏性得名，其校驗矩陣中非零元素極少，并且校驗矩陣的行重要大于列重，所以一般情況下校驗矩陣的列重均比較小。另外，門限模式的選取是在迭代譯碼開始之前進行，門限模式一旦確定，在譯碼的迭代過程中無需變更，每輪迭代的復雜度不會增加，這意味著即使門限模式的選取稍微復雜，也并不會影響譯碼算法的整體復雜度。

4 仿真結(jié)果

圖1給出了LDPC碼（1008，3，6）在BF算法和改進BF算法下的誤比特率（BER）性能曲線。BF算法的最大迭代次數(shù)設為50，改進BF算法的最大迭代次數(shù)分別設為2、4、6、10和50。如圖1所示，在BER為10-5時，與BF算法（門限模式為3）相比，通過交替使用門限3和2，改進BF算法（門限模式為3-2）獲得了大約2.5 dB的編碼增益。

圖1 LDPC碼（1008，3，6）在BF算法和改進BF算法下的性能Fig.1 Performance of LDPC code（1008，3，6）with BF and the improved BF algorithms

由圖1可以看出，在門限模式3-2下，改進BF算法在迭代10次以內(nèi)時可有效改善譯碼性能，迭代10次后再增加迭代次數(shù)所獲得的編碼增益變得非常有限，迭代10次獲得的性能與迭代50次獲得的性能幾乎相同，這意味著改進BF算法具有較快的譯碼收斂速度，迭代10次后即可達到近似最佳的性能。由此可以看出，最大迭代次數(shù)選擇為10次，可實現(xiàn)譯碼性能和計算復雜度之間的良好折衷。

圖2給出了LDPC碼（2550，4，10）在BF算法和改進BF算法下的BER性能曲線。BF算法的最大迭代次數(shù)設為50，改進BF算法的最大迭代次數(shù)設為10。如圖2所示，在BER為10-5時，與BF算法（門限模式為3）相比，改進BF算法（門限模式為4-3-2）獲得了0.7 dB的編碼增益。

圖2 LDPC碼（2550，4，10）在BF算法和改進BF算法下的性能Fig.2 Performance of LDPC code（2550，4，10）with BF and the improved BF algorithms

5 結(jié)束語

本文研究了LDPC碼的硬判決BF譯碼算法，發(fā)現(xiàn)通過適當?shù)剡x取譯碼門限，可以有效提高BF算法的性能。由此，提出了一種改進的BF算法，在迭代過程中不是使用一個固定的門限而是利用一個交替的門限模式進行比特翻轉(zhuǎn)，降低了錯誤翻轉(zhuǎn)的概率，提高了譯碼性能。仿真結(jié)果表明，與標準的BF算法相比，改進BF算法以同樣低的復雜度獲得了更優(yōu)的譯碼性能，同時改進BF算法僅需要較少的迭代次數(shù)即可收斂，有效降低了譯碼延時和計算復雜度，非常適用于功率有限的移動通信系統(tǒng)或者實時性要求較高的高速通信網(wǎng)絡。

本文主要是對LDPC碼硬判決譯碼進行研究，為保證復雜度低并未利用信道的軟信息，下一步將分析如何在盡量低的復雜度下利用信道的軟信息進一步提高硬判決譯碼的性能。

［1］Gallager R G.Low density parity check codes［J］.IEEE Transactions on Information Theory，1962，8（1）：21-28.

［2］Miladinovic N，F(xiàn)ossorierM.Improved bit-flipping decoding of low-density parity-check codes［J］.IEEE Transactions on Information Theory，2005，51（4）：1594-1606.

［3］Ngatched TM N，Bossert M，F(xiàn)ahrner A，et al.Two bitflipping decoding algorithms for low-density parity-check codes［J］.IEEE Transactions on Communications，2009，57（3）：591-596.

［4］Dong JQ，Li Y N，Xie N D，et al.Candidate bit based bit -flipping decoding algorithm for LDPC codes［C］／／Proceedings of 2009 IEEE International Symposium on Inforamtion Theory.Seoul，Korea：IEEE，2009：2166-2168.

［5］Hung JH，Chen SG.A 16Gbps real-time BF-based LDPC decoder for IEEE 802.3an standard［C］／／Proceedings of 2011 International Conference on Multimedia and Signal Processing.Guilin，China：IEEE，2011：63-67.

［6］Cho J，Kim J，Sung W.VLSI implementation of a highthroughput soft-bit-flipping decoder for geometric LDPC codes［J］.IEEE Transactions on Circuits and Systems I，2010，57（5）：1083-1094.

LIU Yuan-hua was born in Xuzhou，Jiangsu Province，in 1983.She received the Ph.D.degree from Xidian University in 2010.She is now a lecturer.Her research concerns channel coding and modulation technology.

Email：yuanhliu＠163.com

張美玲（1982—），女，廣東梅州人，2010年于西安電子科技大學獲博士學位，現(xiàn)為西安郵電學院講師，主要從事信息安全方面的研究。

ZHANGMei-lingwasborn in Meizhou，Guangdong Province，in 1982.She received the Ph.D.degree from Xidian University in 2010. She is now a lecturer.Her research concerns information security.

An Im proved Iterative Bit-flipping Decoding Algorithm for Low-density Parity-check Codes

LIU Yuan-hua，ZHANGMei-ling
（School of Communication and Information Engineering，Xi′an University of Posts and Telecommunications，Xi′an，710121，China）

An improved iterative bit-flipping（BF）algorithm adapted for decoding low-density parity-check（LDPC）codes is proposed to improve the performance of the hard-decision BF decoding algorithm.The new algorithm usesan alternating threshold pattern to determine the bitswhether to be flipped or not，and the flipping error probability is effectively decreased.Simulation results show that compared with BF algorithm，the improved BF algorithm improves both the error-correction performance and the convergence speed whilemaintaining the low computational complexity.

low-density parity-check code；bit-flipping；iterative decoding

The National Program on Key Basic Research Project（973 Program）（2012CB328300）；The Scientific Research Program Funded by Shaanxi Provincial Education Department（11JK1007）；The Program for Young Teachers in Xi′an University of Posts and Telecommunications（No.0001286）

TN911.21

A

10.3969／j.issn.1001-893x.2012.04.013

劉原華（1983—），女，江蘇徐州人，2010年于西安電子科技大學獲博士學位，現(xiàn)為西安郵電學院講師，主要從事信道編碼、通信調(diào)制方面的研究；

1001-893X（2012）04-0488-04

2011-11-15；

2012-02-17

國家重點基礎研究發(fā)展規(guī)劃（973計劃）項目（2012CB328300）；陜西省教育廳專項科研計劃項目（11JK1007）；西安郵電學院青年教師基金項目（0001286）