Improved linear programming decoding using frustrated cycles

Shrinivas Kudekar, Jason K. Johnson, Misha Chertkov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

We consider data transmission over a binary-input additive white Gaussian noise channel using low-density parity-check codes. One of the most popular techniques for decoding low-density parity-check codes is the linear programming decoder. In general, the linear programming decoder is suboptimal. In this paper we present a systematic approach to enhance the linear programming decoder. More precisely, in the cases where the linear program outputs a fractional solution, we give a simple algorithm to identify frustrated cycles which cause the output of the linear program to be fractional. Then adding these cycles, adaptively to the basic linear program, we show improved word error rate performance.

Original languageEnglish
Title of host publication2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages1496-1500
Number of pages5
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey
Duration: 7 Jul 201312 Jul 2013

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Conference

Conference2013 IEEE International Symposium on Information Theory, ISIT 2013
Country/TerritoryTurkey
CityIstanbul
Period7/07/1312/07/13

Fingerprint

Dive into the research topics of 'Improved linear programming decoding using frustrated cycles'. Together they form a unique fingerprint.

Cite this