Adaptive Methods for Linear Programming Decoding

DOI10.1109/TIT.2008.2006384MaRDI QIDQ3604926zbMATH OpenOpenAlexFDO

Authors Mohammad Hossein Taghavi, Paul Siegel

Publication date 24 February 2009

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

Full work available at URL https://arxiv.org/abs/cs/0703123

Mathematics Subject Classification ID

Linear programming (90C05) Sensitivity (robustness) (93B35)

Abstract: Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that it can significantly reduce the complexity of the problem, which was originally exponential in the maximum check-node degree. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in the performance.

Recommendations

• Using Linear Programming to Decode Binary Linear Codes
• Multistep linear programming approaches for decoding low-density parity-check codes
• Using linear programming to decode LDPC codes
• Message passing algorithms and improved LP decoding

Cited in

(5)

• Multistep linear programming approaches for decoding low-density parity-check codes
• Linear time adaptive arithmetic coding
• A Reduced-Complexity Projection Algorithm for ADMM-Based LP Decoding
• Efficient Implementation of Linear Programming Decoding
• scientific article; zbMATH DE number 7720786 (Why is no real title available?)

This page was built for publication: Adaptive Methods for Linear Programming Decoding

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