簡單高效的LDPC碼加權比特翻轉譯碼算法

張高遠，周 亮，文 紅

(電子科技大學通信與抗干擾技術國家重點實驗室 成都 611731)

簡單高效的LDPC碼加權比特翻轉譯碼算法

張高遠，周 亮，文 紅

(電子科技大學通信與抗干擾技術國家重點實驗室 成都 611731)

現有的兩種低密度奇偶校驗(LDPC)碼加權比特翻轉(WBF)譯碼算法雖然具有較低的實現復雜度，但糾錯性能并不理想。該文基于對兩種WBF算法的物理意義和它們之間內在聯系的詳細理論分析，提出一種可靠度外信息修正(ERA)方案。該方案顯著提高了現有兩種低復雜度譯碼算法校驗方程可靠度的準確性，進而提高了翻轉效率。仿真結果表明，在AWGN信道條件下，ERA方案能顯著提高現有兩種WBF算法的譯碼性能，獲得顯著譯碼增益，從而實現了譯碼復雜度和性能間的良好折中。

比特翻轉; 可靠度外信息修正; LDPC碼; 最大后驗概率

低密度奇偶校驗(LDPC)碼[1]是一種逼近香農限的好碼，在深空通信、光通信和磁盤存儲等眾多領域得到廣泛應用[2]。在其眾多譯碼算法中，置信傳播(belief-propagation，BP)[3]算法、歸一化和偏移BP算法[4]性能優異，但實現復雜度較高。APP-Based(a posteriori probability-based)算法和最小和(min-sum, MS)算法[3]是對BP算法的簡化近似，文獻[5-6]提出的歸一化APP-Based (normalized APP-based)、歸一化最小和(normalized MS，NMS)與偏移最小和(offset MS，OMS)算法在性能和實現復雜度上得到一定的折中。比特翻轉(bit flipping, BF)譯碼算法實現最為簡單，適用于要求簡單編譯碼裝置的場合。加權BF(weighted BF, WBF)算法則將校驗節點鄰接的信息節點的最小幅度作為雙極性校驗子的權重[7]。文獻[8]通過引入加權因子，使改進的WBF(modified WBF，MWBF)算法中的翻轉函數更加有效。與MWBF算法相比，文獻[9]提出的IMWBF(improved modified WBF)算法，取得了一定的增益。很多學者對上述WBF算法的結構進行修正，提出了一些改進的算法[10-15]。對于上述WBF算法而言，信息節點和校驗節點之間傳遞的僅僅是二進制信息(即校驗式信息和翻轉比特信息)，屬于二進制置信傳播算法[16]，實現復雜度大大降低。

文獻[17]的IMWBF算法是基于歸一化最小和(normalized MS-based，NMS-Based)算法的最優WBF算法，且WBF算法和MWBF算法是IMWBF算法的簡化形式。但并沒有對IMWBF算法翻轉函數的物理意義做詳細的分析說明，更沒有從理論上得出如何簡化IMWBF算法才能得出WBF算法和MWBF算法。本文從全新的角度出發，首先推導出IMWBF算法，得出其翻轉函數中各項所代表的嚴格的物理意義；其次，根據這種全新的理解方式，推導得出MWBF算法和WBF算法，并闡明3種算法間的內在聯系；最后提出一種可靠度外信息修正(extrinsic reliability adjustment，ERA)方案對WBF和MWBF算法進行改進。

1 基本定義和算法描述

碼長為N、信息位長為K的二元LDPC碼，可由M行N列的校驗矩陣H=[hmn]決定。對于規則LDPC碼，H的第m行中1的數量用dr表示，第n列中1的數量用dc表示。H的第m行中1的位置可表示為A(m)={n:hmn=1}；第n列中1的位置可表示為B(n)={m:hmn=1}。為碼字序列，經BPSK調制后得到進入加性高斯白噪聲信道后得到接收序列是均值為零、方差為σ2高斯白噪聲。為硬判決輸出序列，判決規則為表示錯誤圖樣，如果xn錯誤，則en=1；否則en=0。定義對數似然比為：

1.1 MS-Based WBF算法的推導

記比特xn發生錯誤的先驗概率為qn，比特xn發生錯誤的后驗概率為則對于AWGN信道有[3,18]：從而得到由APP-Based算法可得[3]：

其中，

而

式中，rmn為{xi|Xm′xn}中有奇數個錯誤的概率。利用近似關系[3]：

則有：

從而有：

將式(6)代入式(3)得到：

將式(7)代入式(2)得到：

式中，ωmn為歸一化ERI(normalized ERI，NERI)的幅度，即為文獻[16]中的MS-based WBF算法。(2sm?1)ωmn為第m個校驗方程提供的NERI，由sm和ωmn決定；校驗方程提供的NERI，由smn和決定；為歸一化IRI(NIRI)，即xn的可靠度先驗信息；En為歸一化PRI(NPRI)。

