CaltechAUTHORS
Published September 2012 | Version Submitted
Journal Article Open

Reweighted LP Decoding for LDPC Codes

Creators

  • 1. ROR icon California Institute of Technology
  • 2. ROR icon University of Southern California

Abstract

We introduce a novel algorithm for decoding binary linear codes by linear programming (LP). We build on the LP decoding algorithm of Feldman and introduce a postprocessing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity.

Additional Information

© 2012 IEEE. Manuscript received March 14, 2011; revised September 27, 2011; accepted May 11, 2012. Date of publication June 01, 2012; date of current version August 14, 2012. This work was supported in part by the National Science Foundation under Grants CCF-0729203, CNS-0932428, and CCF-1018927, in part by the Office of Naval Research under the MURI Grant N00014-08-1-0747, in part by Caltech's Lee Center for Advanced Networking, and in part by DARPA FA8750-07-C-0231. The material in this paper was presented in part at the Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2010.

Attached Files

Submitted - Reweighted_20LP_20Decoding_20for_20LDPC_20Codes.pdf

Files

Reweighted_20LP_20Decoding_20for_20LDPC_20Codes.pdf

Files (434.3 kB)

Name Size
md5:1a354e9b9742820df15240f445b56323
434.3 kB Preview Download

Additional details

Identifiers

Eprint ID
34754
Resolver ID
CaltechAUTHORS:20121008-110544402

Related works

Describes
http://arxiv.org/abs/1103.2837 (URL)

Funding

NSF
CCF-0729203
NSF
CNS-0932428
NSF
CCF-1018927
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI)
N00014-08-1-0747
Caltech Lee Center for Advanced Networking
Defense Advanced Research Projects Agency (DARPA)
FA8750-07-C-0231

Dates

Created
2012-10-08
Created from EPrint's datestamp field
Updated
2021-11-09
Created from EPrint's last_modified field

Caltech Custom Metadata

Other Numbering System Name
INSPEC Accession Number
Other Numbering System Identifier
12931603