Integer programming based analysis of decoding failures for LDPC codes

Abstract

Low-density parity-check (LDPC) codes are one of the most e cient and common error correcting codes thanks to their high error performance. Using iterative messagepassing 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 oor 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 oor is observed as the attening of the error performance curve at high SNR values. In this thesis, an e cient, general framework is presented for nding common, devastating error prone structures of any nite 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 oor performance of any LDPC code and increase its performance in the error oor region via carefully modifying its design.