Analysis of connections between pseudocodewords

Nathan Axvig, Deanna Dreher, Katherine Morrison, Eric Psota, Lance C. Pérez, Judy L. Walker

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature - linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords-are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.

Original languageEnglish (US)
Pages (from-to)4099-4107
Number of pages9
JournalIEEE Transactions on Information Theory
Issue number9
StatePublished - 2009


  • Graph cover decoding
  • Iterative message-passing decoding
  • Linear programming decoding
  • Low-density parity-check (LDPC) codes
  • Pseudocodewords

ASJC Scopus subject areas

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


Dive into the research topics of 'Analysis of connections between pseudocodewords'. Together they form a unique fingerprint.

Cite this