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

International Symposium on Turbo Codes and Iterative Information Processing

Comparison of different schedulings for the ADMM based LDPC decoding

Imen Debbabi, Bertrand Le Gal, Nadia Khouja, Fethi Tlili, Christophe Jégo

Published Sep 1, 2016• 9 citations
Publisher

Abstract

This paper proposes a general framework aiming at describing and comparing LDPC decoders based on the ADMM approach. ADMM is a linear programming decoding method. When applied on LDPC codes, it acts as an iterative message passing technique and enhances the error correction performance compared with the usual belief propagation based decoders. In this paper, three ADMM decoding algorithms classified according to their scheduling type are described and compared. Simulation results show that the layered scheduling is efficient to enhance the error correction performance while decreasing the average number of decoding iterations for the considered LDPC codes.

DOI
10.1109/istc.2016.7593075

Related papers

Accelerating Pro-ADMM-HL Penalized Algorithm for Decoding Binary LDPC Codes

Jing Bai, Weipeng Duan, Yuhao Chi +1 more

The alternating direction method of multipliers (ADMM) approach to decoding low-density parity-check (LDPC) codes has garnered lots of attention due to its superior error correction performance in error floor regions. However, improving convergence characteristic of ADMM decoding efficiently remains to be a crucial but challenging issue for practical application. In order to tackle this challenge, in this paper we first propose an efficient Pro-ADMM-based decoding algorithm framework by inserting additional quadratic proximal terms to each iteration of ADMM decoding for stabilizing the variable updates. Second, an message-passing interpretation of Pro-ADMM decoder is considered, and then an improved version based on horizontal layered scheduling, named Pro-ADMM-HL decoder is developed to further enhance the convergence behavior of Pro-ADMM decoding. Additionally, we analyze that the complexity of the proposed Pro-ADMM-HL decoders at each iteration displays linearly to LDPC code length. Finally, the effectiveness of the proposed Pro-ADMM and Pro-ADMM-HL decoding algorithm in terms of error correction performance and convergence characteristic is demonstrated by simulation results.

IEEE Communications Letters•May 8, 2024•3 citations

Fast Converging ADMM-Penalized Algorithm for LDPC Decoding

Imen Debbabi, Bertrand Le Gal, Nadia Khouja +2 more

The alternate direction method of multipliers (ADMM) approach has been recently considered for LDPC decoding. It has been approved to enhance the error rate performance compared with conventional message passing (MP) techniques in both the waterfall and error floor regions at the cost of a higher computation complexity. In this letter, a formulation of the ADMM decoding algorithm with modified computation scheduling is proposed. It increases the error correction performance of the decoding algorithm and reduces the average computation complexity of the decoding process thanks to a faster convergence. Simulation results show that this modified scheduling speeds up the decoding procedure with regards to the ADMM initial formulation while enhancing the error correction performance. This decoding speed-up is further improved when the proposed scheduling is teamed with a recent complexity reduction method detailed in Wei et al.IEEE Commun. Lett., 2015.

IEEE Communications Letters•Feb 19, 2016•39 citations

Reduced Complexity Node-Wise Scheduling of ADMM Decoding for LDPC Codes

Xiaopeng Jiao, Jianjun Mu, Haoyuan Wei

Similar to the belief propagation decoder, linear programming decoding based on the alternating direction method of multipliers (ADMM) can also be seen as an iterative message-passing decoding algorithm. How to schedule messages efficiently is an important aspect since it will influence the convergence rate of iterative decoders. In this letter, we investigate the node-wise scheduling for ADMM decoders, named NS-ADMM. In particular, we propose a reduced-complexity method for the NS-ADMM decoder by avoiding Euclidean projections involved in the calculation of message residuals. Simulation results show that the proposed method converges much faster than the flooding and layered scheduling while keeping a lower complexity when compared with the NS-ADMM decoder.

IEEE Communications Letters•Dec 22, 2016•25 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

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

An LP-based algorithm for decoding terminated LDPC convolutional codes

Hayfa Ben Thameur, Nadia Khouja, Fethi Tlili +2 more

