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

朱庆; 吴乐南; 杨永标; 李捷; 徐石明

doi:10.11959/j.issn.1000-436x.2017083

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- Tanner图中基于矩阵运算的短环分布高效计算方法
- Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation
- 通信学报 2017年38卷第4期页码：76-85
- 作者机构：
  
  1. 国电南瑞科技股份有限公司，江苏南京 211106
  2. 东南大学信息科学与工程学院，江苏南京 210096
- 作者简介：
  
  [ "朱庆（1981-），男，江苏扬州人，博士，国电南瑞科技股份有限公司用电技术分公司工程师，主要研究方向为信道编码、可见光通信、电力通信、智能电网。" ]
  [ "吴乐南（1952-），男，安徽枞阳人，东南大学教授、博士生导师，主要研究方向为调制技术、多媒体信号处理、数据压缩。" ]
  [ "杨永标（1978-），男，江苏南通人，国电南瑞科技股份有限公司用电技术分公司副总工，主要研究方向为电力系统自动化、智能电网。" ]
  [ "李捷（1973-），男，江苏南京人，国电南瑞科技股份有限公司用电技术分公司工程师，主要研究方向为电力通信、智能电网。" ]
  [ "徐石明（1967-），男，江苏张家港人，国电南瑞科技股份有限公司用电技术分公司高级工程师，主要研究方向为电力通信、电力系统自动化、智能电网。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61233007)
- DOI：10.11959/j.issn.1000-436x.2017083
  中图分类号： TN911.2
- 网络出版日期：2017-04，
  
  纸质出版日期：2017-04-25
- 稿件说明：
移动端阅览
朱庆, 吴乐南, 杨永标, 等. Tanner图中基于矩阵运算的短环分布高效计算方法[J]. 通信学报, 2017,38(4):76-85.

Qing ZHU, Le-nan WU, Yong-biao YANG, et al. Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation[J]. Journal on communications, 2017, 38(4): 76-85.
朱庆, 吴乐南, 杨永标, 等. Tanner图中基于矩阵运算的短环分布高效计算方法[J]. 通信学报, 2017,38(4):76-85. DOI： 10.11959/j.issn.1000-436x.2017083.

Qing ZHU, Le-nan WU, Yong-biao YANG, et al. Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation[J]. Journal on communications, 2017, 38(4): 76-85. DOI： 10.11959/j.issn.1000-436x.2017083.

摘要

Tanner图中的环分布影响着低密度校验码（LDPC

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

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.

关键词

Keywords

references

HUANG Q , DIAO Q J , LIN S , et al . Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets [J ] . IEEE Transactions on Information Theory , 2012 , 58 ( 5 ): 2648 - 2671 .

OVINNIKOV A A , VITYAZEV V V , et al . Fast estimation of error floor effect for irregular low-density parity-check codes [C ] // 2015 International Siberian Conference on Control and Communications . 2015 : 1 - 4 .

赵明 , 张晓林 . 基于改进2-D+GRS码的QC-LDPC码高效构造 [J ] . 通信学报 , 2015 , 36 ( 2 ): 193 - 199 .

ZHAO M , ZHANG X L . Novel construction of QC-LDPC codes with modified 2-D GRS codes [J ] . Journal on Communications , 2015 , 36 ( 2 ): 193 - 199 .

ASLAM C A , GUAN Y L , CAI K . Improving the belief-propagation convergence of irregular LDPC codes using column-weight based scheduling [J ] . IEEE Communications Letters , 2015 , 19 ( 8 ): 1283 - 1286 .

马克祥 , 孙吉成 , 王萌 , 等 . 用于 LDPC 码快速译码的改进多比特翻转算法 [J ] . 通信学报 , 2014 , 35 ( 2 ): 118 - 124 .

MA K X , SUN J C , WANG M , et al . Improved multi-bits flipping algorithm for high-speed LDPC decoding [J ] . Journal on Communications , 2014 , 35 ( 2 ): 118 - 124 .

RAVEENDRAN N , SRINIVASA S G . An analysis into the loopy belief propagation algorithm over short cycles [C ] // 2014 IEEE International Conference on Communications . 2014 : 2009 - 2014 .

JIAO X P , MU J J . Probabilistic analysis of cycles in random Tanner graphs [C ] // 2013 IEEE International Conference on Signal Processing,Communications and Computing . 2013 : 1 - 5 .

MORITZ B , PETER V . Breaking cycles with dummy bits:improved rate-compatible LDPC codes with short block lengths [C ] // The 9th International ITG Conference on Systems,Communication and Coding . 2013 : 1 - 6 .

CHAO F G , REN H , CAO N . Finding a shortest cycle in a subspace of the cycle space of a graph [J ] . Applied Mathematics and Computation , 2015 , 268 : 393 - 398 .

NITHIN R , GARANI S S . A modified sum-product algorithm over graphs with isolated short cycles [C ] // IEEE International Symposium on Information Theory . 2014 : 2619 - 2623 .

FOUCAUD F , KRIVELEVICH M , PERARNAU G . Large subgraphs without short cycles [J ] . SIAM Journal on Discrete Mathematics , 2015 , 29 ( 1 ): 65 - 78 .

CHEN R , HUANG H , XIAO G . Relation between parity-check matrices and cycles of associated Tanner graphs [J ] . IEEE Communication Letters , 2007 , 11 ( 8 ): 674 - 676 .

CHANG Y C , FU H L . The number of 6-cycles in a graph [J ] . Bulletin of the Institute of Combinatorics and its Applications , 2003 , 39 : 27 - 30 .

FLUM J , GROHE M . The parameterized complexity of counting problems [J ] . SIAM Journal on Computing , 2004 , 33 ( 4 ): 892 - 922 .

JOHNSON D B . Find all the elementary circuits of a directed graph [J ] . Journal SIAM , 1975 , 4 : 77 - 84 .

BAX E T . Algorithms to count paths and cycles [J ] . Information Processing Letters , 1994 , 52 ( 5 ): 249 - 252 .

SCHOTT R , STAPLES G S . On the complexity of cycle enumeration using Zeons [C ] // Applied Geometric Algebras in Computer Science and Engineering . 2010 : 1 - 22 .

STAPLES G S . A new adjacency matrix for finite graphs [J ] . Advances in Applied Clifford Algebras , 2008 , 18 ( 3 ): 979 - 991 .

STORM C . Some properties of graphs determined by edge zeta functions [J ] . Linear Algebra and its Applications , 2011 , 434 ( 5 ): 1285 - 1294 .

FAN J , XIAO J . A method of counting the number of cycles in LDPC codes [C ] // The 8th International Conference on Signal Processing . 2006 : 2183 - 2186 .

HALFORD T R , CHUGG K M . An algorithm for counting short cycles in bipartite graphs [J ] . IEEE Transactions on Information Theory , 2006 , 52 ( 1 ): 287 - 292 .

KADI A , NAJAH S , MRABTI M , et al . Improving performance of the min sum algorithm for LDPC codes [C ] // The Mediterranean Conference on Information ＆ Communication Technologies . 2015 : 381 - 388 .

KARIMI M , BANIASHEMI A H . On the girth of quasi cyclic protograph LDPC codes [C ] // IEEE International Symposium on Information Theory . 2012 : 3078 - 3082 .

KARIMI M , BANIASHEMI A H . Efficient algorithm for finding dominant trapping sets of LDPC codes [J ] . IEEE Transactions on Information Theory , 2012 , 58 ( 5 ): 6942 - 6958 .

KARIMI M , BANIASHEMI A H . Counting short cycles of quasi cyclic protograph LDPC codes [J ] . IEEE Communication Letters , 2012 , 16 ( 3 ): 400 - 403 .

KARIMI M , BANIASHEMI A H . On the girth of quasi cyclic protograph LDPC codes [J ] . IEEE Transactions on Information Theory , 2013 , 59 ( 7 ): 4542 - 4552 .

SUN C , XU H , FENG D , et al . (3,L) quasi-cyclic LDPC codes_Simplified exhaustive search and designs [C ] // The 9th International Symposium on Turbo Codes ＆ Iterative Information Processing . 2016 : 271 - 275 .

HOSUNG P , SEOKBEOM H , SEON N J . Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles [J ] . IEEE Transactions on Information Theory , 2013 , 59 ( 7 ): 4598 - 4614 .

HASHEMI Y , BANIHASHEMI A H . On characterization and efficient exhaustive search of elementary trapping sets of variable-regular LDPC codes [J ] . IEEE Communication Letters , 2015 , 19 ( 3 ): 323 - 326 .

KARIMI M , BANIASHEMI A H . On characterization of elementary trapping sets of variable-regular LDPC codes [J ] . IEEE Transactions on Information Theory , 2014 , 60 ( 9 ): 5188 - 5203 .

浏览量

864

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据