Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1409.5140 · IEEE Transactions on Information Theory

The ADMM Penalized Decoder for LDPC Codes

Xishuo Liu, Stark Christiaan Draper

Published Apr 21, 2016• 80 citations
arXivHTMLPDF

Abstract

Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature-via simulation and via instanton analysis-that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding's high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders-ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with ℓ1and ℓ2penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs.

DOI
10.1109/tit.2016.2555847

Related papers

The l1 penalized decoder and its reweighted LP

Xishuo Liu, Stark Christiaan Draper, Benjamin Recht

Linear programming (LP) decoding for low density parity check (LDPC) codes proposed by Feldman et al. has attracted considerable attention in recent years. Despite having theoretical guarantees in some regimes, at low SNRs LP decoding is observed to have worse error performance than belief propagation (BP) decoding. In this paper, we present a novel decoding algorithm obtained by trying to solve a non-convex optimization problem using the alternating direction method of multipliers (ADMM). This non-convex problem is constructed by adding an ℓ1penalty term to the LP decoding objective. The goal of the penalty term is to make “pseudocodewords”, which are the non-integer vertices of the LP relaxation to which the LP decoder fails, more costly. We name this the “ℓ1penalized decoder”. We also develop a reweighted LP decoding algorithm base on this ℓ1penalized objective. We show that this reweighted LP has an improved theoretical recovery threshold compared to the original LP. In addition, simulations show that, in comparison to LP decoding, these two decoders both achieve significantly lower error rates and are not observed to have an “error floor”. In particular, the ℓ1penalized decoder meets or outperforms the BP decoder at all SNRs.

Allerton Conference on Communication, Control, and Computing•Oct 1, 2012•4 citations

Suppressing pseudocodewords by penalizing the objective of LP decoding

Xishuo Liu, Stark Christiaan Draper, Benjamin Recht

In this paper, we present a new class of decoders for low density parity check (LDPC) codes. We are motivated by the observation that the linear programming (LP) decoder has worse error performance than belief propagation (BP) decoders at low SNRs. We base our new decoders on the alternating direction method of multipliers (ADMM) decomposition technique for LP decoding. The ADMM not only efficiently solves the LP decoding problem, but also makes it possible to explore other decoding algorithms. In particular, we add various penalty terms to the linear objective of LP decoding with the goal of suppressing pseudocodewords. Simulation results show that the new decoders achieve much better error performance compared to LP decoder at low SNRs. What is more, similar to the LP decoder, no error floor is observed at high SNRs.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•25 citations

Instanton search algorithm for the ADMM penalized decoder

Xishuo Liu, Stark Christiaan Draper

Linear programming (LP) decoding using the alternating direction method of multipliers (ADMM) has been shown to be an efficient algorithm. A non-convex variation based on the ADMM LP decoder called the ADMM penalized decoder was introduced by Liu et al. (IEEE ITW, Sep. 2012) to close the signal-to-noise ratio (SNR) gap between LP decoding and classic belief propagation (BP) decoding. This algorithm was shown to achieve or outperform BP decoding at all SNRs, including high SNRs where BP decoding suffers from the error floor effect. In this paper, we study the behaviors of the ADMM penalized decoder at high SNRs where simulation is infeasible. We use a generic tool called instanton analysis and propose an instanton search algorithm for the ADMM penalized decoder. We then apply the algorithm to the [155, 64] Tanner code and a [1057, 813] LDPC code. We show that the instanton information we obtained provides good predictions for word-error-rate curve at high SNRs. In addition, our results suggest that the ADMM penalized decoder can suffer from trapping sets.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•3 citations

Improved ADMM Penalized Decoder for Irregular Low-Density Parity-Check Codes

Xiaopeng Jiao, Haoyuan Wei, Jianjun Mu +1 more

