Error Correction Coding Laboratory

Home Publications Projects Tools Links
  • Contact
    • +1-520-626-5550
    • vasic@ece.arizona.edu

An Efficient Instanton Search Algorithm for LP Decoding of LDPC Codes Over the BSC

S. K. Chilappagari, M. Chertkov, and B. Vasić, "An Efficient Instanton Search Algorithm for LP Decoding of LDPC Codes Over the BSC," IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4417 - 4426, Jul. 2011.

Link

it_lp_bsc.pdf

Citation

@article{CCV_11_IT,
abstract = {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.},
author = {Chilappagari, S. K. and Chertkov, M. and Vasić, B.},
journal = {IEEE Trans. Inf. Theory},
month = {Jul.},
volume = {57},
number = {7},
pages = {4417--4426},
title = {An Efficient Instanton Search Algorithm for {LP} Decoding of {LDPC} Codes Over the {BSC}},
year = {2011},
}