Improved linear programming decoding using frustrated cycles

Shrinivas Kudekar; Jason K. Johnson; Misha Chertkov

doi:10.1109/ISIT.2013.6620476

Improved linear programming decoding using frustrated cycles

Shrinivas Kudekar, Jason K. Johnson, Misha Chertkov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

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 language	English (US)
Title of host publication	2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages	1496-1500
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2013.6620476
State	Published - 2013
Externally published	Yes
Event	2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey Duration: Jul 7 2013 → Jul 12 2013

Publication series

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

Other

Other	2013 IEEE International Symposium on Information Theory, ISIT 2013
Country/Territory	Turkey
City	Istanbul
Period	7/7/13 → 7/12/13

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2013.6620476

Cite this

Improved linear programming decoding using frustrated cycles. / Kudekar, Shrinivas; Johnson, Jason K.; Chertkov, Misha.
2013 IEEE International Symposium on Information Theory, ISIT 2013. 2013. p. 1496-1500 6620476 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kudekar, S, Johnson, JK & Chertkov, M 2013, Improved linear programming decoding using frustrated cycles. in 2013 IEEE International Symposium on Information Theory, ISIT 2013., 6620476, IEEE International Symposium on Information Theory - Proceedings, pp. 1496-1500, 2013 IEEE International Symposium on Information Theory, ISIT 2013, Istanbul, Turkey, 7/7/13. https://doi.org/10.1109/ISIT.2013.6620476

@inproceedings{819a421cb31e4988b7ce1c948c98e828,

title = "Improved linear programming decoding using frustrated cycles",

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.",

author = "Shrinivas Kudekar and Johnson, {Jason K.} and Misha Chertkov",

year = "2013",

doi = "10.1109/ISIT.2013.6620476",

language = "English (US)",

isbn = "9781479904464",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "1496--1500",

booktitle = "2013 IEEE International Symposium on Information Theory, ISIT 2013",

note = "2013 IEEE International Symposium on Information Theory, ISIT 2013 ; Conference date: 07-07-2013 Through 12-07-2013",

}

TY - GEN

T1 - Improved linear programming decoding using frustrated cycles

AU - Kudekar, Shrinivas

AU - Johnson, Jason K.

AU - Chertkov, Misha

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84890405855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84890405855&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2013.6620476

DO - 10.1109/ISIT.2013.6620476

M3 - Conference contribution

AN - SCOPUS:84890405855

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1496

EP - 1500

BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013

T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013

Y2 - 7 July 2013 through 12 July 2013

ER -

Improved linear programming decoding using frustrated cycles

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this