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

IEEE Wireless Communications and Networking Conference

Implementation aspects of a pipeline ADMM-based LP decoding of LDPC convolutional codes

Hayfa Ben Thameur, Bertrand Le Gal, Nadia Khouja, Fethi Tlili, Christophe Jégo

Published Apr 1, 2018• 1 citation
Publisher

Abstract

The enforcement of the linear programming (LP) decoding was recently extended to LDPC convolutional codes (LDPC-CC). It was demonstrated that their convolutional structure suites the message-passing based representation of the LP problem, thanks to the application of the alternating directions method of multipliers (ADMM). In this paper, a modified formulation of the ADMM-LP problem is introduced for pipeline decoding of LDPC-CCs based on the layered schedule. Moreover, an assessment of the fixed-point format required for hardware implementation is provided to evaluate the complexity of the underlying decoding algorithm. Simulations show that an 8-bit quantization scheme yields negligible error correction performances loss of about 0.05 dB regarding the floating-precision ADMM based LDPC-CC decoder. Further, an algorithmic optimization of the Euclidean projection skipping technique, described in [1] [2], is proposed. This improved version enables to reduce the computational complexity of the decoding process without memory penalty contrary to the original formulation.

DOI
10.1109/wcnc.2018.8377103

Related papers

Low complexity ADMM-LP based decoding strategy for LDPC convolutional codes

Hayfa Ben Thameur, Bertrand Le Gal, Nadia Khouja +2 more

A node-wise (NS) schedule has been recently proposed for decoding LDPC codes with the linear programming (LP) decoding approach, based on the alternate direction method of multipliers (ADMM). It improves the error correction performances as well as the convergence speed of the ADMM-LP decoder. However, it suffers from a high computational complexity resulted from residuals calculation. In this paper, a new formulation of the ADMM-LP algorithm with a modified computational scheduling is proposed for decoding LDPC convolutional codes. Simulations show that it reduces the computational complexity while improving the error correction performances and speeding up the decoding process. The decoding complexity is further reduced when considering the NS-ADMM approximation which allows savings up to 70% of the residuals calculation.

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)•Sep 1, 2017•3 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

Reduced complexity ADMM-based schedules for LP decoding of LDPC convolutional codes

Hayfa Ben Thameur, Bertrand Le Gal, Nadia Khouja +2 more

The ADMM based linear programming (LP) technique shows interesting error correction performance when decoding binary LDPC block codes. Nonetheless, it's applicability to decode LDPC convolutional codes (LDPC-CC) has not been yet investigated. In this paper, a first flooding based formulation of the ADMM-LP for decoding LDPC-CCs is described. In addition, reduced complexity decoding schedules to lessen the storage requirements and improve the convergence speed of an ADMM-LP based LDPC-CC decoder without significant loss in error correction performances are proposed and assessed from an algorithmic and computational/memory complexity perspectives.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2017•1 citation

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

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

Application-specific Fixed-point Design of the Alternating Direction Method of Multipliers for Linear Program Decoding

Omar Samhan

We consider the design of linear-programming (LP) decoding in hardware of low-density parity-check (LDPC) codes. Previous work has shown that the alternating direction method of multipliers can be applied to solve LP decoding in a message passing manner amenable to hardware. Wasson et al demonstrated the feasibility of a hardware implementation in a field-programmable gate array. However, the area footprint and message bit-width of the implementation was not competitive with classic alternatives such as min-sum decoding. We leverage recent work by Jiao et al on implementing the central computational primitive of ADMM-LP decoding via look-up tables. In this thesis, we use the work of Jiao et al to develop a modified version of Wasson’s ADMM-LP decoding algorithm, realizing a bit-width reduction of about 50%.

•Jun 1, 2019•1 citation
The enforcement of the linear programming (LP) decoding was recently extended to LDPC convolutional codes (LDPC-CC). It was demonstrated that their convolutional structure suites the message-passing based representation of the LP problem, thanks to the application of the alternating directions method of multipliers (ADMM). In this paper, a modified formulation of the ADMM-LP problem is introduced for pipeline decoding of LDPC-CCs based on the layered schedule. Moreover, an assessment of the fixed-point format required for hardware implementation is provided to evaluate the complexity of the underlying decoding algorithm. Simulations show that an 8-bit quantization scheme yields negligible error correction performances loss of about 0.05 dB regarding the floating-precision ADMM based LDPC-CC decoder. Further, an algorithmic optimization of the Euclidean projection skipping technique, described in [1] [2], is proposed. This improved version enables to reduce the computational complexity of the decoding process without memory penalty contrary to the original formulation.
A node-wise (NS) schedule has been recently proposed for decoding LDPC codes with the linear programming (LP) decoding approach, based on the alternate direction method of multipliers (ADMM). It improves the error correction performances as well as the convergence speed of the ADMM-LP decoder. However, it suffers from a high computational complexity resulted from residuals calculation. In this paper, a new formulation of the ADMM-LP algorithm with a modified computational scheduling is proposed for decoding LDPC convolutional codes. Simulations show that it reduces the computational complexity while improving the error correction performances and speeding up the decoding process. The decoding complexity is further reduced when considering the NS-ADMM approximation which allows savings up to 70% of the residuals calculation.
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.
The ADMM based linear programming (LP) technique shows interesting error correction performance when decoding binary LDPC block codes. Nonetheless, it's applicability to decode LDPC convolutional codes (LDPC-CC) has not been yet investigated. In this paper, a first flooding based formulation of the ADMM-LP for decoding LDPC-CCs is described. In addition, reduced complexity decoding schedules to lessen the storage requirements and improve the convergence speed of an ADMM-LP based LDPC-CC decoder without significant loss in error correction performances are proposed and assessed from an algorithmic and computational/memory complexity perspectives.
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.
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.
We consider the design of linear-programming (LP) decoding in hardware of low-density parity-check (LDPC) codes. Previous work has shown that the alternating direction method of multipliers can be applied to solve LP decoding in a message passing manner amenable to hardware. Wasson et al demonstrated the feasibility of a hardware implementation in a field-programmable gate array. However, the area footprint and message bit-width of the implementation was not competitive with classic alternatives such as min-sum decoding. We leverage recent work by Jiao et al on implementing the central computational primitive of ADMM-LP decoding via look-up tables. In this thesis, we use the work of Jiao et al to develop a modified version of Wasson’s ADMM-LP decoding algorithm, realizing a bit-width reduction of about 50%.