TY - GEN
T1 - Analysis of error floors of LDPC codes under LP decoding over the BSC
AU - Chilappagari, Shashi Kiran
AU - Vasic, Bane
AU - Stepanov, Mikhail
AU - Chertkov, Michael
PY - 2009
Y1 - 2009
N2 - We consider Linear Programming (LP) decoding of a fixed Low-Density Parity-Check (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudo-codeword 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 BSC-instanton 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 upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then 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.
AB - We consider Linear Programming (LP) decoding of a fixed Low-Density Parity-Check (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudo-codeword 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 BSC-instanton 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 upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then 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.
UR - http://www.scopus.com/inward/record.url?scp=70449470759&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449470759&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2009.5205739
DO - 10.1109/ISIT.2009.5205739
M3 - Conference contribution
AN - SCOPUS:70449470759
SN - 9781424443130
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 379
EP - 383
BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009
T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009
Y2 - 28 June 2009 through 3 July 2009
ER -