2008/08/19 by Shashi Kiran Chilappagari, Michael Chertkov, Chilappagari, Shashi Kiran +3
Computer Science · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.0808.2515
Submitted to IEEE Transactions on Information Theory. 9 Pages, 4 Figures; Dr. Bane Vasic added as an author; Changes made to the introduction and abstract; Acknowledgment section added; Some references added; Figures modified to make them more clear;
arxiv created 2008/09/02 · arxiv updated 2009/12/01
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 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.