通信学报 ›› 2017, Vol. 38 ›› Issue (4): 76-85.doi: 10.11959/j.issn.1000-436x.2017083

• 学术论文 • 上一篇    下一篇

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

朱庆1,吴乐南2,杨永标1,李捷1,徐石明1   

  1. 1 国电南瑞科技股份有限公司,江苏 南京 211106
    2 东南大学信息科学与工程学院,江苏 南京 210096
  • 修回日期:2017-03-02 出版日期:2017-04-01 发布日期:2017-07-20
  • 作者简介:朱庆(1981-),男,江苏扬州人,博士,国电南瑞科技股份有限公司用电技术分公司工程师,主要研究方向为信道编码、可见光通信、电力通信、智能电网。|吴乐南(1952-),男,安徽枞阳人,东南大学教授、博士生导师,主要研究方向为调制技术、多媒体信号处理、数据压缩。|杨永标(1978-),男,江苏南通人,国电南瑞科技股份有限公司用电技术分公司副总工,主要研究方向为电力系统自动化、智能电网。|李捷(1973-),男,江苏南京人,国电南瑞科技股份有限公司用电技术分公司工程师,主要研究方向为电力通信、智能电网。|徐石明(1967-),男,江苏张家港人,国电南瑞科技股份有限公司用电技术分公司高级工程师,主要研究方向为电力通信、电力系统自动化、智能电网。
  • 基金资助:
    国家自然科学基金资助项目(61233007)

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

Qing ZHU1,Le-nan WU2,Yong-biao YANG1,Jie LI1,Shi-ming XU1   

  1. 1 NARI Technology Development Co.,Ltd.,Nanjing 211106,China
    2 School of Information Science and Engineering,Southeast University,Nanjing 210096,China
  • Revised:2017-03-02 Online:2017-04-01 Published:2017-07-20
  • Supported by:
    The National Natural Science Foundation of China(61233007)

摘要:

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

关键词: Tanner图, 低密度校验码, 短环, 最短环长

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

中图分类号: 

No Suggested Reading articles found!