同時可以得出以下結論：1) 可以對滿足{xn|n= argEn>0}的比特都進行翻轉，但性能并不理想[16]。 MS-based WBF算法只對滿足比特翻轉，即對發生錯誤后驗概率最大的比特翻轉。2) 文獻[18]已證明利用Max-log MAP(MLP)算法譯碼的推導方式同樣可以得到式(6)的結果，從而得到式(8)的結果。故MS-Based WBF算法是基于MLP準則的算法。

1.2 IMWBF算法的推導

顯然式(9)中的ωmn也是MS算法中校驗節點傳遞給信息節點的信息的幅度，考慮到ωmn大于BP算法中校驗節點傳遞給信息節點的信息的幅度[6]，可對MS-Based WBF算法中的NERI進行歸一化，便得到歸一化MS-based WBF[18]，其翻轉函數為：

對式(10)進行變換后得到：

式中，α可以看做是α′的倒數[16]。式(11)即是IMWBF算法的翻轉函數，故IMWBF算法是基于歸一化MLP(normalized MLP，NMLP)準則的算法[6]。式(11)中各項所代表的嚴格的物理意義與2.1節中定義的相同。

2 基于ERA方案的WBF算法

2.1 MWBF算法和WBF算法的推導

如果對式(4)采用以下近似計算：

對式(13)做歸一化處理，則可得到xn參加的第m個校驗方程向其提供的NERI：同時考慮到NIRI便得到MWBF算法的翻轉函數為：

由此得到文獻[7]中的WBF算法?？梢?，通過對IMWBF算法的NERI進行近似可得到MWBF算法，WBF算法則是在MWBF算法的基礎上，認為xn差錯與否先驗等概，因此二者在性能上必然會有不同程度的損失。

2.2 ERA方案

相比于IMWBF算法，MWBF算法由于涉及式(12)的近似計算，從而引入某種相關性[5]。具體的，MWBF算法中第m個校驗方程向{xn|n∈A(m)}提供的NERI的幅度都為ωm。然而得到的NERI幅度應該為序列{yn,n∈A(m)}的次小值，即xi得到的外信息的可靠度降低，需要修正。傳統意義上講，要實現這種操作，首先要在中找到滿足的信息節點，然后增加其可靠度[19]。顯然傳統方法是進行“先查找，后增加”的操作。由于WBF算法不涉及可靠度信息的更新傳遞，故增加校驗方程中某個信息節點的可靠度等價于增加與其對應的yn的幅度，即可得到一種比傳統實現方法更加簡單的方法，具體步驟如下：

1) 對y的幅度進行預處理：

以下為基于ERA的MWBF譯碼算法步驟。

初始化：初始化迭代次數k=1，設定最大迭代次數Kmax。

1) 計算伴隨式S，若S全為0，停止迭代，輸出x；否則計算第m個校驗方程的權重

2) 計算翻轉函數為：

3) 比特翻轉為：

4) 用更新過的x計算伴隨式，如果S全零，則終止迭代；如果不為全零，但迭代次數達到最大次數限制，也終止迭代。否則k=k+1，跳至步驟2)。

由上述分析可知，新的實現方法只需進行“加法”的操作。需特別指出的是，傳統實現方法最多只需增加M個信息節點的可靠度，而新的實現方案對校驗方程中每個信息節點的可靠度都增加。而仿真結果表明，新的實現方案同樣能有效地削弱近似計算帶來的相關性，提高譯碼性能。為分析方便，認為1次比較運算等同于1次加法運算，則傳統實現方法共需要M(dr?1)次加法運算。同時，由式(15)可知，新的實現方案僅需要增加N次加法運算和N個存儲單元。顯然ERA方案可同時運用于WBF算法，而理論上得出最優化的修正因子γ仍然具有一定難度，可考慮通過仿真得到。

3 仿真結果和統計分析

本節仿真參數如下：采用列重為3的(504,252) PEG-LDPC碼(記為碼A)和(1 008,504) PEG-LDPC碼(記為碼B)[14]，迭代次數分別設定為50和100；在AWGN信道條件下，采用BPSK調制，在每個信噪比下至少采集1 000個比特錯誤。

3.1 尋找最佳的修正因子γ

文獻[8]通過蒙特卡洛仿真得出了MWBF算法的最優加權因子。類似地，文獻[14]通過仿真得出了基于幅度和的WBF算法的最優加權因子?？梢?，當通過理論分析得到算法所需的最優因子較為困難時，蒙特卡洛仿真是首選的有效方法。由于目前通過理論分析得出修正因子γ較為困難，本文仍采用蒙特卡洛仿真。

圖1 碼A條件下，不同信噪比下γ對ERA-WBF算法性能的影響

