J4 ›› 2010, Vol. 37 ›› Issue (2): 311-314.doi: 10.3969/j.issn.1001-2400.2010.02.023

• 研究论文 • 上一篇    下一篇

一种Tanner图短环计数新方法

焦晓鹏1,2;慕建君1,2;周利华1
  

  1. (1. 西安电子科技大学 计算机学院,陕西 西安  710071;
    2. 西安电子科技大学 综合业务网理论及关键技术国家重点实验室,陕西 西安  710071)
  • 收稿日期:2008-12-19 出版日期:2010-04-20 发布日期:2010-06-03
  • 通讯作者: 焦晓鹏
  • 作者简介:焦晓鹏(1984-),男,西安电子科技大学博士研究生,E-mail: jiaozi1216@126.com.
  • 基金资助:

    综合业务网理论及关键技术国家重点实验室开放基金资助项目(ISN10-04);国家自然科学基金资助项目(60573034)

Novel method for counting short cycles of Tanner graphs

JIAO Xiao-peng1,2;MU Jian-jun1,2;ZHOU Li-hua1   

  1. (1. School of Computer Science and Technology, Xidian Univ., Xi'an  710071, China;
    2. State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an  710071, China)
  • Received:2008-12-19 Online:2010-04-20 Published:2010-06-03
  • Contact: JIAO Xiao-peng

摘要:

短环是影响低密度校验码迭代译码性能的重要因素.利用树结构展开的思想,通过分析无效短环和重复短环对计数结果的影响,得出了低密度校验码的一个短环计数公式.利用这一公式,提出了一种基于树结构展开的Tanner图短环计数算法,可对任意给定长度的短环进行计数,从而克服了现有短环计数算法仅能对特定长度短环计数的缺点.对一些典型低密度校验码的短环数量统计结果表明这种算法的正确性.

关键词: 低密度校验码, Tanner图, 短环, 树结构展开

Abstract:

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.

Key words: low-density parity-check (LDPC) codes, Tanner graph, short cycles, tree expanding