基于循環檢測的LDPC比特翻轉譯碼算法研究

朱方強，王中訓，劉 麗，王 娟

（煙臺大學 光電信息科學技術學院，山東 煙臺 264005）

0 引言

低密度奇偶校驗碼（Low-Density Parity-Check，LD?PC）是Gallager[1]于1962年提出的一種基于稀疏校驗矩陣的線性分組碼，但由于當時計算機能力有限，而且級聯碼被認為具有更好的性能，在很長的一段時間內，LDPC碼并未受到重視，直到Mackay和Neal[2]在90年代重新發現并證明LDPC碼是一種逼近香農限的好碼[3]，使用迭代軟信息譯碼的LDPC碼性能甚至超過了Turbo碼，由此對LDPC的研究成為通信領域編譯碼研究的一個熱點。

LDPC碼的譯碼算法基本可分為基于軟判決的譯碼和基于硬判決的譯碼。這些譯碼算法包括基于消息傳遞（Message Passing）的置信傳播（Belief Propagation，BP）算法[3]，改進的BP算法（迭代APP算法、最小和算法等），Gallager提出的比特翻轉（Bit Fliping）算法[1]以及在此基礎上改進的一系列軟硬混合判決算法，如加權比特翻轉算法[4]（WBF）、改進的加權比特翻轉算法[5]（IWBF）、LP加權比特翻轉算法[6]（LP-WBF）等。軟判決算法性能良好但譯碼復雜度高，硬判決算法性能稍差易于硬件實現，有較高的實用性。

本文提出基于比特翻轉的一種改進譯碼算法，對于低密度奇偶校驗矩陣，伴隨式權重會隨著平均錯誤增多而增加，直到錯誤權重大于最小距離的1/2[7]，因此在每次迭代中選擇一個伴隨式權重降低的比特翻轉。同時在比特翻轉算法中存在著多次迭代后算法陷入死循環的問題，本文借鑒文獻[7-8]的循環檢測（Loop Detection，LD）方法有效解決了這個問題。這種改進的基于對接收符號可靠性軟判決的算法在運算復雜度增加不大的情況下使譯碼性能改善顯著。

1 譯碼算法

1.1 LDPC碼基本定義

LDPC碼由校驗矩陣H定義，碼長為n，信息長度為k，H 的維數是m×n，即m行n列（m=n-k）。對于規則LDPC碼有恒定的列重wc和行重wr，非規則碼行重和列重不再固定，但校驗矩陣仍滿足稀疏性[2]。

首先定義譯碼算法中出現的符號。設發送碼字c=(c0,c1,…,cN-1)按照xi=2ci-1準則變為雙極性發送序列x=(x0,x1,…,xN-1)，接收序列為y=(y0,y1,…,yN-1)，其中yi=xi+ni，0 ≤i

在每次迭代時可計算伴隨式s=Z·HT來判斷校驗式和，若所有校驗式都滿足特征子空間為0，則停止譯碼，其中s=(s0,s1,…,sM-1)。對于軟輸出序列 y=(y0,y1,…,yN-1)定義對數似然比為

1.2 本文算法1

BF算法核心思想[1]是根據伴隨式譯碼方案，如果某比特參與的校驗式大多有錯，則認為此比特錯誤概率很大，翻轉比特。基于BF算法提出的算法1的譯碼流程為：1）初始化。設置迭代次數k=0，計算z(0)和s(0)=wt(z(0)·HT)。

2）如果s(k)=0，則進行步驟8）。

3）k← k+1（k+1后，重新賦于k），如果k>kmax將進行步驟9），其中，kmax是最大迭代次數。

6）如果 j(k)=j(k-1)，則進行步驟9）。

7）計算 z(k)=z(k-1)+uj(k)和 s(k)=wt(z(k)·HT)后跳到步驟2）。

8）停止譯碼并返回z(k)。

9）宣布譯碼失敗并返回z(k-1)。

算法1在每次迭代只翻轉1 bit，翻轉的依據是伴隨式權重隨著錯誤權重增多而增加，由于引入計算漢明重使得算法又不同于BF算法。這種判決準則有可能在譯碼中選擇錯誤的位置j翻轉，引進了一個新的錯誤，接著在隨后的迭代譯碼中這個錯誤又有很大可能被糾正。