圖1為不同信噪比下，ERA-WBF算法在碼A條件下受不同γ影響時的誤比特率性能。由圖1可知，對所有的Eb/N0可以選擇一個固定不變且最優的γ，此時的性能損失可忽略不計，且保持較低的實現復雜度。6.0～6.5 dB時的最優化γ為0.3，而6.75 dB時最優化的γ為0.25，但考慮到6.75 dB時γ=0.25和γ=0.3時性能損失可忽略不計，故本文仿真中ERA-WBF算法在碼A條件下最優化的γ設定為0.3。

3.2 算法性能和實現復雜度比較

圖2為最優參數下，碼A和碼B在各算法下性能比較。MWBF算法的最優加權系數分別設定為0.2和0.3[14]，IMWBF算法的最優加權系數都設定為0.2[9]，ERA-WBF的最優γ分別設定為0.3和0.2，ERA-MWBF的最優γ都設定為0.45。圖3給出碼B在各譯碼算法下平均迭代次數比較。圖4給出碼A在IMWBF和MS-Based WBF算法下誤比特性能。

圖2 碼A和碼B在各譯碼算法下性能比較

圖3 碼B在各算法下平均迭代次數統計

圖4 碼A在IMWBF和MS-Based WBF算法下性能圖

表1 BER=10?5，各算法在碼A和碼B下性能統計

表1給出BER=10?5時，各算法的性能比較。由表1可知，在碼A條件下，ERA-MWBF算法與IMWBF算法的性能基本一致。在BER=10?5時，相對于MWBF算法，ERA-MWBF算法可獲得0.45 dB的增益；ERA-WBF算法相對于WBF算法可獲得0.30 dB的增益。在碼B條件下，當Eb/N0大于4.25 dB時，ERA-MWBF的性能甚至好于IMWBF算法。在Eb/N0大于5.0 dB時，ERA-WBF算法的性能也要好于MWBF算法。從圖3可知，修正后WBF算法和MWBF算法的平均迭代次數大大降低。為分析方便，認為一次比較運算等同于一次加法運算。當Eb/N0=4.5 dB時，由圖3得出，ERA-MWBF算法的平均迭代次數比傳統算法降低20次，加法運算次數平均降低20(N?1+dcdr)=20520次[14]，總體上平均加法運算次數降低了20520?N=19512次。類似的，Eb/N0=4.0 dB和5.0 dB時，總體上平均加法運算次數都減低14 382次。從圖4可知，IMWBF和MS-Based WBF算法分別是基于NMLP準則和MLP準則得出的，因此前者性能必然優于后者。

4 結 束 語

本文從一個新的角度得出IMWBF算法的物理意義，分析了IMWBF算法與WBF算法和MWBF算法的內在聯系。以此為基礎提出一種ERA方案對WBF算法和MWBF算法進行改進。仿真結果表明，AWGN信道下，誤比特率為10?5時，與傳統算法相比，基于ERA方案的WBF和MWBF算法可分別獲得約0.70 dB和0.76 dB的增益，同時實現復雜度有所降低，從而在糾錯性能和實現復雜度之間達到了很好的平衡匹配。文獻[7-15]和本文提出的改進方案都以單比特翻轉模式為出發點，即每次迭代過程中對發生錯誤概率最大的比特執行翻轉操作，隸屬于串行算法。多比特翻轉模式下的算法仍有待深入研究。此外，本文提出的改進方案適用于行重和列重相對較小的LDPC碼。仿真結果表明，此改進方案對于行重和列重較大的LDPC碼則不太適用。針對行重和列重較大的LDPC碼，多比特翻轉模式下的改進方案值得進一步的深入研究。

[1] GALLAGER R G. Low density parity check codes[J]. IEEE Transactions on Information Theory, 1962, 8(1): 21-28.

