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

Tanner 图中最短圈的计数


  1. (1. 西安电子科技大学 综合业务网理论及关键技术国家重点实验室,陕西 西安 710071;
    2. 桂林电子科技大学 数学与计算机科学学院,广西 桂林 541004;
    3. 华南农业大学 信息学院,广东 广州 510642;
    4. 西北师范大学 数学与信息科学学院,甘肃 兰州 730070)
  • 收稿日期:2007-10-14 修回日期:1900-01-01 出版日期:2008-12-20 发布日期:2008-12-20
  • 通讯作者: 陈汝伟

On the number of shortest cycles of Tanner graphs

CHEN Ru-wei1,2;HUANG Hua-wei3;DU Xiao-ni4;DING Yong2;XIAO Guo-zhen1

  1. (1. State Key Lab. of Integrated Service Networks, Xidian Univ., Xi’an 710071, China;
    2. School of Math. and Computational Sci., Guilin Univ. of Electronic Tech, Guilin 541004,China;
    3. College of Inform. South China Agricultural Univ., Guangzhou 510642,China;
    4. College of Math. and Inform. Sci., Northwest Normal Univ., Lanzhou 730070,China)
  • Received:2007-10-14 Revised:1900-01-01 Online:2008-12-20 Published:2008-12-20
  • Contact: CHEN Ru-wei

摘要: 应用Chen 等提出的研究线性分组码校验矩阵与Tanner图中圈的关系的方法,证明了围长为2k的校验矩阵中满足一定条件的k行组合与其Tanner图中最短圈的一一对应关系.由这一结论,对Chen等提出的计算Tanner图中最短圈数量的算法加以改进,减少一个运算步骤,而仍然得到同样准确的结果.

关键词: 低密度校验(LDPC)码, Tanner图, 最短圈, 2k-圈矩阵

Abstract: By the method for investigating the relation between parity-check matrixes and cycles of associated Tanner graphs proposed by Chen et al., the one-to-one correspondence between k-row-combinations satisfying a certain condition in a parity-check matrix of grith k and shortest cycles in the associated Tanner graph is proved. As a consequence, the algorithm for counting the shortest cycels of Tanner graphs proposed by Chen et al. is improved. The improved algorithm is as accurate as the original one while omitting one of the main steps.

Key words: low-density parity-check (LDPC) code, Tanner graph, shortest cycle, 2k-cycle-matrix


  • TN911.21