LDPC碼加權比特翻轉譯碼算法的低復雜度提前停止準則

張高遠 周 亮 文 紅

?

LDPC碼加權比特翻轉譯碼算法的低復雜度提前停止準則

張高遠*周 亮 文 紅

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

近年來，針對LDPC碼置信傳播(BP)譯碼算法的提前停止準則的研究已經有了很多，但設計適合加權比特翻轉(WBF)譯碼算法的提前停止準則卻研究甚少。依據對WBF算法的全新理解方式，該文提出一種實現簡單、適用性強的WBF算法提前停止準則，它能在譯碼的初始階段檢測絕大多數不可糾錯的幀。仿真結果表明，基于提前停止準則的WBF算法在性能損失可以忽略的條件下，極大地降低迭代次數，在實現復雜度和性能之間達到了很好的折中。

低密度奇偶校驗碼；加權比特翻轉譯碼；可靠度后驗信息符號；提前停止準則

1 引言

目前針對BP算法的提前停止準則已經有了大量研究，例如分別以每次迭代后信息節點的似然比信息的平均幅度和校驗方程滿足的個數的變化情況為出發點，文獻[16]和文獻[18]得出兩種不同的ESC，但設計適用于WBF算法的ESC卻依然是空白。雖然文獻[18]的思路可以推廣到WBF算法當中，但對于不同的碼，此準則要事先通過仿真得到對應的最優化的參數，實現復雜度較大，本文希望能以WBF算法自身的特點為突破口尋求更適合它的ESC。本文首先以文獻[19]中的研究為基礎對WBF[4]和MWBF[5]進行推導，指明如何對IMWBF算法簡化才能得出WBF和MWBF算法。然后針對基于BP類算法得到的WBF算法提出一種ESC。該ESC的顯著特點在于：實現特別簡單，具有很強的可適用性，對部分WBF算法的性能不會帶來任何損失，更重要的是不需要事先對任何參數進行優化，這點不同于文獻[16]和文獻[18]中的準則。仿真結果表明，在基本不降低譯碼性能的條件下，基于ESC的WBF算法的平均迭代次數大大降。本文提出的ESC能及時發現不可糾錯的幀，這對于具有反饋信道，使用自動請求重傳(Automatic Repeat Request, ARQ)機制[20]的通信系統也具有較大的應用價值。

2 基本定義和算法描述

2.1 MWBF和WBF算法的推導

如果對式(3)中第1個等式采用以下近似計算：

從而

將式(7)代入式(2)有

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

2.2 各WBF算法間的內在聯系

3 基于提前停止準則的算法描述和分析

圖1 3種WBF算法的內在聯系

6種狀態分別定義為：

表1譯碼過程分類

譯碼狀態譯碼結果條件： 完全理想狀態正確每次迭代中都為真 不完全理想狀態正確每次迭代中不都為真 非震蕩狀態1成功但錯誤每次迭代中都為真 非震蕩狀態2成功但錯誤每次迭代中不都為真 震蕩狀態1失敗每次迭代中都為真 震蕩狀態2失敗每次迭代中不都為真

表2 WBF算法在碼1條件下各譯碼狀態幀數統計

表3 MWBF算法在碼1條件下各譯碼狀態幀數統計

表4 IMWBF算法在碼1條件下各譯碼狀態幀數統計

4 仿真結果和統計分析

5 結束語

本文以文獻[19]中的分析為基礎詳細闡述了WBF, MWBF和IMWBF算法內在聯系，并提出一種實現簡單適用范圍廣的WBF算法提前停止準則。仿真結果表明，在AWGN信道條件下，提前停止準則在幾乎不降低譯碼性能的條件下，能及時發現不可糾錯的幀，停止此類幀的迭代過程能大大降低了系統實現復雜度和時延。由于提前停止準則在高信噪比時作用減弱，可以考慮引入2種譯碼模式：有提前停止準則和無提前停止準則。中低信噪比時在第1個模式下運行，在較高信噪比時轉入第2個模式即可。但對于塊衰落信道，由于每幀的信噪比可以看做某些信噪比的組合，因此只工作于第1個模式即可。同時由第3節的統計可知，仍有部分幀的譯碼過程處于不完全理想狀態，其內在的理論原因以及設計對此類型幀沒有影響的停止準則問題仍有待進一步研究。

