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 Electronics, Circuits and Systems (ICECS)

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

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

Published Dec 1, 2015• 5 citations
Publisher

Abstract

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.

DOI
10.1109/icecs.2015.7440322

Related papers

Evaluation of the hardware complexity of the ADMM approach for LDPC decoding

Imen Debbabi, Nadia Khouja, Fethi Tlili +2 more

Linear Programming (LP) is a novel technique for LDPC decoding. With the advance of the Alternate Direction Method of Multipliers (ADMM) approach, a significant step towards LP LDPC decoding scalability and optimization is made possible. Yet, this innovative decoding technique has not been implemented in hardware. Its hardware complexity has neither been estimated nor compared with traditional techniques. In this paper, an overview of the ADMM approach and its error correction performances for LDPC decoding is provided. Then, its computation complexity is evaluated to show the hardware feasibility of ADMM-based LDPC decoders. Our analysis is mainly carried at two levels. First, a quantitative complexity analysis is reported and a comparison with traditional LDPC decoders is given. Second, a proposal of a partially parallel architecture is described and its hardware complexity is evaluated then compared with state-of-the-art LDPC decoders.

IEEE Wireless Communications and Networking Conference•Apr 1, 2016•4 citations

Multicore implementation of LDPC decoders based on ADMM algorithm

Imen Debbabi, Nadia Khouja, Fethi Tlili +2 more

Alternate direction method of multipliers (ADMM) technique has recently been proposed for LDPC decoding. Even though it improves the error rate performance compared with traditional message passing (MP) techniques, it shows a higher computation complexity. In this article, the ADMM decoding algorithm is first described. Then, its computation complexity is analyzed. Finally, an optimized version which benefits from the multi-core processors architecture as well as the ADMM algorithm s parallelism is presented. The optimized version of the ADMM decoder can achieve up to 30 Mbps for standardized LDPC codes on a laptop x86 processor. Therefore, it could guide an efficient GPU implementation for real-time and high-throughput decoding systems requiring correction performances beyond MP-Sum Product Algorithm (SPA) capabilities.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 1, 2016•14 citations

Efficient iterative LP decoding of LDPC codes with alternating direction method of multipliers

Xiaojie Zhang, Paul H. Siegel

In this paper, we propose an efficient message-passing algorithm to solve the LP decoding problem. This algorithm is based on the alternating direction method of multipliers (ADMM), a classic technique in convex optimization theory that is designed for parallel implementation. The computational complexity of ADMM-based LP decoding is largely determined by the method used to project a vector of real values to the parity polytope of a given parity check. The key contribution of this paper is a novel, efficient projection algorithm that can substantially improve the decoding speed of the ADMM-based LP decoder.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•91 citations

ADMM hardware decoder for regular LDPC codes using a NISC-based architecture

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

The Alternate Direction Method of Multipliers (ADMM) approach is an original method for LDPC decoding based on the linear programming (LP) technique. It introduces a novelty at the error correction performance level. Nevertheless, this method can be toughly implemented due to its high computational complexity. In this paper, an implementation of the ADMM LP decoding algorithm on an FPGA target is presented. Its hardware resource cost is evaluated and compared with the state of the art LDPC decoders using the belief propagation (BP) decoding approach. The preliminary logic synthesis results show that an LP based hardware decoder for LDPC codes should be viable for applications with tough error correction requirements. However, additional research works are required to reach equivalent hardware complexity and throughput performances that are similar to traditional BP based LDPC decoders.

IEEE Wireless Communications and Networking Conference•Apr 1, 2018•2 citations

Minimum-Polytope-Based Linear Programming Decoder for LDPC Codes via ADMM Approach

Jing Bai, Yongchao Wang, Francis C. M. Lau

In this letter, we develop an efficient linear programming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main contributions are as follows. First, we propose an algorithm based on the alternating direction method of multipliers (ADMM) technique to solve this LP relaxation. By exploiting the orthogonality structure of the LP model, each ADMM update step can be implemented in parallel. Second, the proposed decoding algorithm under this LP formulation eliminates the Euclidean projection on the check polytope compared with the existing ADMM-based LP decoding algorithms. Third, the feasibility analysis of the proposed algorithm is presented. Moveover, complexity analysis shows that our proposed LP decoder in each iteration has a lower complexity than the state-of-the-art ADMM-based LP decoders. Simulation results demonstrate that the proposed LP decoder achieves better performance than other competing ADMM-based LP decoders in terms of decoding time.

arXiv:1901.07806•IEEE Wireless Communications Letters•Mar 12, 2019•21 citations

Quadratic Programming Decoder for Binary LDPC Codes via ADMM Technique with Linear Complexity

Jing Bai, Yongchao Wang

