一種LDPC碼混合迭代譯碼算法研究

蘇一棟，陳樹新，林 誠

(空軍工程大學(xué)電訊工程學(xué)院，陜西 西安 710077)

Gallager在1962年提出LDPC碼是一類可以用稀疏矩陣或二分圖定義的線性分組碼[1]，它具有性能逼近香農(nóng)限、譯碼復(fù)雜度低、可并行操作、適合硬件實現(xiàn)的優(yōu)點。近年來LDPC碼因其優(yōu)異的性能以及簡潔的形式成為編碼界研究的熱點，并在通信領(lǐng)域擁有廣泛的應(yīng)用前景。現(xiàn)在許多通信標(biāo)準(zhǔn)都應(yīng)用了LDPC碼，例如寬帶無線接入?yún)f(xié)議IEEE 802.16e、下一代衛(wèi)星數(shù)字視頻廣播標(biāo)準(zhǔn)DVBS2，CCSDS 標(biāo)準(zhǔn)以及 GB20600 標(biāo)準(zhǔn)等[2]。

LDPC碼的譯碼算法可分為硬判決算法和軟判決算法兩種。兩種算法各有優(yōu)勢和不足，硬判決易于實現(xiàn)，但性能較差;軟判決性能較好，但復(fù)雜度高。文獻[3]提出了混合比特反轉(zhuǎn)(HBF)譯碼算法，核心思想是先進行BP譯碼，再進行BF譯碼，并且指出在譯碼復(fù)雜度不增加許多的情況下，HBF算法性能優(yōu)于BP算法，此譯碼算法是先進行軟判決，再進行硬判決，雖然性能有所提高，但是譯碼復(fù)雜度并沒有降低，還有所升高。本文提出了一種混合迭代譯碼算法(Mixed Iteration Algorithm，MIA)，核心思想是先進行硬判決，再進行軟判決，這樣在誤碼率性能沒有下降的前提下，譯碼復(fù)雜度大大降低，并且減小了傳播時延。

1 LDPC譯碼算法

1.1 硬判決算法

最初的硬判決算法是由Gallager提出的比特翻轉(zhuǎn)算法(BF)[1]，原理是傳輸序列的某一比特參與的校驗方程錯誤越多，則認(rèn)為此比特錯誤的概率越大，因此翻轉(zhuǎn)該比特。BF算法在迭代過程中傳遞的是二進制硬信息，復(fù)雜度低，但性能較差。為了進一步提高BF算法的性能，Y.Kou等提出了一種加權(quán)比特翻轉(zhuǎn)(WBF)算法[4]，考慮利用信道輸出的軟信息，也就是比特判決的可靠度越大，則其硬判決值的準(zhǔn)確度就越高，因而獲得了性能與復(fù)雜度之間的良好折中。WBF算法將一個校驗關(guān)系的破壞歸因于校驗方程中絕對值最小的那一個符號。如果校驗方程不成立，該方程中所有相關(guān)符號都可能出錯，絕對值越小，符號出錯的可能性越大，但絕對值較大的符號的可信度同樣不應(yīng)被忽略?；谝陨戏治?，F(xiàn)eng Guo等提出了一種可靠性加權(quán)比特翻轉(zhuǎn)(RRWBF)算法[5]。

1.2 軟判決算法

在軟判決譯碼算法方面，最初Gallager提出了置信傳播算法(Belief Propagation Algorithm，BP)，其中需要大量乘法和加法運算，Kschischang等將BP算法作了改進[6]，通過對數(shù)將乘法運算變?yōu)榧臃ㄟ\算，即對數(shù)域BP算法(LLR BP)，在計算校驗位節(jié)點信息時，該算法要用到雙曲正切運算，實現(xiàn)復(fù)雜，為此，F(xiàn)ossorier研究了低復(fù)雜度的迭代譯碼算法[7－8]，將校驗位節(jié)點信息的計算簡化為求符號運算和求最小值運算，提出了最小和算法(UMP BPBased)。

2 MIA算法

RRWBF算法操作簡單，易于硬件實現(xiàn)，但是性能較差，UMP BP－Based算法性能較好，但實現(xiàn)復(fù)雜度較高。MIA算法就是將兩者結(jié)合，通過設(shè)定最大迭代次數(shù)iterRRWBF和iterMSA，提供的誤碼率性能接近UMP BPBased算法，譯碼復(fù)雜度在RRWBF和UMP BP－Based算法之間，并且減小了傳播時延。

假設(shè)二進制碼字 c=[c0，c1，…，cN－1]，經(jīng)過 BPSK 調(diào)制后得到序列 x=[x0，x1，…，xN－1]，其中 xn=1 － 2cN，0≤n≤N－1，x進入均值為0，方差為σ2=N0/2的AWGN 信道后得到信道輸出序列 y=[y0，y1，…，yN－1]，其中yn=xn+vn，0≤n≤N－1，vn為加性高斯白噪聲。根據(jù)接收序列y進行判決得到二進制硬判決序列z=[z0，z1，…，zN－1]。MIA 算法的步驟如下:

1)計算校正子 s=[s0，s1，…，sM－1]，即

如果s=0，停止迭代，輸出硬判決序列z并顯示譯碼成功，否則進入步驟2)。

2)計算翻轉(zhuǎn)函數(shù)En，即

3)翻轉(zhuǎn)最大的En所對應(yīng)的比特zn。

