一种LDPC码双向图环路检测新算法

李博, 王钢, 杨洪娟, 魏民

哈尔滨工业大学通信技术研究所



摘要:

对一种计算通信网节点间全部路由的逻辑代数化算法进行改进,提出一种LDPC码双向图环路检测新算法.算法遵循逻辑代数运算规则,由LDPC码校验矩阵构造双向图的邻接矩阵,并对邻接矩阵中行与行之间进行整合与删除运算以及部分元素的修正运算,对于码长为n,信息位为k的LDPC码只需(n-1)×k次整合和删除运算及k次元素修正运算,就能得到该双向图中所有的环路.通过算例详细说明算法的计算过程,并验证其正确性和合理性.

关键词:  LDPC码  双向图  环路  逻辑代数

DOI：10.11918/j.issn.0367-6234.2010.07.010

分类号:TN915.01

基金项目:



New algorithm of detecting cycles in bipartite graphs of LDPC codes

LI Bo, WANG Gang, YANG Hong-juan, WEI Min

Communication Research Center,Harbin Institute of Technology,Harbin 150001,China

Abstract:

In this paper,a logic algebraic algorithm in computing entire routes among the nodes of a communication network is improved,and a new algorithm of detecting cycles in bipartite graphs of LDPC codes is proposed.The algorithm obeys the logic algebraic calculation rules.Through integrating and deleting rows of relative matrix and correcting some elements of the matrix,the new algorithm can detect all the cycles in the bipartite graphs of LDPC codes.When the code length is n and information bits number is k,the integrating and deleting algorithm needs(n-1)×k times and the correcting algorithm needs k times.The validity and rationality of the algorithm are demonstrated in detail.The calculation course of the algorithm is shown by an example and the correctness is validated.

Key words:  LDPC codes  bipartite graphs  cycles  logic algebra