一种Tanner图短环计数新方法

doi:10.3969/j.issn.1001-2400.2010.02.023

Abstract

Abstract:

Short cycles have an important influence on iterative decoding for low-density parity-check (LDPC) codes. By using tree expanding of Tanner graphs and the analysis of the influence of invalid cycles and duplicate cycles, a formula for counting short cycles of LDPC codes is derived. With the derived formula, an algorithm for counting short cycles of Tanner graphs based on tree expanding is proposed. The proposed algorithm can count short cycles with arbitrary lengths, and thus overcomes the disadvantage of existing algorithms that count short cycles with given lengths. Numerical results of counting short cycles of some typical LDPC codes show the correctness of the proposed algorithm.

Key words: low-density parity-check (LDPC) codes, Tanner graph, short cycles, tree expanding

JIAO Xiao-peng;MU Jian-jun;ZHOU Li-hua. Novel method for counting short cycles of Tanner graphs[J].J4, 2010, 37(2): 311-314.

References

［1］ Gallager R G. Low-density Parity-check Codes［J］. IRE Trans Information Theory, 1962, 8(1): 21-28.
［2］ MacKay D J C, Neal R M. Near Shannon Limit Performance of Low Density Parity Check Codes［J］. Electronics Letters, 1997, 32(18): 1645-1646.
［3］ Richardson T J, Shokrollahi M A, Urbanke R. Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes［J］. IEEE Trans on Information Theory, 2001, 47(2): 619-637.
［4］孙韶辉, 慕建君, 王新梅. 低密度校验码研究及其新进展［J］. 西安电子科技大学学报, 2001, 28(3): 393-397.
Sun Shaohui, Mu Jianjun, Wang Xinmei. Study and Advances of Low Density Parity Check Codes［J］. Journal of Xidian University, 2001, 28(3): 393-397.
［5］ Tanner R M. A Recursive Approach to Low Complexity Codes［J］. IEEE Trans on Information Theory, 1981, 27(5): 533-547.
［6］ Halford T R, Chugg K M. An Algorithm for Counting Short Cycles in Bipartite Graphs［J］. IEEE Trans on Information Theory, 2006, 52(1): 287-292.
［7］陈汝伟, 黄华伟, 肖国镇, 等. Tanner图中最短圈的计数［J］. 西安电子科技大学学报, 2008, 35(6): 983-985.
Chen Ruwei, Huang Huawei, Xiao Guozhen, et al. On the Number of Shortest Cycles of Tanner Graphs［J］. Journal of Xidian University, 2008, 35(6): 983-985.
［8］ Fan J, Xiao Y. A Method of Counting the Number of Cycles in LDPC Codes［C］//The 8th International Conference on Signal Processing (ICSP). Guilin: IEEE, 2006: 16-20.
［9］ Mao Y, Banihashemi A H. A Heurist Search for Good Low Density Parity-check Codes At Short Block Lengths［C］//Proc Int Conf Communications. Helsinki: IEEE, 2001: 41-44.
［10］ Wu Xiaofu, Zhao Chunming, You Xiaohu, et al. Clustering of Cycles and Construction of LDPC Codes［C］//Proc IEEE GLOBECOM. New Orleans: IEEE, 2008: 1102-1105.
［11］ MacKay D J C. Encyclopedia of Sparse Graph Codes［DB/OL］. ［2008-09-04］. http://www.inference.phy.cam. ac.uk./mackay/codes/data.html.

[1]	WANG Xiangxu,CHE Shuling,JI Yuhui. Effective construction method for locally repairable codes [J]. Journal of Xidian University, 2019, 46(3): 26-31.
[2]	XU Hengzhou;SUN Cheng;BAI Baoming. Nonbinary LDPC codes constructed based on cyclic difference families [J]. Journal of Xidian University, 2017, 44(1): 6-11+28.
[3]	GUO Junjun;MU Jianjun. Selection algorithm of finite alphabet iterative decoders for LDPC codes [J]. J4, 2013, 40(6): 111-115.
[4]	ZHANG Guohua；WANG Xinmei. On the existence of a class of QC-LDPC codes with girth at least six [J]. J4, 2011, 38(3): 136-139+149.
[5]	CHEN Chao;BAI Bao-ming;WANG Xin-mei. A class of nonbinary quasi-cyclic LDPC codes with a low-density generator matrix [J]. J4, 2010, 37(3): 412-416.
[6]	CHEN Ru-wei1;2;HUANG Hua-wei3;DU Xiao-ni4;DING Yong2;XIAO Guo-zhen1. On the number of shortest cycles of Tanner graphs [J]. J4, 2008, 35(6): 983-985.

Novel method for counting short cycles of Tanner graphs

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 6

Metrics

Comments

Recommended 10