Recent Publications
S. K. Chilappagari, M. G. Stepanov, M. Chertkov and B. Vasic, "Analysis of Error Floors of LDPC Codes under LP Decoding over the BSC", submitted to ISIT 2009
We consider Linear Programming (LP) decoding of a fixed LowDensity ParityCheck (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudocodeword which is not a codeword. We propose an efficient algorithm termed the Instanton Search Algorithm (ISA) which, given a random input, generates a set of flips called the BSCinstanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upperbounded by twice the number of flips in the input. Repeated sufficient number of times, the ISA outcomes the number of unique instantons of different sizes. We use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semianalytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.
S. K. Chilappagari, M. Chertkov, M. G. Stepanov and B. Vasic, "Instantonbased Techniques for Analysis and Reduction of Error Floors of LDPC Codes", to appear in IEEE JSAC on Capacity Approaching Codes
We describe a family of instantonbased optimization methods developed recently for the analysis of the error floors of lowdensity paritycheck (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of suboptimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.
S. K. Chilappagari, M. Chertkov and B. Vasic, "Provably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC", submitted to IEEE Transcations on Information Theory, September 2008
We consider Linear Programming (LP) decoding of a fixed LowDensity ParityCheck (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudocodeword which is not a codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which, given a random input, generates a set of flips called the BSCinstanton. We prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upperbounded by twice the number of flips in the input. Repeated sufficient number of times, the ISA outcomes the number of unique instantons of different sizes.
S. K. Chilappagari, D. V. Nguyen, B. Vasic and M. W. Marcellin, "On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes", under second round of review, IEEE Transactions on Information Theory
The relation between the girth and the guaranteed error correction capability of $\gamma$leftregular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least $3 \gamma/4$ is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to leftregular and rightuniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the codelength) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. It is also shown that the bound on the required expansion cannot be improved when the left degree is even. A lower bound on the size of variable node sets which have the required expansion is established.
S. K. Chilappagari, D. V. Nguyen, B. Vasic and M. W. Marcellin, "Error Correction Capability of ColumnWeightThree LDPC Codes: Part II", submitted to IEEE Transactions on Information Theory
The relation between the girth and the error correction capability of columnweightthree LDPC codes is investigated. Specifically, it is shown that the Gallager A algorithm can correct $g/21$ errors in $g/2$ iterations on a Tanner graph of girth $g \geq 10$.
S. K. Chilappagari and B. Vasic, "Error Correction Capability of COlumnWeightThree LDPC Codes", to appear in IEEE Transactions on Information Theory, May 2009
In this paper, the error correction capability of columnweightthree LDPC codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to $k \geq 5$ errors is to avoid cycles of length up to $2k$ in its Tanner graph. As a consequence of this result, it is shown that given any $\alpha>0, \exists N $ such that $\forall n>N$, no code in the ensemble of columnweightthree codes can correct all $\alpha n$ or fewer errors. The results are extended to the bit flipping algorithms.