1.3 本文算法2（算法1的改進）

對算法1可以在幾乎不增加運算復雜度的前提下進行改進并達到更好的性能。借鑒文獻[5]對WBF算法的改進，算法2增加對接收符號的可靠性度量以提高算法性能。

1）|Li|越大說明硬判決結果zi可靠性越高。

2）如果在校驗矩陣H的不同列沒有非零元素重疊，則每列對伴隨式權重的貢獻值為wc。

3）在不同的信噪比下，|Li|的值一般不一樣，所以存在最優權重因子α。對于特定的LDPC碼在某一信噪比下，最優的權重因子選擇譯碼時比特錯誤最小對應的α值，一般需要計算機仿真得到。

當α=0時，算法2就變為算法1。對于這兩種算法，譯碼的最大迭代次數kmax是自定的，對于譯碼的停止規則在算法中已表明：獲得步驟2）的結果，迭代次數為k次，宣布譯碼成功；達到最大迭代次數獲得步驟6）的結果，宣布譯碼失敗，這些都在仿真中可以看到。

1.4 基于循環檢測的算法2（LD）

用j(k)表示在第k次迭代時被翻轉的比特位置，如果j(k)=j(k-1)，則z(k)=z(k-2)，z(k+ρ)=z(k-2+ρ)，其中 ρ為大于 0的實數，這樣算法在第k次迭代時會陷入一個死循環。為了解決上述問題，文獻[6]提出了簡化的破環路算法，即LD算法，通過選擇在第k次迭代時s(k)i的次小值代替最小值來打破這種死循環。

式中：1≤k′

1）初始化。設置迭代次數k=0，計算z(0)和s(0)=wt(z(0)·HT)，設置清除比特位置集合B，使其為空集（原步驟1））。

3）計算n(k′)和w(k′)，1 ≤ k′

2 算法運算復雜度分析

1）算法2的運算復雜度分析

在每次迭代中，通過Nwcwr次異或運算和加法運算來計算伴隨式權重，N-1次比較運算來選擇比特翻轉位。可靠性尺度因子awc| |Li只需在算法的第一次迭代前計算一次，由于比較運算可當做加法運算處理，因此每次迭代需要2N-1次加法運算和Nwcwr次異或運算。

2）基于循環檢測的算法2（LD）運算復雜度分析

一般循環檢測操作的次數與分組碼字長度N沒有關系，只與執行迭代次數有關。在實際仿真中最大迭代次數kmax一般遠小于碼長N，并且譯碼收斂的平均迭代次數小于最大迭代次數kmax。因此，用于循環檢測的運算量與原算法2的2N-1次加法運算和Nwcwr次異或運算量相比可忽略不計，可認為算法2（LD）運算復雜度基本沒有增加。

3）比較幾種算法每次迭代的運算量

BP算法[2-3]需要11Nωc-9N 次乘法，N(ωc+1)次除法以及N(3ωc+1)次加法運算，WBF算法[4]需要N-1+wcwr次加法運算，LP-WBF算法[6]需要N-1+wcwr次加法運算，本文算法2需要2N-1次加法運算和Nwcwr次異或運算。通過比較發現，基于比特翻轉的改進算法每次迭代計算量要比軟判決的BP算法少得多，只有加法運算沒有了乘除運算，更易于硬件實現，而本文的算法2及改進的算法2和同類比特翻轉類算法相比運算復雜度增加不大。

3 仿真試驗及結果分析

基于Matlab仿真平臺對本文算法進行仿真，并與標準BF算法、WBF算法、IWBF算法、LP-WBF算法和BP算法在誤碼率上進行比較。仿真采用BPSK調制，經過噪聲均值為0，方差為N02的加性高斯白噪聲信道。

3.1 算法1與BF算法比較

圖1為列重為3的（504，252）LDPC碼的比特翻轉算法BF與本文算法1誤碼率BER圖像對比，設最大迭代次數kmax為150。由于算法1與BF算法均是單一的硬判決算法，所以在這里單獨比較兩種算法的性能。由圖1可知，在誤碼率為10-3時，算法1與BF算法相比有大約0.5 dB的增益，同一信噪比下，算法1性能改善約一個數量級。由于伴隨式漢明重的引入，算法1的譯碼復雜度要比BF算法大。

