【作者】 刘文明；

【导师】 朱光喜；

【作者基本信息】 华中科技大学 ， 信息与通信工程， 2006， 博士

【摘要】 随着移动通信系统高速率业务需求的不断增加,前向纠错码和信号处理技术越来越受到人们的关注。Gallager在1962年提出的低密度奇偶校验码(Low-Density Parity-Check Codes,LDPC)是一类可以用稀疏矩阵或二分图定义的线性分组码。它具有非常好的特点:性能逼近香农限,描述方便,易于进行理论分析,译码简单且可并行操作,适合硬件实现。近年来LDPC码以其优异的性能、简洁的形式以及良好的应用前景吸引广大研究人员进行了深入研究。LDPC码具有较强的纠错能力,但是其编码比较复杂,一直以来没有出现好的解析构造方法。Gallager只提供了一类伪随机LDPC码,好的LDPC码,尤其是长码,都要通过计算机搜索得到。由于缺乏循环和准循环特性,这种通过计算机搜索得到的码,编码十分复杂,不利于实际应用。因此,研究编码器的设计方法对于LDPC码的应用具有重要的现实意义。本论文正是在国家“十五”863计划重大专项课题“新一代蜂窝移动通信系统无线传输链路技术研究(FuTURE)”(2001AA123014)和国家自然科学基金重大项目“未来移动通信系统基础理论与技术研究”(60496310)的资助下,开展了LDPC码编码技术的研究。本文开始介绍了LDPC码的起源、当前发展概况,然后详细介绍了LDPC码的定义以及其Tanner图表示,在规则码的基础上给出了非规则码的定义以及设计方法。最后,介绍了Gallager编码方法以及Mackay编码设计方法。本文接着介绍了LDPC码通用的一类译码方法―消息传递算法(Message Passing Algorithms),在算法的每一轮迭代过程中,关于各个节点的置信信息需要在变量节点和校验节点之间传递。首先简单介绍了BP算法,在此基础上研究了LDPC码的和积译码算法,以及对数域的和积译码算法,并给出了高斯信道下的具体算法实现。最后,探讨了一种简化的对数域和积译码算法。好的LDPC码,尤其是长码,都要通过计算机搜索得到。这种通过计算机搜索得到的长码,编码十分复杂,不利于实际应用,因此设计确定性的编码方法具有重要的现实意义。关于这一研究,首先研究了线性同余序列构造规则LDPC码的设计方法,在此基础上,提出了一种二次同余序列构造LDPC码的设计方法。但上述二种方法的编码比较复杂,不利于实用。针对此缺点,提出了一种改进的准规则LDPC编码方法,采用双对角矩阵以及线性同余序列构造校验矩阵,有效地解决了LDPC码编码复杂度高的问题,使其编码具有线性复杂度。与已有的一些确定性编码方法相比,该方法具有两大优势:第一,实现简单,通过迭代生成校验比特,编码具有线性复杂度;第二,节省存储空间,编、译码端只需要存储少量参数,就可以恢复出校验矩阵;第三,与随机构造的编码方法相比该编码器具有更好的纠错性能。为了进一步研究LDPC码的构造方法并考虑其实用性,本文提出了基于循环差集(Cyclic Difference Sets)的构造方法。首先介绍了区组设计的基本概念以及循环差集的定义和循环差集的构造,然后研究了一种循环差集的码字构造方法。与该方法相对应,提出了一种基于完备距离循环排列的LDPC编码方法。采用上述方法构造的编码器,其校验矩阵由于进行列分割失去了循环性,不能利用循环移位寄存器进行编码,编码复杂。为了降低编码复杂度,提出了一种循环差集的准循环编码方式。与已有的一些循环差集设计方法相比,该设计具有两大优势:第一,实现简单,可以通过移位寄存器实现编码,编码具有线性复杂度;第二,节省存储空间,编、译码端只需要存储少量参数,就可以恢复出校验矩阵进行编译码。更多还原

【Abstract】 With the increasing demand for high-speed services in mobile communication systems, forward error correction (FEC) codes and signal processing techniques are receiving much attention. Low-density parity-check codes (LDPC) first discovered by Gallager in 1962 are a class of linear block error-correcting codes that can be defined by the very sparse parity-check matrix or the bipartite graph. They have very attractive properties: error performance approaching Shannon limits, easy description and implementation, convenient theoretical analysis and research, easily decoded in complete parallel ways and suitable for hardware implementation. In resent years, LDPC codes have gained increasingly consideration of researchers with their excellent error performance, simple description and very good application foreground. LDPC codes have become another focus following turbo codes in error-correcting coding fields.There were not good algebraic methods for constructing LDPC codes though they have good performance. Good LDPC codes, especially long codes, often are obtained by searching in computer. As lacking the circlular or quasi-circular character of the circular LDPC codes, these search-based codes have very complex encoding structure. Therefore, it is very important to find good encoding methods. This motivates us to investigate the encoding methods for LDPC codes. Our work is supported by the National High Technology Research and Development Program of China under Grant No. 2001AA123014 and National Science Foundation of China under Grant No. 603905405.We firstly introduce the present situation of the development about LDPC codes, the definition of the regular LDPC codes and their Tanner graphs. Based on the description, the definition of the irregular LDPC codes was presented. In the end, the Gallager encoder and Mackay encoder were introduced.We then show a general decoding method of LDPC codes, called message passing algorithm, which means that the belief message of each node was propagated between the check nodes and bit nodes. The sum-product algorithm (SPA), its new version in log domain and its application in Gaussian channel model were introduced based on the introduction of the BP algorithm. In the end, a simplified decoding algorithm in log domain was presented.Good LDPC codes, especially long codes, often are obtained by searching in computer. These search-based codes have very complex encoding structure and do not facilitate hardware implementation. Therefore, it is very important to find good deterministic encoding methods. Based on the description, we introduce maximal-length linear congruential sequences generated using a simple recursion to generate the bipartite graph of LDPC codes. A method using quadratic congruential sequences to design regular LDPC code is proposed. The main advantage of this method is that the structure of the encoder can be generated using a determined recursion, rather than having to store the encoder structure graph in memory. However their encoding complexity was very large and disadvantageous in physical application. To slove the problem, we put forward a kind of semi-regular LDPC codes using dual-diagonal matrix and a regular matrix generated with simple recursion, which make their encoding complexity be linear with the coding lengths. Compared with the existing deterministic LDPC codes, our design has two main advantages: Firstly, it can be easily encoded with linear complexy by using iterative algorithm; secondly, the structure allow for small storage requirements, as well as the check matrix being obtained via small number of parameters; thirdly, simulation results show that these codes provide better performance than a constrained pseudorandom construction.We lastly introduced the concept of block design, definition of cyclic difference sets and the construction of cyclic difference sets. A new method to construct LDPC codes based on cyclic difference sets of combinatorics was introduced. With similarity, a new method to construct LDPC codes based on cyclic permutation of perfect distance of combinatorics was proposed. But their encoding complexity was complicated because column splitting make them lose cyclicality. In order to reduce the complexity of encoding, a new method to construct semi-cyclic LDPC codes based on cyclic difference sets was proposed. Compared with the existing LDPC codes based on cyclic difference sets, our design has two main advantages: Firstly, it can be easily encoded with linear complexy by using cyclic register; secondly, the structure allow for small storage requirements, as well as for encoding and decoding via fast and simple circuits.更多还原