一种有效的LDPC码伪码字搜索算法

doi:10.3969/j.issn.1001-2400.2018.06.027

西安电子科技大学学报 ›› 2018, Vol. 45 ›› Issue (6): 162-166.doi: 10.3969/j.issn.1001-2400.2018.06.027

• 研究论文 • 上一篇

一种有效的LDPC码伪码字搜索算法

郭军军1;白硕栋1;慕建君2;荆心1;肖锋1

(1. 西安工业大学计算机学院, 陕西西安 710021；
2. 西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2018-04-01 出版日期:2018-12-20 发布日期:2018-12-20
作者简介:郭军军(1977-)，男，副教授，E-mail: guojunjun@xatu.edu.cn
基金资助:
国家自然科学基金资助项目(61572392); 陕西省重点研发计划资助项目(2018GY-0232); 西安工业大学校长基金资助项目(XAGDXJJ16016)

Efficient pseudo-codeword search algorithm for LDPC codes

GUO Junjun1;BAI Shuodong1;MU Jianjun2;JING Xin1;XIAO Feng1

(1. School of Computer Science and Engineering, Xi'an Technological Univ., Xi'an 710021, China;
2. School of Computer Science and Technology, Xidian Univ., Xi'an 710071, China)

Received:2018-04-01 Online:2018-12-20 Published:2018-12-20

摘要/Abstract

摘要： 为了获得影响低密度奇偶校验码线性规划译码性能的伪码字，通过深入分析有害的Tanner子图中变量节点位置与线性规划译码器输入分量位置的对应关系，提出了二元对称信道下低密度奇偶校验码的一种有效的低重量伪码字搜索算法．通过对基于交替方向乘子法的线性规划译码器输入向量叠加偏置噪声，经过有限次迭代搜索后可快速收敛到低重量伪码字．仿真结果表明，与现有伪码字搜索算法相比，所提出的方法能够更准确地找到大量中短码长规则和非规则低密度奇偶校验码的低重量伪码字．

关键词: 低密度奇偶校验码, 错误平台, 伪码字, 线性规划译码

Abstract: In order to obtain the pseudo-codewords which can decrease the linear programming (LP) decoding performance of low-density parity-check(LDPC) codes, an efficient algorithm for searching low-weight pseudo-codewords of LDPC codes is proposed on the binary symmetric channel by making a detailed analysis of the corresponding relationship between variable nodes in the harmful Tanner subgraphs and input components of LP decoders. The proposed algorithm can rapidly converge to low-weight pseudo-codewords of LDPC codes with finite iterations by biasing noises for the input vectors of the LP decoder based on the alternating direction method of multipliers. Simulation results show that the proposed approach can accurately find many low-weight pseudo-codewords of regular and irregular LDPC codes with a short or middle length compared with the existing pseudo-codeword search method.

Key words: low-density parity-check codes, error floor, pseudo-codewords, linear programming decoding

中图分类号:

TN911. 22

郭军军, 白硕栋, 慕建君, 荆心, 肖锋. 一种有效的LDPC码伪码字搜索算法[J]. 西安电子科技大学学报, 2018, 45(6): 162-166.

GUO Junjun, BAI Shuodong, MU Jianjun, JING Xin, XIAO Feng. Efficient pseudo-codeword search algorithm for LDPC codes[J]. Journal of Xidian University, 2018, 45(6): 162-166.

参考文献［12］

［1］	GALLAGER R G. Low-density Parity-check Codes［J］. IRE Transactions on Information Theory, 1962, 8(1): 21-28.<br />
［2］	MCGREGOR A, MILENKOVIC O. On the Hardness of Approximating Stopping and Trapping Sets［J］. IEEE Transactions on Information Theory, 2010, 56(4): 1640-1650.<br />
［3］	BLAKE I, LIN S. On Short Cycle Enumeration in Biregular Bipartite Graphs［J］. IEEE Transactions on Information Theory, 2017, 64(10): 6526-6535.<br />
［4］	GUO J J, MU J, JIAO X, et al. Finding Small Fundamental Instantons of LDPC Codes by Path Extension［J］. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2014, E97-A(4): 1001-1004.<br />
［5］	HASHEMI Y, BANIHASHEMI A H. Characterization and Efficient Exhaustive Search Algorithm for Elementary Trapping Sets of Irregular LDPC Codes［C］／／Proceedings of the 2017 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2017: 1192-1196.<br />
［6］	KAKAKHAIL S, REYNAL S, DECLERCQ D, et al. An Efficient Pseudo-codeword Search Algorithm for Belief Propagation Decoding of LDPC Codes［C］／／Proceedings of the 2009 International Conference on Ultra Modern Telecommunications and Workshops. Washington: IEEE Computer Society, 2009: 1-5.<br />
［7］	CHILAPPAGARI S K, CHERTKOV M, VASIC B. An Efficient Instanton Search Algorithm for LP Decoding of LDPC Codes over the BSC［J］. IEEE Transactions on Information Theory, 2011, 57(7): 4417-4426.<br />
［8］	LIU X, DRAPER S C. Instanton Search Algorithm for the ADMM Penalized Decoder［C］／／Proceedings of the 2014 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2014: 696-700.<br />
［9］	WEI H, BANIHASHEMI A H. An Iterative Check Polytope Projection Algorithm for ADMM-based LP Decoding of LDPC Codes［J］. IEEE Communications Letters, 2018, 22(1): 29-32.<br />
［10］	WANG B, MU J, JIAO X, et al Improved Penalty Functions of ADMM Penalized Decoder for LDPC Codes［J］. IEEE Communications Letters, 2017, 21(2): 234-237.<br />
［11］	TANNER R M, SRIDHARA D, FUJA T. A Class of Group-structured LDPC Codes［C］／／Proceedings of the 2001 6th International Symposium on Communication Theory and Applications. Piscataway: IEEE, 2001: 365-370.<br />
［12］	焦晓鹏, 慕建君, 周利华. 一种Tanner图短环计数新方法［J］. 西安电子科技大学学报, 2010, 37(2): 311-314.<br />
	JIAO Xiaopeng, MU Jianjun, ZHOU Lihua. Novel Method for Counting Short Cycles of Tanner Graphs［J］. Journal of Xidian University, 2010, 37(2): 311-314.<br />
	<div>
	<br />
	</div>

[1]	张娅妹,周林,陈辰,陈启望,贺玉成. 瑞利衰落信道中SC-LDPC码滑窗译码算法[J]. 西安电子科技大学学报, 2020, 47(6): 78-83.
[2]	张娅妹,周林,陈辰,郭荣新,贺玉成. 窗口可变的空间耦合LDPC码滑窗译码算法[J]. 西安电子科技大学学报, 2020, 47(3): 128-134.
[3]	孙岳,李蓓蕾,梁彩虹,李颖. 块衰落信道下串联多链空间耦合LDPC码设计[J]. 西安电子科技大学学报, 2019, 46(2): 1-5.
[4]	张昭基;李颖. 适用于突发删除信道的非对称空间耦合LDPC码[J]. 西安电子科技大学学报, 2017, 44(5): 1-6.
[5]	张旋;慕建君;焦晓鹏. 一种MLC闪存存储系统的比特翻转译码算法[J]. 西安电子科技大学学报, 2017, 44(5): 75-80+146.
[6]	任计林;车书玲;郑征. 规则LDPC码在GPU上的加速译码[J]. 西安电子科技大学学报, 2017, 44(3): 25-30.
[7]	范亚楠;王丽冲;姚秀娟;孟新. 交叠的分层置信度传播LDPC译码算法[J]. 西安电子科技大学学报, 2017, 44(2): 88-94.
[8]	徐恒舟;孙成;白宝明. 循环差族构造的多元LDPC码[J]. 西安电子科技大学学报, 2017, 44(1): 6-11+28.
[9]	刘洋;李颖;李京娥. 译码转发中继信道下双层延长LDPC码设计[J]. J4, 2014, 41(5): 13-17.
[10]	马克祥;刘毅;胡建华;孙吉成;张海林. LDPC码的一种低复杂度译码算法及关键电路设计[J]. J4, 2013, 40(6): 6-12.
[11]	马卓;杜栓义;王新梅. BICM系统中一种低复杂度的迭代解映射算法[J]. J4, 2011, 38(2): 42-46.
[12]	胡家义;王文博. 基于加权图的准循环低密度奇偶校验码构造算法 [J]. J4, 2008, 35(5): 938-941.

一种有效的LDPC码伪码字搜索算法

Efficient pseudo-codeword search algorithm for LDPC codes

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献［12］

相关文章 12

Metrics

本文评价

推荐阅读 10

一种有效的LDPC码伪码字搜索算法

Efficient pseudo-codeword search algorithm for LDPC codes

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［12］

相关文章 12

Metrics

本文评价

推荐阅读 10

参考文献［12］