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

Simple item page
dc.creatorChilappagari, Shashi Kiran
dc.creatorChertkov, Michael
dc.creatorVasic, Bane
dc.date2008-08-19
dc.date2008-09-02
dc.date.accessioned2026-07-07T09:59:35Z
dc.date.available2026-07-07T09:59:35Z
dc.descriptionWe 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.
dc.descriptionSubmitted 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;
dc.identifierhttps://arxiv.org/abs/0808.2515
dc.identifierhttp://arxiv.org/abs/0808.2515
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168075
dc.subjectInformation Theory
dc.subjectStatistical Mechanics
dc.titleProvably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC
dc.typetext

Files

Collections

arXiv