LP Decoding Corrects a Constant Fraction of Errors

DOI10.1109/TIT.2006.887523MaRDI QIDQ3548232zbMATH OpenFDO

Authors Jon Feldman, Tal Malkin, Martin J. Wainwright, Rocco A. Servedio, Clifford Stein

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TIT.2006.887523

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Cyclic codes (94B15) Decoding (94B35)

Recommendations

• Message passing algorithms and improved LP decoding
• LP decoding achieves capacity
• Using Linear Programming to Decode Binary Linear Codes

Cited in

(20)

• Multidimensional decoding networks for trapping set analysis
• Identifying an unknown code by partial Gaussian elimination
• LP decoding of codes with expansion parameter above \(2/3\)
• Analysis of the relation between properties of LDPC codes and the Tanner graph
• Characterizations of pseudo-codewords of (low-density) parity-check codes
• LP decoding achieves capacity
• Low-power LDPC decoding by exploiting the fault-tolerance of the sum-product algorithm
• Using Linear Programming to Decode Binary Linear Codes
• Improved Bounds on the Word Error Probability of<tex>$RA(2)$</tex>Codes With Linear-Programming-Based Decoding
• Minimum Pseudoweight and Minimum Pseudocodewords of LDPC Codes
• On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm
• On linear programming decoding on a quantized additive white Gaussian noise channel
• Asymptotic estimation of the fraction of errors correctable by q-ary LDPC codes
• scientific article; zbMATH DE number 1775410 (Why is no real title available?)
• LP/SDP hierarchy lower bounds for decoding random LDPC codes
• Local-optimality guarantees based on paths for optimal decoding
• Decoding turbo-like codes via linear programming
• Error bounds for repeat-accumulate codes decoded via linear programming
• Linear-time decoding from a constant fraction of errors for irregular expander codes
• When can an expander code correct (n) errors in O(n) time?

This page was built for publication: LP Decoding Corrects a Constant Fraction of Errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548232)