Linear programming based detectors for two-dimensional intersymbol interference channels

Shrinivas Kudekar, Jason K. Johnson, Misha Chertkov

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

4 Citations (Scopus)

Abstract

We present and study linear programming based detectors for two-dimensional intersymbol interference channels. Interesting instances of two-dimensional intersymbol interference channels are magnetic storage, optical storage and Wyner's cellular network model. We show that the optimal maximum a posteriori detection in such channels lends itself to a natural linear programming based sub-optimal detector. We call this the Pairwise linear program detector. Our experiments show that the Pairwise linear program detector performs poorly. We then propose two methods to strengthen our detector. These detectors are based on systematically enhancing the Pairwise linear program. The first one, the Block linear program detector adds higher order potential functions in an exhaustive manner, as constraints, to the Pairwise linear program detector. We show by experiments that the Block linear program detector has performance close to the optimal detector. We then develop another detector by adaptively adding frustrated cycles to the Pairwise linear program detector. Empirically, this detector also has performance close to the optimal one and turns out to be less complex then the Block linear program detector.

Original languageEnglish
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages2999-3003
Number of pages5
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: 31 Jul 20115 Aug 2011

Publication series

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

Conference

Conference2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/TerritoryRussian Federation
CitySt. Petersburg
Period31/07/115/08/11

Fingerprint

Dive into the research topics of 'Linear programming based detectors for two-dimensional intersymbol interference channels'. Together they form a unique fingerprint.

Cite this