---- dataentry seminar ----
date_dt : 2009-06-03
title : Trapping Sets, Instantons and Error Floors of LDPC Codes
speaker : Dr. Shashi Kiran Chilappagari
affiliation :  University of Arizona and ALGO, EPFL.
time : 11h15-12h15
room : BC229
table : seminars
===================
template:datatemplates:seminar
-----------------------


==== abstract ====
Low-density parity-check (LDPC) codes have been the focus of much research over the past decade due to their capacity approaching performance even when decoded using low-complexity decoding algorithms such as iterative message passing algorithms. Traditional message passing decoders are based on belief propagation and operate on a graphical representation of the code known as the Tanner graph. While optimal only for loop-free graphs, they work surprisingly well on loopy graphs. However, their performance abruptly degrades in the high signal-to-noise ratio (SNR), leading to the phenomenon of error floor.

In this talk, we present an overview of our recent results in the analysis of error floors of LDPC codes with emphasis on the binary symmetric channel (BSC). We describe a combinatorial framework to characterize the failures of the iterative decoders using trapping sets. By examining the relation between trapping sets and cycles in the Tanner graph, we establish tight upper and lower bounds on the guaranteed error correction capability of column-weight-three LDPC codes. We then show how the knowledge of trapping sets can be used to estimate the frame-error-rate (FER) performance in the error floor region.

We also present a complete characterization of the failures of the linear programming (LP) decoder using instantons. We explore the relation between trapping sets and instantons and show that the failures of different decoders for different channels share a common underlying topological structure. We then present code construction techniques that avoid such harmful configurations and provide codes with superior error floor performance.

(Joint work with Prof. Bane Vasic, Dr. Michael Chertkov, Dr. Mikhail Stepanov, Dr. Michael Marcellin, Dr. S. Sankaranarayanan and Dung Nguyen)

*Speaker Bio: *Shashi Kiran Chilappagari received the B.Tech. and M.Tech. degrees in electrical engineering from the Indian Institute of Technology, Madras, India in 2004 and Ph.D. in electrical engineering from the University of Arizona in 2008. He is currently a Research Engineer in the Department of Electrical and Computer Engineering at the University of Arizona, Tucson. In the summer of 2006, he was an intern in the Systems Group at the IBM Zurich Research Laboratory, Zurich, Switzerland. In the summer of 2008, he interned at the Los Alamos National Labs, Los Alamos, U.S.A. His research interests include error control coding and information theory with focus on the analysis of failures of various sub-optimal decoding algorithms for LDPC codes.