3.2 算法2最優α因子的選取

對于給定列重wc的LDPC碼，在給定信噪比下，α因子不同，則算法性能也不一樣。最優α因子的值一般與LDPC碼和具體的碼結構有關。選擇wc為3的（273，191）Gallager碼[9]仿真α因子對比特錯誤概率BER的影響，最大迭代次數kmax為200。圖2和圖3仿真了在不同信噪比下，最優α因子對誤碼率和平均迭代次數的影響。基于最優α因子的定義，由圖2可知，在較低的信噪比下，α因子對比特錯誤概率影響并不明顯。隨著信噪比的增加，最優α因子變化不是很大。圖2和圖3可得到當α大約為1.2時，誤碼率最低，譯碼需要的平均迭代次數最少，即α=1.2為此碼最優權重因子。

3.3 算法2與其他算法性能比較

由圖2和圖3得到，wc為3的（273，191）Gallager碼[9]的最優α因子為1.2。圖4對比了WBF算法、IWBF算法、LP-WBF算法、BP算法、本文算法2以及算法2的改進，即基于循環檢測的算法2（LD）的誤碼率性能。其中，IWBF算法中的權重因子優化為α=0.4，LP-WBF算法是改進的基于循環檢測的算法。除BP算法最大迭代次數為40，其他算法最大迭代次數為200。當信噪比較低時，比特翻轉類算法性能改善較小，軟判決的BP算法性能改善明顯，隨著信噪比增大，本文算法性能改善優于同類基于軟硬混合判決的比特翻轉算法。由圖4可知，基于接收符號可靠性判斷的算法2性能遠優于WBF算法和IWBF算法；不帶循環檢測的算法2譯碼性能比LP-WBF算法稍差一些，當BER為10-5時，LP-WBF算法比算法2多獲得0.2 dB增益；基于循環檢測的算法2（LD）性能要優于 LP-WBF算法，在 BER為10-6時，算法 2（LD）比LP-WBF算法可獲得0.3 dB增益。在BER為10-5時，改進的算法2（LD）比算法2獲得大約0.5 dB增益，與BP算法相比相差大約0.9 dB。

4 小結

本文在比特翻轉算法基礎上提出了基于循環檢測和對接收符號可靠性信息軟判決的譯碼算法。仿真結果表明，硬判決算法1與標準的BF算法相比獲得大約0.5 dB的增益，基于軟硬混合判斷的算法2（LD）性能優于同類的LP-WBF算法約0.3 dB，與軟判決BP算法相比相差大約0.9 dB，這種改進的算法在譯碼復雜度增加不大的情況下顯著改善了譯碼性能，達到了譯碼復雜度和性能的折中。本文只對兩種隨機碼進行了仿真，同樣改進的算法也適用于其他LDPC碼，如RS-LDPC碼、PEG-LD?PC碼等[9]。

[1]GALLAGER R G.Low density parity check codes[EB/OL].[2010-10-18].http：//www.rle.mit.edu/rgallager/documents/ldpc.pdf.

[2] MACKAY D J C，NEAL R M.Near Shannon limit performance of low density parity check codes[J].IEEE Trans.Electronics Letters，1997，33（6）：457-458.

[3] MACKAY D J C.Good error-correcting codes based on very sparse matrices[EB/OL].[2010-10-18].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.1309&rep=rep1&type=pdf.

[4] KOU Y L，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.

[5] ZHANG Juntan，FOSSORIER M P C.A modified weighted bit-flipping decoding of low-density parity-check codes[J].IEEE Trans.Communications Letters，2004，8（3）：165-167.

[6] LIU Zhenyu，PADOS D A.A decoding algorithm for finite-geomety LDPC codes[J].IEEE Trans.Communications，2005，53（3）：415-421.

[7] BOSSERT M.Channel coding for telecommunications[M].New York：Wiley，1999.

[8] BOSSERT M，HERGERT F.Hard and soft-decision decoding beyond the half minimum distance：an algorithm for linear codes[J].IEEE Trans.Information Theory，1986，32（5）：709-714.

[9] 吳黎麗，趙新建.不規則LDPC碼面向4G的性能改進[J].電視技術，2009，33（S2）：184-185.