Linear programming (LP) technique was demonstrated as efficient for binary and non-binary LDPC block decoding. Indeed, it improves the error correction performance of codes and provides the Maximum-likelihood (ML) certificate. In this paper, the LP algorithm is applied for decoding LDPC convolutional codes (LDPC-CC). The proposed algorithm is built on the decomposition method based on the alternating direction method of multipliers (ADMM). Motivated by the strong convergence guarantees of an ADMM based LDPC block code (LDPC-BC) decoder and its comparable complexity to a Belief Propagation (BP) based LDPC-BC decoder, the efficiency of decoding LDPC-CCs using the ADMM algorithm is empirically analyzed in this paper. Simulations are carried over LDPC-CCs derived from LDPC-BCs and the LDPC-CC proposed by the IEEE 1901 standard. Experimental results show that the LP decoding approach is a promising technique for improving LDPC-CC error correction performance.

International Conference on Internet of Things, Embedded Systems and Communications (IINTEC)•Oct 1, 2017•1 citation
This paper proposes a general framework aiming at describing and comparing LDPC decoders based on the ADMM approach. ADMM is a linear programming decoding method. When applied on LDPC codes, it acts as an iterative message passing technique and enhances the error correction performance compared with the usual belief propagation based decoders. In this paper, three ADMM decoding algorithms classified according to their scheduling type are described and compared. Simulation results show that the layered scheduling is efficient to enhance the error correction performance while decreasing the average number of decoding iterations for the considered LDPC codes.
The alternating direction method of multipliers (ADMM) approach to decoding low-density parity-check (LDPC) codes has garnered lots of attention due to its superior error correction performance in error floor regions. However, improving convergence characteristic of ADMM decoding efficiently remains to be a crucial but challenging issue for practical application. In order to tackle this challenge, in this paper we first propose an efficient Pro-ADMM-based decoding algorithm framework by inserting additional quadratic proximal terms to each iteration of ADMM decoding for stabilizing the variable updates. Second, an message-passing interpretation of Pro-ADMM decoder is considered, and then an improved version based on horizontal layered scheduling, named Pro-ADMM-HL decoder is developed to further enhance the convergence behavior of Pro-ADMM decoding. Additionally, we analyze that the complexity of the proposed Pro-ADMM-HL decoders at each iteration displays linearly to LDPC code length. Finally, the effectiveness of the proposed Pro-ADMM and Pro-ADMM-HL decoding algorithm in terms of error correction performance and convergence characteristic is demonstrated by simulation results.
The alternate direction method of multipliers (ADMM) approach has been recently considered for LDPC decoding. It has been approved to enhance the error rate performance compared with conventional message passing (MP) techniques in both the waterfall and error floor regions at the cost of a higher computation complexity. In this letter, a formulation of the ADMM decoding algorithm with modified computation scheduling is proposed. It increases the error correction performance of the decoding algorithm and reduces the average computation complexity of the decoding process thanks to a faster convergence. Simulation results show that this modified scheduling speeds up the decoding procedure with regards to the ADMM initial formulation while enhancing the error correction performance. This decoding speed-up is further improved when the proposed scheduling is teamed with a recent complexity reduction method detailed in Wei et al.IEEE Commun. Lett., 2015.
Similar to the belief propagation decoder, linear programming decoding based on the alternating direction method of multipliers (ADMM) can also be seen as an iterative message-passing decoding algorithm. How to schedule messages efficiently is an important aspect since it will influence the convergence rate of iterative decoders. In this letter, we investigate the node-wise scheduling for ADMM decoders, named NS-ADMM. In particular, we propose a reduced-complexity method for the NS-ADMM decoder by avoiding Euclidean projections involved in the calculation of message residuals. Simulation results show that the proposed method converges much faster than the flooding and layered scheduling while keeping a lower complexity when compared with the NS-ADMM decoder.
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.
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.
Linear programming (LP) technique was demonstrated as efficient for binary and non-binary LDPC block decoding. Indeed, it improves the error correction performance of codes and provides the Maximum-likelihood (ML) certificate. In this paper, the LP algorithm is applied for decoding LDPC convolutional codes (LDPC-CC). The proposed algorithm is built on the decomposition method based on the alternating direction method of multipliers (ADMM). Motivated by the strong convergence guarantees of an ADMM based LDPC block code (LDPC-BC) decoder and its comparable complexity to a Belief Propagation (BP) based LDPC-BC decoder, the efficiency of decoding LDPC-CCs using the ADMM algorithm is empirically analyzed in this paper. Simulations are carried over LDPC-CCs derived from LDPC-BCs and the LDPC-CC proposed by the IEEE 1901 standard. Experimental results show that the LP decoding approach is a promising technique for improving LDPC-CC error correction performance.