一种Tanner图短环计数新方法

doi:10.3969/j.issn.1001-2400.2010.02.023

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

一种Tanner图短环计数新方法

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

(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-peng^1,2;MU Jian-jun^1,2;ZHOU Li-hua¹

(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

摘要/Abstract

摘要：

短环是影响低密度校验码迭代译码性能的重要因素．利用树结构展开的思想，通过分析无效短环和重复短环对计数结果的影响，得出了低密度校验码的一个短环计数公式．利用这一公式，提出了一种基于树结构展开的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

焦晓鹏;慕建君;周利华. 一种Tanner图短环计数新方法[J]. J4, 2010, 37(2): 311-314.

JIAO Xiao-peng;MU Jian-jun;ZHOU Li-hua. Novel method for counting short cycles of Tanner graphs[J]. J4, 2010, 37(2): 311-314.

参考文献

［1］ Gallager R G. Low-density Parity-check Codes［J］. IRE Trans Information Theory, 1962, 8(1): 21-28.
［2］ MacKay D J C, Neal R M. Near Shannon Limit Performance of Low Density Parity Check Codes［J］. Electronics Letters, 1997, 32(18): 1645-1646.
［3］ Richardson T J, Shokrollahi M A, Urbanke R. Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes［J］. IEEE Trans on Information Theory, 2001, 47(2): 619-637.
［4］孙韶辉, 慕建君, 王新梅. 低密度校验码研究及其新进展［J］. 西安电子科技大学学报, 2001, 28(3): 393-397.
Sun Shaohui, Mu Jianjun, Wang Xinmei. Study and Advances of Low Density Parity Check Codes［J］. Journal of Xidian University, 2001, 28(3): 393-397.
［5］ Tanner R M. A Recursive Approach to Low Complexity Codes［J］. IEEE Trans on Information Theory, 1981, 27(5): 533-547.
［6］ Halford T R, Chugg K M. An Algorithm for Counting Short Cycles in Bipartite Graphs［J］. IEEE Trans on Information Theory, 2006, 52(1): 287-292.
［7］陈汝伟, 黄华伟, 肖国镇, 等. Tanner图中最短圈的计数［J］. 西安电子科技大学学报, 2008, 35(6): 983-985.
Chen Ruwei, Huang Huawei, Xiao Guozhen, et al. On the Number of Shortest Cycles of Tanner Graphs［J］. Journal of Xidian University, 2008, 35(6): 983-985.
［8］ Fan J, Xiao Y. A Method of Counting the Number of Cycles in LDPC Codes［C］//The 8th International Conference on Signal Processing (ICSP). Guilin: IEEE, 2006: 16-20.
［9］ Mao Y, Banihashemi A H. A Heurist Search for Good Low Density Parity-check Codes At Short Block Lengths［C］//Proc Int Conf Communications. Helsinki: IEEE, 2001: 41-44.
［10］ Wu Xiaofu, Zhao Chunming, You Xiaohu, et al. Clustering of Cycles and Construction of LDPC Codes［C］//Proc IEEE GLOBECOM. New Orleans: IEEE, 2008: 1102-1105.
［11］ MacKay D J C. Encyclopedia of Sparse Graph Codes［DB/OL］. ［2008-09-04］. http://www.inference.phy.cam. ac.uk./mackay/codes/data.html.

[1]	李华安, 王汶振, 徐恒舟, 陈超, 白宝明. 类Raptor多速率QC-LDPC码的一种优化方法[J]. 西安电子科技大学学报, 2024, 51(6): 52-59.
[2]	胡继文, 郑慧娟, 童胜, 白宝明, 徐达人, 王仲立. 低复杂度LDPC码信息瓶颈量化译码器设计[J]. 西安电子科技大学学报, 2022, 49(5): 76-83.
[3]	李华安,白宝明,徐恒舟,陈超. 一种类Raptor多速率QC-LDPC码的代数构造方法[J]. 西安电子科技大学学报, 2022, 49(1): 134-141.
[4]	周沈洋,白宝明,任兆丰,朱敏,李秉豪,唐瑞波. 面向高吞吐传输的级联极化码BP List译码算法[J]. 西安电子科技大学学报, 2020, 47(6): 58-65.
[5]	王祥旭,车书玲,纪玉晖. 一种有效的局部可修复码的构造方法[J]. 西安电子科技大学学报, 2019, 46(3): 26-31.
[6]	王彪;慕建君;焦晓鹏;王钟斐. LDPC码ADMM惩罚译码的早停止方法[J]. 西安电子科技大学学报, 2018, 45(5): 43-49.
[7]	孙成;徐恒舟;冯丹;白宝明;张玉龙. 可分解的可分组设计构造的LDPC码[J]. 西安电子科技大学学报, 2017, 44(3): 31-35+42.
[8]	徐娟;姚如贵;李路;高凡琪. 优化稀疏LU分解的LDPC编码算法研究 [J]. J4, 2015, 42(2): 127-132.
[9]	郭军军;慕建君. 一种LDPC码有限字母表迭代译码器选择算法[J]. J4, 2013, 40(6): 111-115.
[10]	陈超;白宝明;王新梅. 一类具有低密度生成矩阵的非二元准循环LDPC码[J]. J4, 2010, 37(3): 412-416.
[11]	陈霖;冯大政. 一种快速的渐进边增长算法[J]. J4, 2009, 36(3): 406-409.
[12]	陈汝伟1;2;黄华伟3;杜小妮4;丁勇2;肖国镇1. Tanner 图中最短圈的计数 [J]. J4, 2008, 35(6): 983-985.
[13]	王单;童胜;李颖;王新梅. LDPC码的快速收敛译码算法[J]. J4, 2005, 32(1): 103-107.
[14]	童胜;王鹏;王单;王新梅. LDPC码量化和积译码的高效实现[J]. J4, 2004, 31(5): 709-713.
[15]	贺玉成;孙韶辉;慕建君;王新梅. 快速低密度校验码迭代译码量化算法[J]. J4, 2002, 29(2): 338-343.

一种Tanner图短环计数新方法

Novel method for counting short cycles of Tanner graphs

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0