Searching for low weight pseudo-codewords

Michael Chertkov, Mikhail Stepanov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


Belief Propagation (BP) and Linear Programming (LP) decodings of Low Density Parity Check (LDPC) codes are discussed. We summarize results of instanton/pseudo-codeword approach developed for analysis of the error-floor domain of the codes. Instantons are special, code and decoding specific, configurations of the channel noise contributing most to the Frame-Error-Rate (FER). Instantons are decoded into pseudo-codewords. Instanton/pseudo-codeword with the lowest weight describes the largest Signal-to-Noise-Ratio (SNR) asymptotic of FER, while the whole spectra of the low weight instantons is descriptive of the FER vs SNR profile in the extended error-floor domain. First, we describe a general optimization method that allows to find the instantons for any coding/decoding. Second, we introduce LP-specific pseudo-codeword search algorithm that allows efficient calculations of the pseudo-codeword spectra. Finally, we discuss results of combined BP/LP error-floor exploration experiments for two model codes.

Original languageEnglish (US)
Title of host publication2007 Information Theory and Applications Workshop, Conference Proceedings, ITA
Number of pages7
StatePublished - 2007
Event2007 Information Theory and Applications Workshop, ITA - San Diego, CA, United States
Duration: Jan 29 2007Feb 2 2007

Publication series

Name2007 Information Theory and Applications Workshop, Conference Proceedings, ITA


Other2007 Information Theory and Applications Workshop, ITA
Country/TerritoryUnited States
CitySan Diego, CA

ASJC Scopus subject areas

  • Information Systems
  • Information Systems and Management


Dive into the research topics of 'Searching for low weight pseudo-codewords'. Together they form a unique fingerprint.

Cite this