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.
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.
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.
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.
Alternating direction method of multipliers (ADMM) decoding is a new decoding framework for low-density parity-check (LDPC) codes. It can be used to implement linear programming (LP) decoding or penalized LP decoding. Similar to belief propagation (BP) decoding, ADMM decoding consists of local “check” and “variable updates”. However, ADMM decoding performs better than BP at high signal-to-noise ratios (SNRs). To understand why these two locally operating algorithms result in different error floor behaviors, we study the dynamics of ADMM decoding in this paper. In particular, we focus on trapping sets, which are observed to cause error floors in ADMM decoding. Our results show that the dynamics of ADMM decoding on trapping sets can be characterized as a jump linear system. Furthermore, these results indicate that the Lagrange multipliers involved in ADMM play an important role in correcting trapping set errors. Finally, we present simulation results that support this understanding.
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.
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.
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.