An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes

Michael Chertkov, Mikhail G. Stepanov

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


In linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristically create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a pseudocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.

Original languageEnglish (US)
Pages (from-to)1514-1520
Number of pages7
JournalIEEE Transactions on Information Theory
Issue number4
StatePublished - Apr 2008


  • Error-floor
  • Linear programming decoding
  • Low-density parity-check (LDPC) codes

ASJC Scopus subject areas

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


Dive into the research topics of 'An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes'. Together they form a unique fingerprint.

Cite this