Towards Low-Complexity Linear-Programming Decoding

Abstract

We consider linear-programming (LP) decoding of low-density parity-check (LDPC) codes. While it is clear that one can use any general-purpose LP solver to solve the LP that appears in the decoding problem, we argue in this paper that the LP at hand is equipped with a lot of structure that one should take advantage of. Towards this goal, we study the dual LP and show how coordinate-ascent methods lead to very simple update rules that are tightly connected to the min-sum algorithm. Moreover, replacing minima in the formula of the dual LP with soft-minima one obtains update rules that are tightly connected to the sum-product algorithm. This shows that LP solvers with complexity similar to the min-sum algorithm and the sum-product algorithm are feasible. Finally, we also discuss some sub-gradient-based methods.

References in corpus (1)

• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes

Cited by in corpus (28)

• Probabilistic Analysis of Linear Programming Decoding
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
• Hardware Based Projection onto The Parity Polytope and Probability Simplex
• Efficient Linear Programming Decoding of HDPC Codes
• A Unified Framework for Linear-Programming Based Communication Receivers
• Joint Decoding of LDPC Codes and Finite-State Channels via Linear-Programming
• Improved linear programming decoding of LDPC codes and bounds on the minimum and fractional distance
• Low-Complexity LP Decoding of Nonbinary Linear Codes
• Polytope of Correct (Linear Programming) Decoding and Low-Weight Pseudo-Codewords
• An Iterative Joint Linear-Programming Decoding of LDPC Codes and Finite-State Channels
• Pseudo-codeword Landscape
• Decomposition Methods for Large Scale LP Decoding
• Approximated Structured Prediction for Learning Large Scale Graphical Models
• An Efficient Pseudo-Codeword Search Algorithm for Linear Programming Decoding of LDPC Codes
• Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
• Error Bounds for Repeat-Accumulate Codes Decoded via Linear Programming
• A Separation Algorithm for Improved LP-Decoding of Linear Block Codes
• LP decoding of expander codes: a simpler proof
• Proximal-ADMM Decoder for Nonbinary LDPC Codes
• Hardware-Based ADMM-LP Decoding
• Belief Propagation for Linear Programming
• The approximate maximum-likelihood certificate
• ADMM LP decoding of non-binary LDPC codes in ${\mathbb{F}}_{2^m}$
• Blending Learning and Inference in Structured Prediction
• Trellis-Based Check Node Processing for Low-Complexity Nonbinary LP Decoding
• Low Complexity Linear Programming Decoding of Nonbinary Linear Codes
• Searching for low weight pseudo-codewords
• Divide & Concur and Difference-Map BP Decoders for LDPC Codes