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)，中央高校基本科研业务费专项资金(A03008023901004)和博士点基金(20120185110030, 20130185130002)联合资助课题