圖3 碼1和碼2條件下，基于提前迭代停止準則的各算法性能比較

圖4 碼1和碼2條件下，各算法平均迭代次數比較

表5碼1條件下，各算法平均迭代次數統計

SNR=2.0 dB SNR=2.5 dB SNR=3.0 dB 算法平均迭代次數算法平均迭代次數算法平均迭代次數 傳統ESC傳統ESC傳統ESC WBF47.024.2WBF35.715.5WBF23.713.8 MWBF71.111.2MWBF47.811.6MWBF24.211.7 IMWBF64.215.6IMWBF37.314.2IMWBF17.112.6

表6碼2條件下，各算法平均迭代次數統計

SNR=3.0 dB SNR=3.5 dB SNR=4.0 dB 算法平均迭代次數算法平均迭代次數算法平均迭代次數 傳統ESC傳統ESC傳統ESC WBF50.741.5WBF48.536.8WBF44.531.1 MWBF49.135.9MWBF46.331.7MWBF40.727.5 IMWBF47.940.4IMWBF44.235.3IMWBF36.629.1

[1] Gallager R G. Low density parity check codes[J]., 1962, IT-8(1): 21-28.

[2] 袁瑞佳, 白寶明. 基于FPGA的LDPC碼編譯碼器聯合設計[J]. 電子與信息學報, 2012, 34(1): 38-44.

Yuan Rui-jia and Bai Bao-ming.FPGA-based joint design of LDPC encoder and decoder[J].&, 2012, 34(1): 38-44.

[3] 朱慶, 吳樂南. 低復雜度校驗節點調度的LDPC串行譯碼算法[J]. 信號處理, 2013, 29(5): 550-556.

Zhu Qing and Wu Le-nan. Low-complexity check-node-based serial scheduling belief propagation for LDPC codes[J].,2013, 29(5): 550-556.

[4] Kou Y, Lin S, and Fossorier M. Low-density parity-check codes based on finite geometries: a rediscovery and new results[J]., 2001, 47(7): 2711-2736.

[5] Zhang J and Fossorier M. A modified weighted bit-flipping decoding of low-density parity-check codes[J]., 2004, 8(3): 165-167.

[6] Jiang M, Zhao C M, Shi Z,.. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes[J]., 2005, 9(9): 814-816.

[7] Wadayama T, Nakamura K, Yagita M,. Gradient descent bit flipping algorithms for decoding LDPC codes[J]., 2010, 58(6): 1610-1614.

[8] Chen T. An efficient bit-flipping decoding algorithm for LDPC codes[C]. Proceedings of International Conference on Cross Strait Quad-Regional Radio Science and Wireless Technology, New Taipei City, 2012: 109-112.

[9] 劉原華, 張美玲. 結構化LDPC碼的改進比特翻轉譯碼算法[J]. 北京郵電大學學報, 2012, 35(4): 116-119.

Liu Yuan-hua and Zhang Mei-ling. Improved bit-flipping method for decoding structured Low-Density Parity-Check codes[J]., 2012, 35(4): 116-119.

[10] 張高遠, 周亮, 蘇偉偉, 等. 基于平均幅度的LDPC碼加權比特翻轉譯碼算法[J]. 電子與信息學報, 2013, 35(11):2572-2578.

Zhang Gao-yuan, Zhou Liang, Su Wei-wei.. Average magnitude based weighted bit-flipping decoding algorithm for LDPC codes[J].&, 2013, 35(11): 2572-2578.

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

[12] Wu X F, Ling C, Jing M.. New insights into weighted bit-flipping decoding[J]., 2009, 57(8): 2177-2181.