In this paper, we develop an efficient quadratic programming (QP) decoding algorithm via the alternating direction method of multipliers (ADMM) technique for binary low density parity check (LDPC) codes. Its main content is as follows: first, through transforming the three-variables parity check equation to its equivalent expression, we relax the maximum likelihood decoding problem to a quadratic program. Second, the ADMM technique is exploited to design the solving algorithm of the resulting QP decoding model. Compared with the existing ADMM-based mathematical programming (MP) decoding algorithms, our proposed algorithm eliminates complex Euclidean projection onto the check polytope. Third, we prove that the proposed algorithm satisfies the favorable property of all-zeros assumption. Moreover, by exploiting the inside structure of the QP model, we show that the decoding complexity of our proposed algorithm in each iteration is linear in terms of LDPC code length. Simulation results demonstrate that the proposed QP decoder attains better error-correction performance than the sum-product BP decoder and costs the least amount of decoding time amongst the state-of-the-art ADMM-based MP decoding algorithms.

International Conference on Communications•Jun 1, 2020•3 citations
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.
Linear Programming (LP) is a novel technique for LDPC decoding. With the advance of the Alternate Direction Method of Multipliers (ADMM) approach, a significant step towards LP LDPC decoding scalability and optimization is made possible. Yet, this innovative decoding technique has not been implemented in hardware. Its hardware complexity has neither been estimated nor compared with traditional techniques. In this paper, an overview of the ADMM approach and its error correction performances for LDPC decoding is provided. Then, its computation complexity is evaluated to show the hardware feasibility of ADMM-based LDPC decoders. Our analysis is mainly carried at two levels. First, a quantitative complexity analysis is reported and a comparison with traditional LDPC decoders is given. Second, a proposal of a partially parallel architecture is described and its hardware complexity is evaluated then compared with state-of-the-art LDPC decoders.
Alternate direction method of multipliers (ADMM) technique has recently been proposed for LDPC decoding. Even though it improves the error rate performance compared with traditional message passing (MP) techniques, it shows a higher computation complexity. In this article, the ADMM decoding algorithm is first described. Then, its computation complexity is analyzed. Finally, an optimized version which benefits from the multi-core processors architecture as well as the ADMM algorithm s parallelism is presented. The optimized version of the ADMM decoder can achieve up to 30 Mbps for standardized LDPC codes on a laptop x86 processor. Therefore, it could guide an efficient GPU implementation for real-time and high-throughput decoding systems requiring correction performances beyond MP-Sum Product Algorithm (SPA) capabilities.
In this paper, we propose an efficient message-passing algorithm to solve the LP decoding problem. This algorithm is based on the alternating direction method of multipliers (ADMM), a classic technique in convex optimization theory that is designed for parallel implementation. The computational complexity of ADMM-based LP decoding is largely determined by the method used to project a vector of real values to the parity polytope of a given parity check. The key contribution of this paper is a novel, efficient projection algorithm that can substantially improve the decoding speed of the ADMM-based LP decoder.
The Alternate Direction Method of Multipliers (ADMM) approach is an original method for LDPC decoding based on the linear programming (LP) technique. It introduces a novelty at the error correction performance level. Nevertheless, this method can be toughly implemented due to its high computational complexity. In this paper, an implementation of the ADMM LP decoding algorithm on an FPGA target is presented. Its hardware resource cost is evaluated and compared with the state of the art LDPC decoders using the belief propagation (BP) decoding approach. The preliminary logic synthesis results show that an LP based hardware decoder for LDPC codes should be viable for applications with tough error correction requirements. However, additional research works are required to reach equivalent hardware complexity and throughput performances that are similar to traditional BP based LDPC decoders.
In this letter, we develop an efficient linear programming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main contributions are as follows. First, we propose an algorithm based on the alternating direction method of multipliers (ADMM) technique to solve this LP relaxation. By exploiting the orthogonality structure of the LP model, each ADMM update step can be implemented in parallel. Second, the proposed decoding algorithm under this LP formulation eliminates the Euclidean projection on the check polytope compared with the existing ADMM-based LP decoding algorithms. Third, the feasibility analysis of the proposed algorithm is presented. Moveover, complexity analysis shows that our proposed LP decoder in each iteration has a lower complexity than the state-of-the-art ADMM-based LP decoders. Simulation results demonstrate that the proposed LP decoder achieves better performance than other competing ADMM-based LP decoders in terms of decoding time.
In this paper, we develop an efficient quadratic programming (QP) decoding algorithm via the alternating direction method of multipliers (ADMM) technique for binary low density parity check (LDPC) codes. Its main content is as follows: first, through transforming the three-variables parity check equation to its equivalent expression, we relax the maximum likelihood decoding problem to a quadratic program. Second, the ADMM technique is exploited to design the solving algorithm of the resulting QP decoding model. Compared with the existing ADMM-based mathematical programming (MP) decoding algorithms, our proposed algorithm eliminates complex Euclidean projection onto the check polytope. Third, we prove that the proposed algorithm satisfies the favorable property of all-zeros assumption. Moreover, by exploiting the inside structure of the QP model, we show that the decoding complexity of our proposed algorithm in each iteration is linear in terms of LDPC code length. Simulation results demonstrate that the proposed QP decoder attains better error-correction performance than the sum-product BP decoder and costs the least amount of decoding time amongst the state-of-the-art ADMM-based MP decoding algorithms.