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

Shashi Kiran Chilappagari; Michael Chertkov; Bane Vasic

doi:10.1109/TIT.2011.2146670

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 journal › Article › peer-review

13 Scopus citations

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 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 language	English (US)
Article number	5895058
Pages (from-to)	4417-4426
Number of pages	10
Journal	IEEE Transactions on Information Theory
Volume	57
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2011.2146670
State	Published - Jul 2011

Keywords

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

Access to Document

10.1109/TIT.2011.2146670

Cite this

@article{59c39dc25bbe405897a87629fbf01757,

title = "An efficient instanton search algorithm for LP decoding of LDPC codes over the BSC",

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 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.",

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

author = "Chilappagari, {Shashi Kiran} and Michael Chertkov and Bane Vasic",

note = "Funding Information: Manuscript received September 02, 2008; revised October 26, 2010; accepted December 01, 2010. Date of current version June 22, 2011. The work of S. K. Chilappagari was performed while he was a summer GRA at LANL. The work at LANL, by S. K. Chilappagari and M. Chertkov, was carried out under the auspices of the National Nuclear Security Administration of the U.S. Department of Energy at Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396. B. Vasic was supported in part by the NSF and in part by Seagate Technology. Part of this work was presented at the IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, July, 2009. Part of this work appeared in the special issue of the Journal of Selected Areas in Communications on Capacity Approaching Codes, August 2009.",

year = "2011",

month = jul,

doi = "10.1109/TIT.2011.2146670",

language = "English (US)",

volume = "57",

pages = "4417--4426",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

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

AU - Chilappagari, Shashi Kiran

AU - Chertkov, Michael

AU - Vasic, Bane

N1 - Funding Information: Manuscript received September 02, 2008; revised October 26, 2010; accepted December 01, 2010. Date of current version June 22, 2011. The work of S. K. Chilappagari was performed while he was a summer GRA at LANL. The work at LANL, by S. K. Chilappagari and M. Chertkov, was carried out under the auspices of the National Nuclear Security Administration of the U.S. Department of Energy at Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396. B. Vasic was supported in part by the NSF and in part by Seagate Technology. Part of this work was presented at the IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, July, 2009. Part of this work appeared in the special issue of the Journal of Selected Areas in Communications on Capacity Approaching Codes, August 2009.

PY - 2011/7

Y1 - 2011/7

N2 - 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.

AB - 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.

KW - Binary symmetric channel (BSC)

KW - error-floor

KW - linear programming decoding

KW - low-density parity-check (LDPC) codes

KW - pseudo-codewords

UR - http://www.scopus.com/inward/record.url?scp=79959552159&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959552159&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2146670

DO - 10.1109/TIT.2011.2146670

M3 - Article

AN - SCOPUS:79959552159

SN - 0018-9448

VL - 57

SP - 4417

EP - 4426

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

M1 - 5895058

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this