4)若s=0，則譯碼結(jié)束;若s≠0且未達到最大迭代次數(shù)，重復(fù)步驟1)～3)，否則，執(zhí)行后續(xù)步驟。

5)初始化L(qij)=L(ci)=2yi/σ2。

6)進行迭代處理，其中校驗節(jié)點消息處理為

若L(Qi)＞ 0，則，否則;若或者達到最大迭代次數(shù)，則譯碼結(jié)束，否則從步驟6)繼續(xù)迭代。

3 算法仿真及分析

為了驗證混合譯碼算法的性能，采用BPSK調(diào)制、AWGN信道，選用Mackay的1A方法生成碼長為200、碼率1/2的LDPC碼進行性能仿真。

3.1 算法性能比較

BF算法、RRWBF算法、UMP BP－Based算法和MIA算法在最大迭代次數(shù)為10時的誤碼率曲線如圖1所示。

圖1 最大迭代次數(shù)為10時的誤碼性能

由圖1可以看出，MIA算法誤碼率性能接近UMP BP－Based算法。

3.2 不同算法迭代次數(shù)比較

LDPC碼的每種譯碼算法都要設(shè)定算法最大迭代次數(shù)，算法迭代次數(shù)會隨著Eb/No的增大而減小，算法的復(fù)雜度一部分決定于算法的平均迭代次數(shù)，而MIA算法的平均迭代次數(shù)是由RRWBF算法和UMP BP－Based算法的平均迭代次數(shù)共同構(gòu)成的。根據(jù)蒙特卡羅法可以計算固定Eb/No值時的算法平均迭代次數(shù)，本節(jié)設(shè)定算法的最大迭代次數(shù)為50，BF算法、RRWBF 算法、UMP BP－Based 算法和 LLR BP算法4種不同算法的平均迭代次數(shù)曲線如圖2所示。

圖2 不同算法的平均迭代次數(shù)

由圖2可以得出，當(dāng)Eb/No=1 dB時，各算法的平均迭代次數(shù)如表1所示。

表1 Eb/No=1 dB時的各算法的平均迭代次數(shù)

3.3 算法復(fù)雜度分析

碼率1/2的LDPC碼(n，p，2p)，各種算法的每次迭代的運算量如表2所示[9]。

表2 各算法每次迭代運算量

由表2可以計算，本文選用Mackay的1A方法生成的碼為(200，3，6)，每次迭代時RRWBF算法需217次加法，UMP BP－Based算法需850次加法，RRWBF算法運算量是UMP BP－Based算法的1/4。由分析可知，Eb/No=1 dB時，RRWBF算法誤碼率性能約為10－2，根據(jù)分析可知，RRWBF算法平均迭代次數(shù)為11，UMP BP－Based算法平均迭代次數(shù)為4?？梢远x:平均算法復(fù)雜度為Iaverage，單次算法復(fù)雜度為I，平均迭代次數(shù)為N，則Eb/No=1 dB時，UMP BP－Based和MIA算法平均算法復(fù)雜度公式分別為

由此可以計算，在Eb/No=1 dB時，MIA算法平均算法復(fù)雜度為2431次加法，而UMP BP－Based平均算法復(fù)雜度為3400次加法，MIA算法比UMP BP－Based算法運算復(fù)雜度降低了28.5%。

4 小結(jié)

本文提出的MIA算法先進行了硬判決，后進行了軟判決譯碼，充分發(fā)揮了RRWBF算法實現(xiàn)復(fù)雜度低，UMP BP－Based算法性能好的優(yōu)點，實現(xiàn)了在誤碼率性能沒有下降的前提下，譯碼復(fù)雜度明顯降低的效果，進而使得傳播時延得到減小。根據(jù)MIA算法設(shè)計的LDPC解碼器將會非常適用于質(zhì)量很差、實時通信要求較高的信道，如臨近空間雨衰信道、蜂窩網(wǎng)的城市環(huán)境的信道等。設(shè)備復(fù)雜度有所提高，但對于設(shè)備集成度越來越高的今天，這個因素的影響力將越來越小。

[1]GALLAGER R G.Low density parity check codes[M].[S.l.]:MIT Press，1963.

[2]肖揚.Turbo與LDPC編解碼及其應(yīng)用[M].北京:人民郵電出版社，2010.

[3]周立媛，張立軍，陳常嘉.低密度校驗碼的混合比特反轉(zhuǎn)譯碼算法[J].北京交通大學(xué)學(xué)報，2005，29(2):1673－0291.

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

[5]GUO F，HANZO L.Reliability ratio based weighted bit－flipping decoding for low－density parity－check codes[J].IEEE Trans.Electronic Letters，2004，40(21):1356－1358.

[6]KSCHISCHANG F R，F(xiàn)REY B J，LOELIGER H A.Factor graphs and the sum－product algorithm[J].IEEE Trans.Information Theory，2001，47(2):498－519.

[7]FOSSORIER M P C.Iterative reliability－based decoding of low－density parity check codes[J].IEEE Journal of Selected Areas in Communications，2001，19(5):908－917.

[8]FOSSORIER M R C，MIHALJEVIC M，IMAI H.Reduced complexity iterative decoding of low－density parity check codes based on belief propagation[J].IEEE Trans.Communication，1999，47(5):673－680.

[9]LIU Zhenyu，PADOS D A.A decoding algorithm for finite－geometry LDPC codes[J].IEEE Trans.Communications，2005，53(3):415－421.