Tanner图中基于矩阵运算的短环分布高效计算方法

doi:10.11959/j.issn.1000-436x.2017083

Abstract

Abstract:

Loop distribution of Tanner graph affects the BER performance of low-density parity-check codes(LDPC) decoding.To count short cycles in the Tanner graph efficiently,a side by side recursion algorithm based on matrix computation was proposed.Firstly,5 basic graph structures were defined to realize recursive calculate in the implementation process.Compared with previous works,the algorithm provided many methods for counting the same length of cycles.The same result confirmed the correctness of the algorithm.The new algorithm could not only calculate the total number of cycles,but also gave the number each edge participating in fixed-length cycles.Its complexity was proportional to the product of D and square of N,where D was the average degree of variable nodes,and N denoted the code length.For LDPC codes,D was far less than N.For most of the LDPC codes,the calculation for numbers of cycle-length g、g+2、g+4 was only several seconds.

Key words: Tanner graph, low-density parity-check codes (LDPC), short cycle, girth

CLC Number:

TN911.2

Qing ZHU,Le-nan WU,Yong-biao YANG,Jie LI,Shi-ming XU. Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation[J]. Journal on Communications, 2017, 38(4): 76-85.

Figures/Tables 14

References 30

[1]	HUANG Q , DIAO Q J , LIN S ,et al. Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets[J]. IEEE Transactions on Information Theory, 2012,58(5): 2648-2671.
[2]	OVINNIKOV A A , VITYAZEV V V , et al . Fast estimation of error floor effect for irregular low-density parity-check codes[C]// 2015 International Siberian Conference on Control and Communications. 2015: 1-4.
[3]	赵明, 张晓林 . 基于改进2-D+GRS码的QC-LDPC码高效构造[J]. 通信学报, 2015,36(2): 193-199.
	ZHAO M , ZHANG X L . Novel construction of QC-LDPC codes with modified 2-D GRS codes[J]. Journal on Communications, 2015,36(2): 193-199.
[4]	ASLAM C A , GUAN Y L , CAI K . Improving the belief-propagation convergence of irregular LDPC codes using column-weight based scheduling[J]. IEEE Communications Letters, 2015,19(8): 1283-1286.
[5]	马克祥, 孙吉成, 王萌 ,等. 用于 LDPC 码快速译码的改进多比特翻转算法[J]. 通信学报, 2014,35(2): 118-124.
	MA K X , SUN J C , WANG M ,et al. Improved multi-bits flipping algorithm for high-speed LDPC decoding[J]. Journal on Communications, 2014,35(2): 118-124.
