Design Of Low-Density Parity-Check Codes

Error-correcting codes (ECC) enable the communication systems to have a low-power, reliable transmission over noisy channels. Low-Density Parity-Check (LDPC) codes are the best known ECC codes that can achieve data rates very close to Shannon limit. Because of their outstanding performance, low-complexity parallel decoding algorithm and universal application potentials, they have become one of the hottest topics in coding theory today. In general, long random-like LDPC codes perform better than structured LDPC codes of comparable parameters; however, they usually do not have sufficient structure to allow simple encoding. In contrast, structured LDPC codes have encoding advantages over the random-like LDPC codes, especially QC-LDPC (Quasi-Cyclic LDPC) codes. The QC-LDPC codes can be encoded in linear time with shift registers. Since short cycles prevent the iterative decoding from converging and degrade the performance of the LDPC decoders, they must be avoided in code construction. Therefore, designing the structured LDPC codes with large girth and good performance is very important.In this dissertation, several novel methods are explored and investigated for designing LDPC codes. The main results are as follows:1) At relatively short block lengths, for a given block length and a degree distribution, individual LDPC codes in an ensemble show significant variations in performance, especially at high SNRs. Thus, in this dissertation, a search algorithm, based on tree, is proposed to get the codes with biggest average girth. With this method, the best codes can be selected from this ensemble.2) A special class of QC-LDPC codes with high code rates and without cycles of length 4 is proposed. The new codes have an efficient encoding algorithm due to the lower triangular form and simple structure of their parity check matrices. Since the parity check matrix of the QC-LDPC code is composed of blocks of circulant matrices, the required memory for storing it can be significantly reduced, compared with randomly constructed LDPC codes. 3) A graph-theoretic method to construct structured LDPC codes with large girth is proposed. In this method, we design a connection graph with three kinds of special paths to ensure that the Tanner graph of the parity check matrix mapped from the connection graph is without short cycles. The construction method results in several classes of QC-LDPC codes with column weight 3, whose girths are 8 or 12, respectively. Furthermore, by extending this construction method, several classes of structured LDPC codes with column weight 2, whose girths are respectively 16 or 24, can be obtained. The new codes can be encoded with a simple shift register adder accumulator, and the structure of the QC-LDPC codes also reduces the decoder storage and hardware complexity.4) The coding scheme based on LDPC codes is also investigated in this dissertation. Firstly, a class of special product codes called VSPC-LDPC codes is introduced. The corresponding decoding algorithms, circuits and performance analysis are also presented. Secondly, a new structure protection algorithm of LDPC codes is proposed. The new algorithm can reduce the probability of some noise distribution patterns to improve decoding performance and speed.