Based on linear programming (LP) decoding with alternating direction method of multipliers (ADMM), Liu et al. proposed an ADMM penalized decoder for low-density parity-check (LDPC) codes that can improve the error rate performance at low signal-to-noise ratios. In this letter, we propose a new ADMM penalized decoder to improve the error rate performance further for irregular LDPC codes. The proposed decoder modifies the penalty term of the objective function by assigning different penalty parameters for different variable node degrees. Simulations over three irregular LDPC codes show that the proposed decoder performs considerably better than the ADMM penalized decoder.

IEEE Communications Letters•Apr 10, 2015•49 citations

ADMM Check Node Penalized Decoders for LDPC Codes

Haoyuan Wei, Amir H. Banihashemi

Alternating direction method of multipliers (ADMM) is an efficient implementation of linear programming (LP) decoding for low-density parity-check (LDPC) codes. By adding penalty terms to the objective function of the LP decoding model, ADMM variable node (VN) penalized decoding can suppress the non-integral solutions and improve the frame error rate (FER) performance in the low signal-to-noise ratio (SNR) region. In this paper, we propose a novel ADMM check node (CN) penalized decoding algorithm. Codeword solutions which satisfy all parity-check equations will have smaller penalty values than non-codeword solutions, including the non-integral solutions. We discuss the required properties of CN-penalty functions, propose a few functions that satisfy those properties, and study their performance/complexity trade-offs. We also investigate the convergence properties of the proposed algorithm and prove that its performance is independent of the transmitted codeword. Using Monte Carlo simulations and instanton analysis, we then demonstrate that the proposed CN-penalized decoder outperforms ADMM VN penalized decoders in both waterfall and error floor regions. This comes at the expense of some increase in the decoding complexity.

IEEE Transactions on Communications•Mar 15, 2021•14 citations

Low-Density Parity-Check Decoding Algorithm Based on Symmetric Alternating Direction Method of Multipliers

Ji Zhang, Anmin Chen, Ying Zhang +3 more

The Alternating Direction Method of Multipliers (ADMM) has proven to be an efficient approach for implementing linear programming (LP) decoding of low-density parity-check (LDPC) codes. By introducing penalty terms into the LP decoding model's objective function, ADMM-based variable node penalized decoding effectively mitigates non-integral solutions, thereby improving frame error rate (FER) performance, especially in the low signal-to-noise ratio (SNR) region. In this paper, we leverage the ADMM framework to derive explicit iterative steps for solving the LP decoding problem for LDPC codes with penalty functions. To further enhance decoding efficiency and accuracy, We propose an LDPC code decoding algorithm based on the symmetric ADMM (S-ADMM). We also establish some contraction properties satisfied by the iterative sequence of the algorithm. Through simulation experiments, we evaluate the proposed S-ADMM decoder using three standard LDPC codes and three representative fifth-generation (5G) codes. The results show that the S-ADMM decoder consistently outperforms conventional ADMM penalized decoders, offering significant improvements in decoding performance.