[6]	RAVEENDRAN N , SRINIVASA S G . An analysis into the loopy belief propagation algorithm over short cycles[C]// 2014 IEEE International Conference on Communications. 2014: 2009-2014.
[7]	JIAO X P , MU J J . Probabilistic analysis of cycles in random Tanner graphs[C]// 2013 IEEE International Conference on Signal Processing,Communications and Computing. 2013: 1-5.
[8]	MORITZ B , PETER V . Breaking cycles with dummy bits:improved rate-compatible LDPC codes with short block lengths[C]// The 9th International ITG Conference on Systems,Communication and Coding. 2013: 1-6.
[9]	CHAO F G , REN H , CAO N . Finding a shortest cycle in a subspace of the cycle space of a graph[J]. Applied Mathematics and Computation, 2015,268: 393-398.
[10]	NITHIN R , GARANI S S . A modified sum-product algorithm over graphs with isolated short cycles[C]// IEEE International Symposium on Information Theory. 2014: 2619-2623.
[11]	FOUCAUD F , KRIVELEVICH M , PERARNAU G . Large subgraphs without short cycles[J]. SIAM Journal on Discrete Mathematics, 2015,29(1): 65-78.
[12]	CHEN R , HUANG H , XIAO G . Relation between parity-check matrices and cycles of associated Tanner graphs[J]. IEEE Communication Letters, 2007,11(8): 674-676.
[13]	CHANG Y C , FU H L . The number of 6-cycles in a graph[J]. Bulletin of the Institute of Combinatorics and its Applications, 2003,39: 27-30.
[14]	FLUM J , GROHE M . The parameterized complexity of counting problems[J]. SIAM Journal on Computing, 2004,33(4): 892-922.
[15]	JOHNSON D B . Find all the elementary circuits of a directed graph[J]. Journal SIAM, 1975,4: 77-84.
[16]	BAX E T . Algorithms to count paths and cycles[J]. Information Processing Letters, 1994,52(5): 249-252.
[17]	SCHOTT R , STAPLES G S . On the complexity of cycle enumeration using Zeons[C]// Applied Geometric Algebras in Computer Science and Engineering. 2010: 1-22.
[18]	STAPLES G S . A new adjacency matrix for finite graphs[J]. Advances in Applied Clifford Algebras, 2008,18(3): 979-991.
[19]	STORM C . Some properties of graphs determined by edge zeta functions[J]. Linear Algebra and its Applications, 2011,434(5): 1285-1294.
[20]	FAN J , XIAO J . A method of counting the number of cycles in LDPC codes[C]// The 8th International Conference on Signal Processing. 2006: 2183-2186.
[21]	HALFORD T R , CHUGG K M . An algorithm for counting short cycles in bipartite graphs[J]. IEEE Transactions on Information Theory, 2006,52(1): 287-292.
[22]	KADI A , NAJAH S , MRABTI M ,et al. Improving performance of the min sum algorithm for LDPC codes[C]// The Mediterranean Conference on Information ＆ Communication Technologies. 2015: 381-388.
[23]	KARIMI M , BANIASHEMI A H . On the girth of quasi cyclic protograph LDPC codes[C]// IEEE International Symposium on Information Theory. 2012: 3078-3082.
[24]	KARIMI M , BANIASHEMI A H . Efficient algorithm for finding dominant trapping sets of LDPC codes[J]. IEEE Transactions on Information Theory, 2012,58(5): 6942-6958.
[25]	KARIMI M , BANIASHEMI A H . Counting short cycles of quasi cyclic protograph LDPC codes[J]. IEEE Communication Letters, 2012,16(3): 400-403.
[26]	KARIMI M , BANIASHEMI A H . On the girth of quasi cyclic protograph LDPC codes[J]. IEEE Transactions on Information Theory, 2013,59(7): 4542-4552.
[27]	SUN C , XU H , FENG D ,et al. (3,L) quasi-cyclic LDPC codes_Simplified exhaustive search and designs[C]// The 9th International Symposium on Turbo Codes ＆ Iterative Information Processing. 2016: 271-275.
[28]	HOSUNG P , SEOKBEOM H , SEON N J . Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles[J]. IEEE Transactions on Information Theory, 2013,59(7): 4598-4614.
[29]	HASHEMI Y , BANIHASHEMI A H . On characterization and efficient exhaustive search of elementary trapping sets of variable-regular LDPC codes[J]. IEEE Communication Letters, 2015,19(3): 323-326.
[30]	KARIMI M , BANIASHEMI A H . On characterization of elementary trapping sets of variable-regular LDPC codes[J]. IEEE Transactions on Information Theory, 2014,60(9): 5188-5203.

Metrics

Recommended 0

No Suggested Reading articles found!

码型			环数		运行时间/s
码型	环长为4	环长为6	环长为8	环长为10	Lollipop	本文方法
GA128_256	0	164	1 000	7 217	0.17	0.019
GA256_512	0	153	1 104	8 627	0.51	0.070
GA512_1024	0	168	1 151	8 877	2.60	0.250
GA1000_2000	0	182	1 175	9 774	160.00	0.750
GA2000_4000	0	171	1 263	9 934	120.00	2.600
GA4000_8000	0	143	1 190	10 042	1 038.00	9.000
PG813_1057	0	190 496 768	137 300 545 536	11 258 644 733 952	8.10	1.200
PG191_273	0	3 168 256	534 643 200	109 922 641 920	0.50	0.060
EG1023	0	157 465 616	106 517 624 400	81 959 438 474 496	10.00	1.300
QC288_576	48	504	6 756	—	0.87	0.090
PEGir252_504	0	13 244	420 609	13 567 791	0.70	0.080
2256_4512	0	752	5 640	81 968	155.00	4.200

Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 30

Related Articles 3

Metrics

Recommended 0

[1]	Jian JIAO,Zhi-hua YANG,Shu-shi GU,Jie ZHOU,Qin-yu ZHANG. Novel joint encoding/decoding algorithms of LT codes based on random permute egde-growth and stopping set [J]. Journal on Communications, 2013, 34(2): 31-39.
[2]	Guo-hua ZHANG,Rong SUN,Xin-mei WANG. Explicit construction of girth-eight QC-LDPC codes and its application in CRT method [J]. Journal on Communications, 2012, 33(3): 171-176.
[3]	Jing LEI,Jian-hui WANG,Chao-jing TANG. Quasi-cyclic extension based on PEG algorithm for construction of LDPC codes [J]. Journal on Communications, 2008, 29(9): 103-110.