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

Entropy

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

Ji Zhang, Anmin Chen, Ying Zhang, Baofeng Ji, Huaan Li, Hengzhou Xu

Published Apr 9, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.3390/e27040404

Related papers

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

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•50 citations

ADMM Decoding of LDPC Codes: Simplification and Improvement

Haoyuan Wei

In this dissertation, we study linear programming (LP) decoding of low-density parity-check (LDPC) codes based on the alternating direction method of multipliers (ADMM) technique, or ADMM decoding for short.The decoding of LDPC codes is formulated as an LP model and solved efficiently by the ADMM technique.However, compared with traditional belief-propagation decoding, ADMM decoding suffers from higher complexity and worse error correction performance, which prevents the employment of ADMM decoding in reality.To reduce the complexity of ADMM decoding, we first focus on the simplification of the check polytope projection, the most complex operation in ADMM decoding.We propose an iterative check polytope projection algorithm without the sorting operation.The proposed algorithm converges with the increase of iterations.Moreover, for a fixed number of iterations, its average complexity and the worst-case complexity are linear in the input dimension.Another direction we propose to simplify ADMM decoding is to devise a better scheduling scheme than the standard flooding scheme.We start from the node-wise scheduling scheme which only updates the check node messages with the maximum message residual.Then we simplify the calculation of the message residual and propose a reduced-complexity node-wise scheduling scheme.To improve the error correction performance of ADMM decoding, we propose a novel ADMM penalized decoding algorithm whose penalty term is based on check nodes (CN).We investigate the properties of the CN penalty functions and show several examples.We make conclusions on its convergence properties and prove its failure probability is independent of the transmitted codewords for symmetric channels.Monte-Carlo simulation and the instanton analysis show its better error correction performance in the low and high SNR regions.Finally, we propose a post-processing technique to lower the error floor of LDPC codes.The output of the first stage decoder can be revised if the syndrome is found This is a journey with joys and tears.I encountered many amazing people.They instructed me, helped me, and accompanied me.First of all, I would like to thank Prof. Amir H. Banihashemi for his guidance.His attitudes towards the research and devotion to one specific area are impressive.All these will have a life-long influence on me.It is also a great time working with people in his coding research group.I have a great memory of learning from their presentations.Next, I should thank Prof.

•Jan 1, 2021•0 citations

ADMM LP decoding of non-binary LDPC codes in $\mathbb{F}_{2^m}$

Xishuo Liu, Stark Christiaan Draper

In this paper, we develop efficient decoders for non-binary low-density parity-check (LDPC) codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in $\mathbb{F}_{2^m}$ to a set of constraints in $\mathbb{F}_{2}$ that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projection onto polytopes that are studied in the literature, a projection that can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.

arXiv:1409.5141•Sep 17, 2014•1 citation

ADMM LP Decoding of Non-Binary LDPC Codes in $ \mathbb {F}_{2^{m}}$

Xishuo Liu, Stark Christiaan Draper

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in F2m to a set of constraints in F2that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.

IEEE Transactions on Information Theory•Apr 15, 2016•10 citations

Improved Free-of-CPP ADMM-Based Iterative Decoding Algorithm of Binary LDPC Codes

Jing Bai, Zedong An, Yuhao Chi +2 more

Iterative decoding algorithms based on the alternating direction method of multipliers (ADMM) decoding of low density parity check (LDPC) codes has emerged as an alternating decoding method and bringed a boom of research on drawing upon mathematical optimization to LDPC decoding. Improving error-correcting performance is a key issue to enhance the superiority of ADMM decoding. In this letter, we investigate an efficient ADMM-based iterative decoder for binary LDPC codes. First, we build an mathematical programming equivalence of the maximum likelihood (ML) decoding problem by transforming parity-check constraints to multiple equivalent linear constraints and eliminating check-polytope projection (CPP). Then, an iterative algorithm based on ADMM technique is developed to solve this free-of-CPP (FCPP) equivalence and each ADMM update can be computed efficiently. Moreover, the proposed ADMM-FCPP decoding algorithm is analyzed to display a linear complexity to the length of the LDPC code at each iteration. Finally, simulation results demonstrate the superiority of the proposed decoder in error-correcting performance compared with the state-of-the-art ADMM-based decoders.

IEEE Signal Processing Letters•Dec 4, 2024•3 citations
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.
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.
In this dissertation, we study linear programming (LP) decoding of low-density parity-check (LDPC) codes based on the alternating direction method of multipliers (ADMM) technique, or ADMM decoding for short.The decoding of LDPC codes is formulated as an LP model and solved efficiently by the ADMM technique.However, compared with traditional belief-propagation decoding, ADMM decoding suffers from higher complexity and worse error correction performance, which prevents the employment of ADMM decoding in reality.To reduce the complexity of ADMM decoding, we first focus on the simplification of the check polytope projection, the most complex operation in ADMM decoding.We propose an iterative check polytope projection algorithm without the sorting operation.The proposed algorithm converges with the increase of iterations.Moreover, for a fixed number of iterations, its average complexity and the worst-case complexity are linear in the input dimension.Another direction we propose to simplify ADMM decoding is to devise a better scheduling scheme than the standard flooding scheme.We start from the node-wise scheduling scheme which only updates the check node messages with the maximum message residual.Then we simplify the calculation of the message residual and propose a reduced-complexity node-wise scheduling scheme.To improve the error correction performance of ADMM decoding, we propose a novel ADMM penalized decoding algorithm whose penalty term is based on check nodes (CN).We investigate the properties of the CN penalty functions and show several examples.We make conclusions on its convergence properties and prove its failure probability is independent of the transmitted codewords for symmetric channels.Monte-Carlo simulation and the instanton analysis show its better error correction performance in the low and high SNR regions.Finally, we propose a post-processing technique to lower the error floor of LDPC codes.The output of the first stage decoder can be revised if the syndrome is found This is a journey with joys and tears.I encountered many amazing people.They instructed me, helped me, and accompanied me.First of all, I would like to thank Prof. Amir H. Banihashemi for his guidance.His attitudes towards the research and devotion to one specific area are impressive.All these will have a life-long influence on me.It is also a great time working with people in his coding research group.I have a great memory of learning from their presentations.Next, I should thank Prof.
ADMM LP decoding of non-binary LDPC codes in F2m\mathbb{F}_{2^m}F2m​
In this paper, we develop efficient decoders for non-binary low-density parity-check (LDPC) codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in F2m\mathbb{F}_{2^m}F2m​ to a set of constraints in F2\mathbb{F}_{2}F2​ that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projection onto polytopes that are studied in the literature, a projection that can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.
In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in F2m to a set of constraints in F2that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.
Iterative decoding algorithms based on the alternating direction method of multipliers (ADMM) decoding of low density parity check (LDPC) codes has emerged as an alternating decoding method and bringed a boom of research on drawing upon mathematical optimization to LDPC decoding. Improving error-correcting performance is a key issue to enhance the superiority of ADMM decoding. In this letter, we investigate an efficient ADMM-based iterative decoder for binary LDPC codes. First, we build an mathematical programming equivalence of the maximum likelihood (ML) decoding problem by transforming parity-check constraints to multiple equivalent linear constraints and eliminating check-polytope projection (CPP). Then, an iterative algorithm based on ADMM technique is developed to solve this free-of-CPP (FCPP) equivalence and each ADMM update can be computed efficiently. Moreover, the proposed ADMM-FCPP decoding algorithm is analyzed to display a linear complexity to the length of the LDPC code at each iteration. Finally, simulation results demonstrate the superiority of the proposed decoder in error-correcting performance compared with the state-of-the-art ADMM-based decoders.