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 Letters

Real Time LP Decoding of LDPC Codes for High Correction Performance Applications

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

Published Oct 5, 2016• 8 citations
Publisher

Abstract

The alternate direction method of multipliers is a recent linear programming error correcting approach which improves the decoding performance of LDPC codes compared with the best BP decoding techniques. In this letter, an efficient implementation of the ADMM LP decoding algorithm on a multicore architecture is presented. Its throughput performance level is about one order of magnitude higher than related works on the same multicore target. The proposed decoder's throughput reaches up to 100 Mb/s which makes it viable for real time applications with tough error correction requirements.

DOI
10.1109/lwc.2016.2615304

Related papers

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

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

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

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

Hardware-Based Linear Program Decoding With the Alternating Direction Method of Multipliers

Mitchell Wasson, Mario Milicevic, Stark Christiaan Draper +1 more

We present a hardware-based implementation of linear program (LP) decoding for binary linear codes. LP decoding frames error-correction as an optimization problem. In contrast, variants of belief propagation (BP) decoding frame error-correction as a problem of graphical inference. LP decoding has several advantages over BP-based methods, including convergence guarantees and better error-rate performance in high-reliability channels. The latter makes LP decoding attractive for optical transport and storage applications. However, LP decoding, when implemented with general solvers, does not scale to large blocklengths and is not suitable for a parallelized implementation in hardware. It has been recently shown that the alternating direction method of multipliers (ADMM) can be applied to decompose the LP decoding problem. The result is a message-passing algorithm with a structure very similar to BP. We present modifications to this algorithm, resulting in a more intuitive and hardware-compatible form. This is particularly true for projection onto the parity polytope: the major computational primitive for ADMM-LP decoding. Furthermore, we present results for a fixed-point Verilog implementation of ADMM-LP decoding. This implementation targets a field-programmable gate array (FPGA) platform to evaluate error-rate performance and estimate resource usage. We show that frame error rate performance well within 0.5 dB of double-precision implementations is possible with 10-bit messages. Finally, we outline research opportunities that should be explored en route to an application-specific integrated circuit (ASIC) implementation that is capable of Gigabit-per-second throughput.

arXiv:1611.05975•IEEE Transactions on Signal Processing•Jul 22, 2019•21 citations
The alternate direction method of multipliers is a recent linear programming error correcting approach which improves the decoding performance of LDPC codes compared with the best BP decoding techniques. In this letter, an efficient implementation of the ADMM LP decoding algorithm on a multicore architecture is presented. Its throughput performance level is about one order of magnitude higher than related works on the same multicore target. The proposed decoder's throughput reaches up to 100 Mb/s which makes it viable for real time applications with tough error correction requirements.
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.
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.
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.
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.
We present a hardware-based implementation of linear program (LP) decoding for binary linear codes. LP decoding frames error-correction as an optimization problem. In contrast, variants of belief propagation (BP) decoding frame error-correction as a problem of graphical inference. LP decoding has several advantages over BP-based methods, including convergence guarantees and better error-rate performance in high-reliability channels. The latter makes LP decoding attractive for optical transport and storage applications. However, LP decoding, when implemented with general solvers, does not scale to large blocklengths and is not suitable for a parallelized implementation in hardware. It has been recently shown that the alternating direction method of multipliers (ADMM) can be applied to decompose the LP decoding problem. The result is a message-passing algorithm with a structure very similar to BP. We present modifications to this algorithm, resulting in a more intuitive and hardware-compatible form. This is particularly true for projection onto the parity polytope: the major computational primitive for ADMM-LP decoding. Furthermore, we present results for a fixed-point Verilog implementation of ADMM-LP decoding. This implementation targets a field-programmable gate array (FPGA) platform to evaluate error-rate performance and estimate resource usage. We show that frame error rate performance well within 0.5 dB of double-precision implementations is possible with 10-bit messages. Finally, we outline research opportunities that should be explored en route to an application-specific integrated circuit (ASIC) implementation that is capable of Gigabit-per-second throughput.