Iterative decoding of LDPC and GLDPC codes over a binary symmetric channel

For decades since Claude Shannon published his landmark paper [1] and introduced information theory into electrical engineering, scientists have been on a quest to find a coding scheme that would approach the theoretical limit imposed by a communication channel. Designs of good coding schemes have been focused primarily on finding codes that can be decoded with optimal and feasible decoding algorithms. This approach, which was widely accepted by coding theorists, was revised with the introduction of turbo codes and low-density parity-check (LDPC) codes. These two novel approaches were proved to approach the infamous channel capacity using a suboptimum iterative decoding. Consequently, suboptimum iterative decoding techniques have been receiving more attention. Most of the work on iterative decoding of LDPC codes has been dedicated to LDPC codes and their performance on the AWGN channel. On the other hand iterative decoding of LDPC codes on the binary symmetric channel (BSC) was somewhat neglected. With the ever increasing transmission rates in modern optical communications, which are modelled with BSC, there is a need for a very fast and very powerful decoder that will support it.; This research investigates iterative decoding of LDPC and generalized LDPC (GLDPC) codes on BSC. For the decoding of LDPC codes, a new bit flipping (BF) algorithm named the probabilistic bit flipping algorithm was proposed. Convergence of the algorithm is investigated using a standard assumption of cycle free code that enables derivation of recursive equations. The analysis showed that the proposed algorithm improves the threshold over the existing algorithms for some classes of LDPC codes. The algorithm is also analyzed in the presence of cycles in the associated codegraph and proved to be more resilient than existing algorithms. In addition, the proposed algorithm was proved to achieve considerable gain in decoding time in the waterfall part of the performance curve. A new GLDPC coding scheme was proposed that utilizes Reed-Solomon (RS) and Bose-Chaudhuri-Hochquenghem (BCH) codes as component codes. An iterative algorithm is proposed and analyzed in a manner similar to that for LDPC codes. The convergence analysis showed that codes approach the channel capacity within 0.4dB for very high rates. A finite length analysis of proposed GLDPC codes over Q-ary erasure channel (QEC) was conducted. The analysis recognized codegraph structures that determined the performance of the code so that the average bit and block error probabilities over the ensemble of GLDPC codes could be obtained. Finally, the finite length analysis results were extended to BSC as a very tight lower bound of the expected performance over the ensemble.