Designing structured low density parity check codes with large girth

Low-density parity-check (LDPC) codes are excellent error-correcting codes with performance close to the Shannon Capacity. However, cycles, especially short cycles, are harmful to LDPC codes.; The thesis is concerned with minimizing the impact of cycles in LDPC codes and their associated Tanner graphs. This is explored in three main dimensions: design of large girth codes, partitioning the original Tanner graph into sub-trees to achieve fast decoding, and reducing a Tanner graph to pseudo-trees to facilitate the design of low-complexity encoders.; Girth is a crucial parameter for LDPC codes since large girth leads to more efficient iterative decoding and better codes. We introduce two types of novel structured regular LDPC codes---partition-and-shift LDPC (PS-LDPC) codes and turbo-structured LDPC (TS-LDPC) codes. They are both constructed from their associated Tanner graphs and can be designed to have arbitrary large girth g. Their representation is parsimonious. They are described by a small set of parameters, the shifts, which simplifies their implementation. They can be designed with any desired column weight j ≥ 2 and flexible code rates. We derive detailed theorems and algorithms to construct systematically PS-LDPC codes and TS-LDPC codes with arbitrarily specified girth g and arbitrarily column weight j and row weight k. For PS-LDPC codes, we present an algorithm that efficiently constructs large PS-LDPC codes with large girth iteratively from smaller codes with small girth. For TS-LDPC codes, we present an algorithm to design their interleavers to prevent short cycles. We study the BER performance of these codes by simulation and compare them with random codes free of 4-cycles. Our simulation results show that, in the high SNR region, PS-LDPC codes and TS-LDPC codes with large girth outperform random codes, alleviating the error floor phenomenon. We also analyzed the girth and distance properties of PS-LDPC codes. We show that, for PS-LDPC codes, g is proportional to log(j -1)(k-1) n, where j and k are the column weight and row weight respectively.; The thesis also introduces a new fast decoding algorithm, the split-merge decoding. This algorithm splits the original Tanner graph of the LDPC code into sub-trees. (Abstract shortened by UMI.)...