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

New algorithm of detecting cycles in bipartite graphs of LDPC codes

摘要:

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

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.