Novel method for counting short cycles of Tanner graphs

被引：1

作者：

Jiao X.-P. ^{[1
,2
]}

Mu J.-J. ^{[1
,2
]}

Zhou L.-H. ^{[1
]}

机构：

[1] School of Computer Science and Technology, Xidian Univ.

[2] State Key Lab. of Integrated Service Networks, Xidian Univ.

来源：

Xi'an Dianzi Keji Daxue Xuebao/Journal of Xidian University | 2010年 / 37卷 / 02期

关键词：

Low-density parity-check (LDPC) codes; Short cycles; Tanner graph; Tree expanding;

D O I：

10.3969/j.issn.1001-2400.2010.02.023

中图分类号：

学科分类号：

摘要：

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.

引用

页码：311 / 314

页数：3

共 11 条

[1]

Gallager R.G., Low-density parity-check codes, IRE Trans Information Theory, 8, 1, pp. 21-28, (1962)

[2]

MacKay D.J.C., Neal R.M., Near Shannon limit performance of low density parity check codes, Electronics Letters, 32, 18, pp. 1645-1646, (1997)

[3]

Richardson T.J., Shokrollahi M.A., Urbanke R., Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans on Information Theory, 47, 2, pp. 619-637, (2001)

[4]

Sun S., Mu J., Wang X., Study and advances of low density parity check codes, Journal of Xidian University, 28, 3, pp. 393-397, (2001)

[5]

Tanner R.M., A recursive approach to low complexity codes, IEEE Trans on Information Theory, 27, 5, pp. 533-547, (1981)

[6]

Halford T.R., Chugg K.M., An algorithm for counting short cycles in bipartite graphs, IEEE Trans on Information Theory, 52, 1, pp. 287-292, (2006)

[7]

Chen R., Huang H., Xiao G., Et al., On the number of shortest cycles of tanner graphs, Journal of Xidian University, 35, 6, pp. 983-985, (2008)

[8]

Fan J., Xiao Y., A method of counting the number of cycles in LDPC codes, The 8th International Conference on Signal Processing (ICSP), pp. 16-20, (2006)

[9]

Mao Y., Banihashemi A.H., A heurist search for good low density parity-check codes at short block lengths, Proc Int Conf Communications, pp. 41-44, (2001)

[10]

Wu X., Zhao C., You X., Et al., Clustering of cycles and construction of LDPC codes, Proc IEEE GLOBECOM, pp. 1102-1105, (2008)

← 1 2 →