Research On LDPC Codes And Applications

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.