通信学报2017，Vol.38Issue(4)：76-85,10.DOI:10.11959/j.issn.1000-436x.2017083
Tanner图中基于矩阵运算的短环分布高效计算方法
Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation
摘要
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.关键词
Tanner图/低密度校验码/短环/最短环长Key words
Tanner graph/low-density parity-check codes (LDPC)/short cycle/girth分类
信息技术与安全科学引用本文复制引用
朱庆,吴乐南,杨永标,李捷,徐石明..Tanner图中基于矩阵运算的短环分布高效计算方法[J].通信学报,2017,38(4):76-85,10.基金项目
国家自然科学基金资助项目(No.61233007)The National Natural Science Foundation of China (No.61233007) （No.61233007）
