Recent Publications (click here for a Complete List of 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", accepted for presentation at ISIT 2009
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 semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.
S. K. Chilappagari, B. Vasic and M. W. Marcellin, "Guaranteed Error Correction Capability of Codes on Graphs", in Proc. ITA 2009.
A summary of recent results relating the column weight and girth of the Tanner graph to the guaranteed error correction capability is provided. The intuition behind expander based arguments and their potential to derive new results for column-weight-three codes is provided.
S. K. Chilappagari, M. Chertkov, M. G. Stepanov and B. Vasic, "Instanton-based 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 instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (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 sub-optimal decoders. 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.
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 design an efficient algorithm termed the Instanton Search Algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton. 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 upper-bounded 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
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 left-regular and right-uniform generalized LDPC codes.
S. K. Chilappagari, D. V. Nguyen, B. Vasic and M. W. Marcellin, "Error Correction Capability of Column-Weight-Three LDPC Codes: Part II", submitted to IEEE Transactions on Information Theory
The relation between the girth and the error correction capability of column-weight-three LDPC codes is investigated. Specifically, it is shown that the Gallager A algorithm can correct $g/2-1$ errors in $g/2$ iterations on a Tanner graph of girth $g \geq 10$.
S. K. Chilappagari and B. Vasic, "Error Correction Capability of COlumn-Weight-Three LDPC Codes", to appear in IEEE Transactions on Information Theory, May 2009
In this paper, the error correction capability of column-weight-three 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 column-weight-three codes can correct all $\alpha n$ or fewer errors. The results are extended to the bit flipping algorithms.
M. Ivkovic, S. K. Chilappagari and Bane Vasic, "Eliminating Trapping Sets in Low-Density Parity Check Codes by using Tanner Graph Covers", IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3763-3768, Aug. 2008.
We discuss error floor asympotics and present a method for improving the performance of low-density parity check (LDPC) codes in the high SNR (error floor) region. The method is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate.
S. K. Chilappagari, S. Sankaranarayanan and B. Vasic, "Error Floors of LDPC Codes on the Binary Symmetric Channel", in Proc. ICC 2006, vol. 3, pp. 1089-1094, June 2006
In this paper, we propose a semi-analytical method to compute error floors of LDPC codes on the binary symmetric channel decoded iteratively using the Gallager B algorithm. The error events of the decoder are characterized using combinatorial objects called trapping sets, originally defined by Richardson. In general, trapping sets are characteristic of the graphical representation of a code. We study the structure of trapping sets and explore their relation to graph parameters such as girth and vertex degrees. Using the proposed method, we compute error floors of regular structured and random LDPC codes with column weight three.
|
|