CaltechAUTHORS
  A Caltech Library Service

Reweighted LP Decoding for LDPC Codes

Khajehnejad, Amin and Dimakis, Alexandros G. and Hassibi, Babak and Vigoda, Benjamin and Bradley, William (2012) Reweighted LP Decoding for LDPC Codes. IEEE Transactions on Information Theory, 58 (9). pp. 5972-5984. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20121008-110544402

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20121008-110544402

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2012.2202211DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6210385PublisherUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
NSFCNS-0932428
NSFCCF-1018927
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI) N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)FA8750-07-C-0231
Subject Keywords:Error correction, LDPC codes, LP decoding
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12931603
Record Number:CaltechAUTHORS:20121008-110544402
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20121008-110544402
Official Citation:Khajehnejad, A.; Dimakis, A.G.; Hassibi, B.; Vigoda, B.; Bradley, W.; , "Reweighted LP Decoding for LDPC Codes," Information Theory, IEEE Transactions on , vol.58, no.9, pp.5972-5984, Sept. 2012 doi: 10.1109/TIT.2012.2202211 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6210385&isnumber=6268384
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34754
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:08 Oct 2012 18:25
Last Modified:08 Oct 2012 18:25

Repository Staff Only: item control page