Abstract
In the first part of this dissertation, we apply generalized Kronecker product recursively to construct low-density parity-check (LDPC) codes with arbitrarily large girth. The parity-check matrices of these codes are block matrices consisting of circulant permutation matrices, thus may benefit from efficient encoding. It turns out that the LU(m, q) codes proposed in the literature is a special case of this construction for prime q. Connectivity of Tanner graphs of these codes are investigated. The performance of codes derived from LU(m, q) codes are demonstrated. The second part, the error correction capability of a greedy bit-flipping (BF) decoding algorithm for LDPC codes is studied by introducing variable node adjacency graphs which are derived from Tanner graphs of LDPC codes. For codes with column weight lambda and girth g=8, it can be shown that error patterns of weight less than or equal to lambda-1 can be corrected, while Gallager's BF algorithm can correct lambda/2 errors. This result implies that the greedy BF algorithm can decode up to the random error-correcting capability over binary symmetric channels for girth 8 codes with minimum distance 2*lambda.