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.
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.
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 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 ℓ 1 and ℓ 2 penalties. 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.
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.
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.
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 low-density parity-check (LDPC) decoding problem can be expressed as an integer linear programming (ILP) problem. One efficient method to solve the ILP problem is to relax the integer constraints and add penalty terms to the objective function, and the revised problem can be solved via the alternating direction method of multipliers (ADMM) algorithm. These penalty terms can punish the non-integral solutions and improve the decoding performance of the decoder. However, ADMM decoders are easily trapped in a local solution, which limits the frame error rate (FER) performance of the decoders at low signal-to-noise ratios (SNR). In this paper, we propose a restartable ADMM-based decoder using a negative proximal regularization. The negative proximal term will be updated whenever the decoder finds a new local solution. Therefore, the decoder can be restarted several times and the candidate solution which satisfies the parity-check equations and has the lowest objective function value can be selected as the decoder’s output. Some properties, together with several choices of penalty terms are discussed. We also investigate the convergence of our proposed decoder, and prove that the possibility of decoding errors is independent of the codeword that is transmitted. Simulation results show that our proposed decoder outperforms other ADMM-based decoders in most cases, while the decoding complexity maintains the same.