[13] 王曉明, 全厚德, 張弛. 基于外信息絕對值信噪比的迭代停止準則[J]. 計算機工程與科學, 2012, 34(6): 178-181.

Wang Xiao-ming, Quan Hou-de, and Zhang Chi. An iterative stoping criterion based on SNR of the absolute value of extrinsic information[J].&, 2012, 34(6): 178-181.

[14] 趙旦峰, 朱鐵林, 劉淵. 基于后驗概率判決的動態迭代停止算法[J]. 吉林大學學報, 2012, 42(3): 766-770.

Zhao Dan-feng, Zhu Tie-lin, and Liu Yuan. Dynamoc iteration stoping algorithm based on APPD[J]., 2012, 42(3): 766-770.

[15] Tao X Y, Zhang Y, Feng D Y,. Layered decoding with a early stoping criterion for LDPC codes[C].Proceedings of International Conference on Information Communication and Management, Hong Kong, China, 2012: 76-80.

[16] Li J, You X H, and Li J. Early stopping for LDPC decoding: convergence of mean magnitude (CMM)[J]., 2006, 10(9): 667-669.

[17] Chen T. An early stopping criterion for LDPC decoding based on average weighted reliability measure[C]. Proceedings of International Conference on Cross Strait Quad-Regional Radio Science and Wireless Technology, New Taipei City, 2012: 123-126.

[18] Shin D, Ha J, Heo K,. An stopping criterion for low-density parity-check codes[J]., 2008, E91-B(4): 1145-1148.

[19] 張高遠, 周亮, 文紅. LDPC碼加權比特翻轉譯碼算法研究[J]. 電子與信息學報, 2014, 36(9): 2093-2097.

Zhang Gao-yuan, Zhou Liang, and Wen Hong. Research on weighted bit-flipping decoding algorithm for LDPC codes[J].&, 2014, 36(9): 2093-2097.

[20] Lin S and Costello D J. Error Control Coding: Fundamentals and Application[M]. Englewood Cliffs, NJ, US, Prentice-Hall, Inc., 1983: 12-13.

[21] 張立軍, 劉明華, 盧萌. 低密度奇偶校驗碼加權大數邏輯譯碼研究[J]. 西安交通大學學報, 2013, 47(4): 35-38.

Zhang Li-jun, Liu Ming-hua, and Lu Meng. A research on weighted majority-logic decoding for LDPCcodes[J]., 2013, 47(4): 35-38.

張高遠： 男，1984年生，博士生，研究方向為信道編譯碼和數字調制解調技術.

周 亮： 男，1961年生，教授，博士生導師，研究方向為信道編譯碼原理與技術、密碼學、信號處理等.

文 紅： 女，1969年生，教授，博士生導師，研究方向為信道編譯碼原理與技術、密碼學、網絡安全通信等.

Low Complexity Early Stopping Criterion for WeightedBit Flipping Decodings of LDPC Codes

Zhang Gao-yuan Zhou Liang Wen Hong

(,,611731,)

Recently, extensive researches have been focused on the early stoping criterion for Belief-Propagation(BP) decoding of LDPC codes. However, there is little study on suitable design of early stopping criterion for Weighted Bit Flipping (WBF) decodings. Based on the whole novel understanding of WBF algorithm, this paper study presents a low complexity and high adaptable stopping criterion which detects most of the undecodable blocks in an early stage of the decoding process. The simulation results show that the proposed method can significatly reduce the average number of required iterations with negligible performance loss, which is able to achieve appealing tradeoff between the complexity and the performance.

Low-Density Parity-Check (LDPC) codes; Weighted Bit Flipping (WBF) decoding; Sign of posteriori reliability information; Early stoping criterion

TN911.22

A

1009-5896(2014)12-2869-07

10.3724/SP.J.1146.2013.02001

張高遠 zhanggaoyuan407@163.com

2013-12-23收到，2014-04-08改回

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