Abstract: To remedy the defects of the traditional sparse matrix construction algorithm in Low Density Parity Check (LDPC) code which is hard to be fulfilled or the obtained results are not satisfactory, a new parity-check matrix searching algorithm was proposed based on two-generation tree structure. This algorithm used the data of tree structure, and could more reasonably the skipping relations of the non-zero elements in the rows and lines of the sparse check matrix. Combined with Ant Colony Algorithm (ACA) which has advantages in path seeking, the proposed algorithm is simple and easy to realize. Furthermore, it is easy to apply the algorithm to the irregular code, when importing the outside information to the code.

Key words: Low Density Parity Check (LDPC) code, two-generation tree structure, error-correcting code, Sum-Product Algorithm (SPA), Ant Colony Algorithm (ACA)

摘要： 针对传统的低密度校验(LDPC)码稀疏矩阵构造算法不易实现或可能得到的结果不满足条件的缺陷，给出了一种新颖的基于两代树结构的低密度校验矩阵的构造搜索算法。该算法采用人们熟悉的树型数据结构，可以较为合理地表示稀疏校验矩阵中行与列中非零元素的跳转关系。结果表明，结合蚁群算法在路径搜索方面的优势，采用这种基于两代树的搜索算法，具有算法简单、容易实现的优点。更进一步，如果考虑到非规则码的构造中外信息的引入，可以很容易地将该算法应用在非规则码的构造中。

关键词: 低密度校验码, 两代树结构, 纠错码, 和积算法, 蚁群算法