Entropy•Apr 9, 2025•1 citation
Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature-via simulation and via instanton analysis-that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding's high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders-ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with ℓ1and ℓ2penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs.
Linear programming (LP) decoding for low density parity check (LDPC) codes proposed by Feldman et al. has attracted considerable attention in recent years. Despite having theoretical guarantees in some regimes, at low SNRs LP decoding is observed to have worse error performance than belief propagation (BP) decoding. In this paper, we present a novel decoding algorithm obtained by trying to solve a non-convex optimization problem using the alternating direction method of multipliers (ADMM). This non-convex problem is constructed by adding an ℓ1penalty term to the LP decoding objective. The goal of the penalty term is to make “pseudocodewords”, which are the non-integer vertices of the LP relaxation to which the LP decoder fails, more costly. We name this the “ℓ1penalized decoder”. We also develop a reweighted LP decoding algorithm base on this ℓ1penalized objective. We show that this reweighted LP has an improved theoretical recovery threshold compared to the original LP. In addition, simulations show that, in comparison to LP decoding, these two decoders both achieve significantly lower error rates and are not observed to have an “error floor”. In particular, the ℓ1penalized decoder meets or outperforms the BP decoder at all SNRs.
In this paper, we present a new class of decoders for low density parity check (LDPC) codes. We are motivated by the observation that the linear programming (LP) decoder has worse error performance than belief propagation (BP) decoders at low SNRs. We base our new decoders on the alternating direction method of multipliers (ADMM) decomposition technique for LP decoding. The ADMM not only efficiently solves the LP decoding problem, but also makes it possible to explore other decoding algorithms. In particular, we add various penalty terms to the linear objective of LP decoding with the goal of suppressing pseudocodewords. Simulation results show that the new decoders achieve much better error performance compared to LP decoder at low SNRs. What is more, similar to the LP decoder, no error floor is observed at high SNRs.
Linear programming (LP) decoding using the alternating direction method of multipliers (ADMM) has been shown to be an efficient algorithm. A non-convex variation based on the ADMM LP decoder called the ADMM penalized decoder was introduced by Liu et al. (IEEE ITW, Sep. 2012) to close the signal-to-noise ratio (SNR) gap between LP decoding and classic belief propagation (BP) decoding. This algorithm was shown to achieve or outperform BP decoding at all SNRs, including high SNRs where BP decoding suffers from the error floor effect. In this paper, we study the behaviors of the ADMM penalized decoder at high SNRs where simulation is infeasible. We use a generic tool called instanton analysis and propose an instanton search algorithm for the ADMM penalized decoder. We then apply the algorithm to the [155, 64] Tanner code and a [1057, 813] LDPC code. We show that the instanton information we obtained provides good predictions for word-error-rate curve at high SNRs. In addition, our results suggest that the ADMM penalized decoder can suffer from trapping sets.
Based on linear programming (LP) decoding with alternating direction method of multipliers (ADMM), Liu et al. proposed an ADMM penalized decoder for low-density parity-check (LDPC) codes that can improve the error rate performance at low signal-to-noise ratios. In this letter, we propose a new ADMM penalized decoder to improve the error rate performance further for irregular LDPC codes. The proposed decoder modifies the penalty term of the objective function by assigning different penalty parameters for different variable node degrees. Simulations over three irregular LDPC codes show that the proposed decoder performs considerably better than the ADMM penalized decoder.
Alternating direction method of multipliers (ADMM) is an efficient implementation of linear programming (LP) decoding for low-density parity-check (LDPC) codes. By adding penalty terms to the objective function of the LP decoding model, ADMM variable node (VN) penalized decoding can suppress the non-integral solutions and improve the frame error rate (FER) performance in the low signal-to-noise ratio (SNR) region. In this paper, we propose a novel ADMM check node (CN) penalized decoding algorithm. Codeword solutions which satisfy all parity-check equations will have smaller penalty values than non-codeword solutions, including the non-integral solutions. We discuss the required properties of CN-penalty functions, propose a few functions that satisfy those properties, and study their performance/complexity trade-offs. We also investigate the convergence properties of the proposed algorithm and prove that its performance is independent of the transmitted codeword. Using Monte Carlo simulations and instanton analysis, we then demonstrate that the proposed CN-penalized decoder outperforms ADMM VN penalized decoders in both waterfall and error floor regions. This comes at the expense of some increase in the decoding complexity.
The Alternating Direction Method of Multipliers (ADMM) has proven to be an efficient approach for implementing linear programming (LP) decoding of low-density parity-check (LDPC) codes. By introducing penalty terms into the LP decoding model's objective function, ADMM-based variable node penalized decoding effectively mitigates non-integral solutions, thereby improving frame error rate (FER) performance, especially in the low signal-to-noise ratio (SNR) region. In this paper, we leverage the ADMM framework to derive explicit iterative steps for solving the LP decoding problem for LDPC codes with penalty functions. To further enhance decoding efficiency and accuracy, We propose an LDPC code decoding algorithm based on the symmetric ADMM (S-ADMM). We also establish some contraction properties satisfied by the iterative sequence of the algorithm. Through simulation experiments, we evaluate the proposed S-ADMM decoder using three standard LDPC codes and three representative fifth-generation (5G) codes. The results show that the S-ADMM decoder consistently outperforms conventional ADMM penalized decoders, offering significant improvements in decoding performance.