張高遠(yuǎn) 周 亮 文 紅

?

LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法的低復(fù)雜度提前停止準(zhǔn)則

張高遠(yuǎn)*周 亮 文 紅

(電子科技大學(xué)通信與抗干擾技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 成都 611731)

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

低密度奇偶校驗(yàn)碼；加權(quán)比特翻轉(zhuǎn)譯碼；可靠度后驗(yàn)信息符號(hào)；提前停止準(zhǔn)則

1 引言

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

2 基本定義和算法描述

2.1 MWBF和WBF算法的推導(dǎo)

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

從而

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

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

2.2 各WBF算法間的內(nèi)在聯(lián)系

3 基于提前停止準(zhǔn)則的算法描述和分析

圖1 3種WBF算法的內(nèi)在聯(lián)系

6種狀態(tài)分別定義為：

表1譯碼過程分類

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

表2 WBF算法在碼1條件下各譯碼狀態(tài)幀數(shù)統(tǒng)計(jì)

表3 MWBF算法在碼1條件下各譯碼狀態(tài)幀數(shù)統(tǒng)計(jì)

表4 IMWBF算法在碼1條件下各譯碼狀態(tài)幀數(shù)統(tǒng)計(jì)

4 仿真結(jié)果和統(tǒng)計(jì)分析

5 結(jié)束語

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

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

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

表5碼1條件下，各算法平均迭代次數(shù)統(tǒng)計(jì)

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

表6碼2條件下，各算法平均迭代次數(shù)統(tǒng)計(jì)

SNR=3.0 dB SNR=3.5 dB SNR=4.0 dB 算法平均迭代次數(shù)算法平均迭代次數(shù)算法平均迭代次數(shù) 傳統(tǒng)ESC傳統(tǒng)ESC傳統(tǒng)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碼編譯碼器聯(lián)合設(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 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] 朱慶, 吳樂南. 低復(fù)雜度校驗(yàn)節(jié)點(diǎn)調(diào)度的LDPC串行譯碼算法[J]. 信號(hào)處理, 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] 劉原華, 張美玲. 結(jié)構(gòu)化LDPC碼的改進(jìn)比特翻轉(zhuǎn)譯碼算法[J]. 北京郵電大學(xué)學(xué)報(bào), 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] 張高遠(yuǎn), 周亮, 蘇偉偉, 等. 基于平均幅度的LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法[J]. 電子與信息學(xué)報(bào), 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] 王曉明, 全厚德, 張弛. 基于外信息絕對值信噪比的迭代停止準(zhǔn)則[J]. 計(jì)算機(jī)工程與科學(xué), 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] 趙旦峰, 朱鐵林, 劉淵. 基于后驗(yàn)概率判決的動(dòng)態(tài)迭代停止算法[J]. 吉林大學(xué)學(xué)報(bào), 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] 張高遠(yuǎn), 周亮, 文紅. LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法研究[J]. 電子與信息學(xué)報(bào), 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] 張立軍, 劉明華, 盧萌. 低密度奇偶校驗(yàn)碼加權(quán)大數(shù)邏輯譯碼研究[J]. 西安交通大學(xué)學(xué)報(bào), 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.

張高遠(yuǎn)： 男，1984年生，博士生，研究方向?yàn)樾诺谰幾g碼和數(shù)字調(diào)制解調(diào)技術(shù).

周 亮： 男，1961年生，教授，博士生導(dǎo)師，研究方向?yàn)樾诺谰幾g碼原理與技術(shù)、密碼學(xué)、信號(hào)處理等.

文 紅： 女，1969年生，教授，博士生導(dǎo)師，研究方向?yàn)樾诺谰幾g碼原理與技術(shù)、密碼學(xué)、網(wǎng)絡(luò)安全通信等.

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

張高遠(yuǎn) zhanggaoyuan407@163.com

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

國家自然科學(xué)基金(61032003, 61271172, 61261021)，中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(A03008023901004)和博士點(diǎn)基金(20120185110030, 20130185130002)聯(lián)合資助課題