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

蘇一棟，陳樹新，林 誠

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

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

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

1 LDPC譯碼算法

1.1 硬判決算法

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

1.2 軟判決算法

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

2 MIA算法

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

假設二進制碼字 c=[c0，c1，…，cN－1]，經過 BPSK 調制后得到序列 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為加性高斯白噪聲。根據接收序列y進行判決得到二進制硬判決序列z=[z0，z1，…，zN－1]。MIA 算法的步驟如下:

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

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

2)計算翻轉函數En，即

3)翻轉最大的En所對應的比特zn。

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

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

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

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

3 算法仿真及分析

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

3.1 算法性能比較

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

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

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

3.2 不同算法迭代次數比較

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

圖2 不同算法的平均迭代次數

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

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

3.3 算法復雜度分析

碼率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，根據分析可知，RRWBF算法平均迭代次數為11，UMP BP－Based算法平均迭代次數為4。可以定義:平均算法復雜度為Iaverage，單次算法復雜度為I，平均迭代次數為N，則Eb/No=1 dB時，UMP BP－Based和MIA算法平均算法復雜度公式分別為

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

4 小結

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

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

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

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

[4]KOU Y，LIN S，FOSSORIER 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，FREY 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.