An efficient instanton search algorithm for LP decoding of LDPC codes over the BSC

Shashi Kiran Chilappagari, Michael Chertkov, Bane Vasic

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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 equal to the transmitted codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which generates an error vector called the BSC-instanton. We prove that: (a) the LP decoder fails for any error pattern with support that is a superset of the support of an instanton; (b) for any input, the ISA outputs an instanton in the number of steps upper-bounded by twice the number of errors in the input error vector. We then find the number of unique instantons of different sizes for a given LDPC code by running the ISA sufficient number of times.

Original languageEnglish (US)
Article number5895058
Pages (from-to)4417-4426
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2011


  • Binary symmetric channel (BSC)
  • error-floor
  • linear programming decoding
  • low-density parity-check (LDPC) codes
  • pseudo-codewords

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'An efficient instanton search algorithm for LP decoding of LDPC codes over the BSC'. Together they form a unique fingerprint.

Cite this