Thumbnail
Access Restriction
Open

Author Chilappagari, Shashi Kiran ♦ Chertkov, Michael ♦ Vasic, Bane
Source arXiv.org
Content type Text
File Format PDF
Date of Submission 2008-08-18
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Natural sciences & mathematics ♦ Mathematics ♦ Physics
Subject Keyword Computer Science - Information Theory ♦ Condensed Matter - Statistical Mechanics ♦ cs ♦ math ♦ physics:cond-mat
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.
Educational Use Research
Learning Resource Type Article
Page Count 9


Open content in new tab

   Open content in new tab