Design Of LDPC Codes With Capacity-Approaching Random-Like Construction

The forward error correction (FEC) codes are an efficient technique of improving reliability for transmitting and memorizing information-data in communication and computer storage systems. Its supreme goal is to find practical encoding and decoding algorithms that closely approach Shannon's channel capacity limit. The theoretical research shows that Low-Density Parity- Check (LDPC) Codes presented by Galager in his doctor dissertation in 1963 is a class of the FEC codes approaching the limit. Gallager investigated the iterative decoding algorithm with linear computational complexity and innate parallelism and provided a array structure of sparae parity-check matrix, called H-matrix for short in the following. But he didn't investigate the linear encoding algorithm and the algebraically constructing problem of the H-matrix. In several recent years, the linear encoding algorithm of the LDPC codes has also met with success. But the algebraic structure and algebraically constructing method of LDPC codes have still many problems need to be researched. Starting from a point of view such that "maximizing the minimum distance was not the key of getting to capacity; rather, codes should be 'random-like' structure", this dissertation presented several framewok structures of constructing H-matrix. Our major aim was to find the "random-like" LDPC codes which have performance of approaching the limit, encoding algorithm of linear complexity and partial or complete parallel decoding implementation as required by the above supreme goal. Besides, the superiority of the presented LDPC ensembles based on the "random- like" framework structures to a lot of existing structural LDPC ensembles lies in: their performance can be analyzed by many theoretical methods, such as threshold limit theory, minimum distance theory, girth theory and SNR(signal noise ratio)-BER(bit error rate) simulation curves; the best threshold performance is 0.345dB within Shannon capacity limit and the best simulation performance is 1.2dB for the 1/2 rate codes under the 10^-6 BER on the additive white Gaussian noise (AWGN) channel; their maximum column weight is below 10, girth can be reach 24 or more large and minimum distance can achieve 63 or more large.This dissertation mainly investigated two frameworks of H-matrix, such as SPB framework consisting of integer Subscript matrix, Permutation matrix and Bidiagonal matrix and MSPT framework consisting of Masking matrix, sparse Subscript matrix, Permutation matrix and approximately lower Triangular array matrix. Among thses matrices, bidiagonal matrix and approximately lower triangular array matrix have determinate construction and can provide linear encoding algorithm, and both subscript matrices, masking matrix and permutation matrix need to be redesigned. Besides, we still developed the MSPB framework from inproving the SPB framework. These framework structures of H-matrix can thansform the complexity problem of constructing H-matrix into the structural designing problem of simply partitioned sub-matices which have random-like characteristics, diversified functions and properties of easy analysis and design. Throughout this paper we investigate the following problem about these sub-matices: 1) to search after the degree distribution pairs based on these frameworks according to the theory of the optimized threshold determined by the density evolution algorithm. These optimized degree distribution pairs can provide the optimum weight distribution parameters for constructing integer subscript matrix and masking matrix; 2) to formulate the computing expression of the circulant-shift values in the integer subscript matrix, which can eliminate small girth, and this computing expression gives a method of designing the circulant-shift values of permutation matrix in the array H-matrix constructed by the complete permutation matrices; 3) to discover and prove the general construction rule of the basic masking matrix with arbitrary large girth, and present a design method of masking matrix with girth larger than 12; 4) to present two methods for designing the sparse subscript matrix, first is to generate the sparse subscript matrix which we mask the integer subscript matrix by the masking matrix with large girth, and second is to construct the sparse subscript matrix which we separate and rearrange the nature numbers, which is used to replace the non-zero elements in masking matrix, by using algorithm sequence with different common differences; 5) to create two new permutation matrix. They are semi-random structure D permutation matrix based on algorithm sequence and random structure Q permutation matrix based on the " n queens" searching algorithm. The D and Q permutation matrices introduce the random property in permutation structure towards the determinate structural permutation matrix formed by identity matrix, and this random property can obviously improve performance of the LDPC codes.Two main constributions of both theoretical and practical interests in this dissertation are: to discover the general structure characteristics of the basic masking matrix with arbitrary large girth and prove its construction rule so as to solve the algebraically constructing problem of H-matrix with girth larger than 12; to investigate the minimum distance property of the LDPC ensembles based on random-like framework structures and provide the design rule of the array H-matrix with the minimum distance as large as posible.