The suboptimal behavior of iterative message-passing and linear programming-based algorithms for decoding binary linear codes is attributed to the presence of certain non-codeword states into which the decoding procedures may be trapped. The problem of convergence toward these error-prone structures can be alleviated by either modifying the decoding algorithm, or improving the structural properties of the parity-check matrix specifying the code. The first main aim of the present thesis is to describe a novel integer linear programming-based approach for finding a redundant/non-redundant parity-check equation whose addition to a parity-check matrix can lead to an effective elimination of the stopping sets. Our second major purpose is to improve the error-correcting capability of the adaptive linear programming decoding algorithm using a subroutine for on-the-fly (i.e., in an on-demand basis during run-time) generation of cut-inducing redundant parity-check equations. Finally, we describe a novel branch-and-bound procedure for exhaustively enumerating the elementary trapping sets in an arbitrary given Tanner graph. The knowledge of the of elementary trapping sets of the given graph can be employed for predicting its error-floor behavior, or for custom-tailoring the decoder so that it can get out of a non-codeword state in which it could get trapped. Keywords 1- Linear programming decoding 2- Elementary trapping sets 3- Error-rate floor phenomenon 4- Iterative message-passing decoding 5- Non-integral pseudo-codewords 6- Stopping sets