[2] 施玉晨, 白寶明. 基于多元LDPC碼的多用戶協作方案[J].電子科技大學學報, 2013, 42(8): 205-208. SHI Yu-chen, BAI Bao-ming. Multiuser cooperative scheme based on nonbinary LDPC codes[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(8): 205-208.

[3] FOSSORIER M, MIHALJEVIC M, IMAI H. Reduced complexity iterative decoding low density parity-check codes based on belief propagation[J]. IEEE Transactions on Information Theory, 1999, 47(5): 673-680.

[4] YAZDANI M, HEMATI S , BANIHASHEMI A. Improving belief propagation on graphs with cycles[J]. IEEE Communications Letters, 2004, 8(1): 57-59.

[5] CHEN Jing-hu, FOSSORIER M. Decoding low-density parity check codes with normalized APP-based Algorithm[C]//Global Telecommunication Conference. San Antonio, TX, USA: IEEE, 2001(2): 1026-1030.

[6] CHEN Jing-hu, DHOLAKIA A, ELEFTHERIOU E, et al. Reduced-complexity decoding of LDPC codes[J]. IEEE Transactions on Communications, 2005, 53(8): 1288-1299.

[7] KOU Y, LIN Shu, FOSSORIER M. Low-density parity-check codes based on finite geometries: a rediscovery and new results[J]. IEEE Transactions on Information Theory, 2001, 47(7): 2711-2736.

[8] ZHANG Jun-tan, FOSSORIER M. A modified weighted bit-flipping decoding of low-density parity-check codes[J]. IEEE Communications Letters, 2004, 8(3): 165-167.

[9] JIANG Ming, ZHAO Chun-ming, SHI Zhi-hua, et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes[J]. IEEE Communications Letters, 2005, 9(9): 814-816.

[10] GUO F, HANZO L. Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes[J]. Electronics Letters, 2004, 40(21): 1356-1358.

[11] 劉原華, 張美玲. LDPC碼的改進迭代比特翻轉譯碼算法[J]. 電訊技術, 2012, 52(4): 488-491. LIU Yuan-hua, ZHANG Mei-ling. An improved iterative bit-flipping decoding algorithm for low-density parity-check codes[J]. Telecommunications Engineering, 2012, 52(4): 488-491.

[12] CHEN T. An efficient bit-flipping decoding algorithm for LDPC codes[C]//International Conference on Cross Strait Quad-Regional Radio Science and Wireless Technology. New Taipei City, Taiwan, China: IEEE, 2012: 109-112.

[13] 劉原華, 張美玲. 結構化LDPC碼的改進比特翻轉譯碼算法[J]. 北京郵電大學學報, 2012, 35(4): 116-119. LIU Yuan-hua, ZHANG Mei-ling. Improved bit-flipping method for decoding structured low-density parity-check codes[J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(4): 116-119.

[14] 張高遠, 周亮, 蘇偉偉,等. 基于平均幅度的LDPC碼加權比特翻轉譯碼算法[J]. 電子與信息學報, 2013, 35(11): 2572-2578. ZHANG Gao-yuan, ZHOU Liang, SU Wei-wei, et al. Average magnitude based weighted bit-flipping decoding algorithm for LDPC codes[J]. Journal of Electronics & Information Technology, 2013, 35(11): 2572-2578.

[15] CHEN T. Channel-independent weighted bit-flipping decoding algorithm for low-density parity-check codes[J]. IET Communications, 2012, 6(17): 2968-2973.

[16] NASTARAN M. New iterative decoding algorithms for low-density parity-check (LDPC) codes[D]. Ottawa, Canada: Carleton University, 2011.

[17] WU Xiao-fu, LING C, JING Ming, et al. New insights into weighted bit-flipping decoding[J]. IEEE Transactions on Communications, 2009, 57(8): 2177-2181.

[18] 張立軍, 劉明華, 盧萌. 低密度奇偶校驗碼加權大數邏輯譯碼研究[J]. 西安交通大學學報, 2013, 47(4): 35-38. ZHANG Li-jun, LIU Ming-hua, LU Meng. A research on weighted majority-logic decoding for LDPC codes[J]. Journal of Xi’an Jiaotong University, 2013, 47(4): 35-38.

[20] DARABIHA A, CARUSONE A C, KSCHISCHANG F R. A bit-serial approximate min-sum LDPC decoder and FPGA implementation[C]//IEEE International Symposium on Circuits and Systems. Island of Kos, Greece: IEEE, 2006: 149-152.

編輯張 俊

Simple and Efficient Weighted Bit-Flipping Decoding Algorithm for LDPC Codes

ZHANG Gao-yuan, ZHOU Liang, and WEN Hong
(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China Chengdu 611731)

An extrinsic reliability adjustment (ERA) scheme of low-density parity-check (LDPC) codes is proposed in this paper based on theoretical analysis of the physical significance for two previous weighted bit-flipping (WBF) algorithms, which have less complexity with poor error correcting performance. The novel scheme significantly improves the check-node realiability accuracy of the two previous WBF algorithms. Therefore, the flipping efficiency of the novel decoding algorithm is increased. The extensive simulations prove that the ERA scheme can obviously improves the performance of the two previous WBF algorithms and a great decoding gain is obtained over an AWGN channel, which achieves an appealing tradeoff between performance and complexity.

bit flipping; extrinsic reliability adjustment; LDPC codes; MAP

TP911.22

A doi:10.3969/j.issn.1001-0548.2015.04.008

2013 ? 10 ? 25；

2015 ? 01 ? 12

國家自然科學基金(61032003, 61271172, 61261021)；中央高?；究蒲袠I務費專項資金(A03008023901004)；高等學校博士學科點專項科研基金(20120185110030，20130185130002)

張高遠(1984 ? )，男，博士生，主要從事信道編譯碼技術方面的研究.