二部图的矩阵与环结构研究及其在LDPC编码中的应用

This project is concerned with the structured LDPC codes and their Tanner graphs (i.e., bipartite graphs). We will explore some new methods to enumerate and count the cycles of several types of structured LDPC codes, and then reveal their cycle structure properties. On this basis, cycle systems of the structured bipartite graphs are investigated, and the girth distribution problems of quasi-cyclic (QC) LDPC codes are addressed. We will establish novel research methods and theoretical tools, which can provide a solid theoretical foundation for the applications of bipartite graphs and their matrices in LDPC coding. The research will include the following topics: novel cycle enumeration and counting methods of three types of structured LDPC codes, i.e., QC codes, cyclic codes, and combinational designs based codes; cycle systems for Tanner graphs of QC-LDPC codes; the girth distribution of Tanner’s QC-LDPC codes.

本项目针对不同类型的结构化LDPC码探寻环枚举和计数新原理，揭示其Tanner图（二部图）中的环结构特性，并以此研究结构化二部图的圈/环分解系统和准循环LDPC码的围长分布问题，从而创建一些全新的研究方法和理论工具，为二部图及其矩阵在LDPC编码中的应用打下坚实的理论基础。主要内容包括：三类结构化LDPC码（准循环类、循环类、组合设计类）的环枚举与计数新方法；准循环LDPC码Tanner图的圈/环分解系统；解决Tanner准循环LDPC码的围长分布。

LDPC码是新一代移动通信中的一种实用信道编码技术，它不仅具有优异的译码性能，而且还具有简单的编译码算法和易于硬件实现的结构。但是还有许多技术难关需要解决，例如，有限长LDPC码对应的Tanner图（二部图）中不可避免地存在长度较短的环，它影响迭代译码算法的性能。本项目针对不同类型的结构化LDPC码探寻环枚举和计数新原理，揭示其Tanner图中的环结构特性，并以此研究结构化二部图的圈/环分解系统和准循环LDPC码的围长分布问题，从而创建一些全新的研究方法和理论工具，为二部图及其矩阵在LDPC编码中的应用打下坚实的理论基础。主要研究内容和重要成果包括下列两个方面：第一，主要研究了循环矩阵及其位置集合的同构理论，分析了循环矩阵的环与非零元素位置之间的关系，给出了环存在的充分必要条件，提出了一种检验长度为4的环存在的有效算法，并以此构造了不含长度为4的环的低秩循环矩阵；分析围长与图的度分布、图的谱之间的关系，为构造与优化设计大围长的LDPC码奠定理论基础，并创建一些全新的研究方法和理论工具。第二，研究了Tanner准循环LDPC码的环结构，提出了环的型的定义及等价性，将Tanner准循环LDPC码的不同长度下环划分为若干个等价类；将长度小于12的环存在性等价于素数域中本原单位根的多项式方程解的存在性；基于辗转相除法在素数域上求解这些多项式方程，并归纳所得到的候选素数，得到了Tanner准循环LDPC码的围长，从而确定了两类Tanner准循环LDPC码的围长分布；本项目研究并完全解决了Tanner(3,19)-规则和(5,13)-规则准循环LDPC码的围长分布问题。本项目主要发表12篇学术论文，其中SCI检索论文9篇，EI检索论文2篇，会议论文1篇，申请了国家发明专利1项，培养河南省教育厅学术技术带头人（访问学者）1人，培养博士1人。