Integer programming based analysis of decoding failures for LDPC codes

Low-density parity-check (LDPC) codes are one of the most efficient and common error correcting codes thanks to their high error performance. Using iterative message-passing decoding or linear programming (LP) decoding with large block sizes, LDPC codes can achieve near-capacity performance while maintaining almost linear encoding and linear decoding complexity (in block length). However, LDPC codes experience the error floor phenomenon in high signal-to-noise ratio (SNR) region due to the presence of small error prone structures in the Tanner graph representation of LDPC codes. The error floor is observed as the flattening of the error performance curve at high SNR values. In this thesis, an efficient, general framework is presented for finding common, devastating error prone structures of any finite length LDPC code. The smallest stopping set for the binary erasure channel (BEC), the smallest fully absorbing set, the smallest absorbing set, and the smallest elementary trapping set for the binary symmetric channel (BSC) are found and then an algorithm for enumerating small error prone structures is proposed. With the knowledge of error prone structures, it is possible to estimate the error floor performance of any LDPC code and increase its performance in the error floor region via carefully modifying its design.