蘇一棟，陳樹(shù)新，林 誠(chéng)

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

Gallager在1962年提出LDPC碼是一類可以用稀疏矩陣或二分圖定義的線性分組碼[1]，它具有性能逼近香農(nóng)限、譯碼復(fù)雜度低、可并行操作、適合硬件實(shí)現(xiàn)的優(yōu)點(diǎn)。近年來(lái)LDPC碼因其優(yōu)異的性能以及簡(jiǎn)潔的形式成為編碼界研究的熱點(diǎn)，并在通信領(lǐng)域擁有廣泛的應(yīng)用前景?，F(xiàn)在許多通信標(biāo)準(zhǔn)都應(yīng)用了LDPC碼，例如寬帶無(wú)線接入?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)勢(shì)和不足，硬判決易于實(shí)現(xiàn)，但性能較差;軟判決性能較好，但復(fù)雜度高。文獻(xiàn)[3]提出了混合比特反轉(zhuǎn)(HBF)譯碼算法，核心思想是先進(jìn)行BP譯碼，再進(jìn)行BF譯碼，并且指出在譯碼復(fù)雜度不增加許多的情況下，HBF算法性能優(yōu)于BP算法，此譯碼算法是先進(jìn)行軟判決，再進(jìn)行硬判決，雖然性能有所提高，但是譯碼復(fù)雜度并沒(méi)有降低，還有所升高。本文提出了一種混合迭代譯碼算法(Mixed Iteration Algorithm，MIA)，核心思想是先進(jìn)行硬判決，再進(jìn)行軟判決，這樣在誤碼率性能沒(méi)有下降的前提下，譯碼復(fù)雜度大大降低，并且減小了傳播時(shí)延。

1 LDPC譯碼算法

1.1 硬判決算法

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

1.2 軟判決算法

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

2 MIA算法

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

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

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

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

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

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

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

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

6)進(jìn)行迭代處理，其中校驗(yàn)節(jié)點(diǎn)消息處理為

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

3 算法仿真及分析

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

3.1 算法性能比較

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

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

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

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

LDPC碼的每種譯碼算法都要設(shè)定算法最大迭代次數(shù)，算法迭代次數(shù)會(huì)隨著Eb/No的增大而減小，算法的復(fù)雜度一部分決定于算法的平均迭代次數(shù)，而MIA算法的平均迭代次數(shù)是由RRWBF算法和UMP BP－Based算法的平均迭代次數(shù)共同構(gòu)成的。根據(jù)蒙特卡羅法可以計(jì)算固定Eb/No值時(shí)的算法平均迭代次數(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í)，各算法的平均迭代次數(shù)如表1所示。

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

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

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

表2 各算法每次迭代運(yùn)算量

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

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

4 小結(jié)

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

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

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

[3]周立媛，張立軍，陳常嘉.低密度校驗(yàn)碼的混合比特反轉(zhuǎn)譯碼算法[J].北京交通大學(xué)學(xué)報(bào)，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.