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

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

作　　者：朱庆[1] 吴乐南[2] 杨永标[1] 李捷[1] 徐石明[1] ZHU Qing WU Le-nan YANG Yong-biao LI Jie XU Shi-ming(NARI Technology Development Co., Ltd., Nanjing 211106, China School of Information Science and Engineering, Southeast University, Nanjing 210096, China)

机构地区：[1]国电南瑞科技股份有限公司,江苏南京211106 [2]东南大学信息科学与工程学院,江苏南京210096

出　　处：《通信学报》2017年第4期76-85,共10页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61233007)~~

摘　　要：Tanner图中的环分布影响着低密度校验码(LDPC,low-density parity-check code)译码算法的误码率性能,为快速计算出Tanner图中短环的数目,提出一种逐边递推基于矩阵运算的算法。首先定义5种基本图结构,算法在实施过程中可实现结构间的递推。与之前的研究工作相比,该算法对于同一环长提供多种方法进行计算,得到相同的计算结果,进一步证实算法的正确性。新算法不仅能计算出总的环数,还能给出每一条边参与的环数。该算法将时间复杂度从正比于码长N的3次方降为正比于码长的平方与变量节点平均度数D的乘积(D<<N)。对于大多数的LDPC码,计算环长为g、g+2、g+4的环数需要的时间仅为数秒。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图 低密度校验码 短环 最短环长 

分 类 号：TN911.2[电子电信—通信与信息系统]