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 International Conference on Acoustics Speech and Signal Processing

ADMM-Based ML Decoding: from Theory to Practice

Kira Kraft, Norbert Wehn

Published May 13, 2021• 5 citations
Publisher

Abstract

Integer Linear Programming (ILP) is a general method to solve the Maximum-Likelihood (ML) decoding problem for all kinds of binary linear codes. To this end, state-of-the-art techniques use a Branch-and-Bound (B&B) framework to partition the underlying integer linear problem into several relaxed linear problems. These linear problems then have to be solved in reasonable time by an efficient Linear Programming (LP) solver. Recently, the Alternating Direction Method of Multipliers (ADMM) has been proposed for efficient software and hardware LP decoding of sparse codes, hence, an ADMM-based ML decoder seems to be a promising approach. In this paper, we investigate this approach with respect to its algorithmic and implementation-specific challenges.

DOI
10.1109/icassp39728.2021.9414728

Related papers

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

Efficient QP-ADMM Decoder for Binary LDPC Codes and Its Performance Analysis

Jing Bai, Yongchao Wang, Qingjiang Shi

This paper presents an efficient quadratic programming (QP) decoder via the alternating direction method of multipliers (ADMM) technique, called QP-ADMM, for binary low-density parity-check (LDPC) codes. Its main contents are as follows: first, we relax the maximum likelihood (ML) decoding problem to a non-convex quadratic program. Then, we develop an ADMM solving algorithm for the formulated non-convex QP decoding model. In the proposed QP-ADMM decoder, complex Euclidean projections onto the check polytope are eliminated and variables in each updated step can be solved analytically in parallel. Moreover, it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence. We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption. Furthermore, by exploiting the inside structures of the QP model, the complexity of the proposed algorithm in each iteration is shown to be linear in terms of LDPC code length. Simulation results demonstrate the effectiveness of the proposed QP-ADMM decoder.

arXiv:1910.12712•IEEE Transactions on Signal Processing•Jan 1, 2020•18 citations

Efficient ADMM Decoder for Non-binary LDPC Codes based on Bit Embedding Technique

Xiaomeng Guo, Yongchao Wang

In this paper, we devise a new alternating direction method of multipliers (ADMM) decoder for non-binary low-density parity-check (LDPC) codes in Galois fields of characteristic two $\left( {{\mathbb{F}_{{2^q}}}} \right)$. Its main content are threefold: first, the procedure of formulating the maximum likelihood (ML) decoding problem in ${\mathbb{F}_{{2^q}}}$ to a linear integer problem in real space is presented; Second, after relaxing the integer problem to a continuous one, an efficient ADMM algorithm is customized to solve the latter, where all the entries of the variable vectors can be obtained in parallel; Third, we show that the proposed ADMM decoder satisfies the favorable codeword-independent property under some mild conditions and its computation complexity in each ADMM iteration is roughly $\mathcal{O}\left( {nq} \right)$, where n is code length of the considered non-binary LDPC code. Simulation results demonstrate that its performance, such as error-correction and decoding efficiency, is very competitive in comparison with state-of-the-art non-binary LDPC decoders.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•1 citation

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

Analysis of ADMM-LP algorithm for LDPC decoding, a first step to hardware implementation

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

The recent interest in linear programming techniques for LDPC decoding showed that these methods are too complex for real applicability. Alternating direction method of multipliers is a classic technique in convex optimization theory. When applied to the linear programming decoding of LDPC codes, the ADMM algorithm acts as a message passing decoding method. In this work, we present a complexity analysis of the ADMM LDPC decoder compared with the sum product approach and we explain the parallelism levels that are explored in the ADMM algorithm. A software implementation by taking advantage of the architectural features of the multi-core processors parallelism is presented. The overall analysis provides a better understanding of the ADMM approach complexity which makes a start to possible hardware implementations.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)•Dec 1, 2015•5 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
Integer Linear Programming (ILP) is a general method to solve the Maximum-Likelihood (ML) decoding problem for all kinds of binary linear codes. To this end, state-of-the-art techniques use a Branch-and-Bound (B&B) framework to partition the underlying integer linear problem into several relaxed linear problems. These linear problems then have to be solved in reasonable time by an efficient Linear Programming (LP) solver. Recently, the Alternating Direction Method of Multipliers (ADMM) has been proposed for efficient software and hardware LP decoding of sparse codes, hence, an ADMM-based ML decoder seems to be a promising approach. In this paper, we investigate this approach with respect to its algorithmic and implementation-specific challenges.
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.
This paper presents an efficient quadratic programming (QP) decoder via the alternating direction method of multipliers (ADMM) technique, called QP-ADMM, for binary low-density parity-check (LDPC) codes. Its main contents are as follows: first, we relax the maximum likelihood (ML) decoding problem to a non-convex quadratic program. Then, we develop an ADMM solving algorithm for the formulated non-convex QP decoding model. In the proposed QP-ADMM decoder, complex Euclidean projections onto the check polytope are eliminated and variables in each updated step can be solved analytically in parallel. Moreover, it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence. We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption. Furthermore, by exploiting the inside structures of the QP model, the complexity of the proposed algorithm in each iteration is shown to be linear in terms of LDPC code length. Simulation results demonstrate the effectiveness of the proposed QP-ADMM decoder.
In this paper, we devise a new alternating direction method of multipliers (ADMM) decoder for non-binary low-density parity-check (LDPC) codes in Galois fields of characteristic two (F2q)\left( {{\mathbb{F}_{{2^q}}}} \right)(F2q​). Its main content are threefold: first, the procedure of formulating the maximum likelihood (ML) decoding problem in F2q{\mathbb{F}_{{2^q}}}F2q​ to a linear integer problem in real space is presented; Second, after relaxing the integer problem to a continuous one, an efficient ADMM algorithm is customized to solve the latter, where all the entries of the variable vectors can be obtained in parallel; Third, we show that the proposed ADMM decoder satisfies the favorable codeword-independent property under some mild conditions and its computation complexity in each ADMM iteration is roughly O(nq)\mathcal{O}\left( {nq} \right)O(nq), where n is code length of the considered non-binary LDPC code. Simulation results demonstrate that its performance, such as error-correction and decoding efficiency, is very competitive in comparison with state-of-the-art non-binary LDPC decoders.
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 recent interest in linear programming techniques for LDPC decoding showed that these methods are too complex for real applicability. Alternating direction method of multipliers is a classic technique in convex optimization theory. When applied to the linear programming decoding of LDPC codes, the ADMM algorithm acts as a message passing decoding method. In this work, we present a complexity analysis of the ADMM LDPC decoder compared with the sum product approach and we explain the parallelism levels that are explored in the ADMM algorithm. A software implementation by taking advantage of the architectural features of the multi-core processors parallelism is presented. The overall analysis provides a better understanding of the ADMM approach complexity which makes a start to possible hardware implementations.
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.