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

Biennial Symposium on Communications

Reduced Message-Passing Bitwidth for Hardware Implementation of ADMM-LP Decoding

Omar Samhan, Stark Christiaan Draper

Published Jun 1, 2018• 4 citations
Publisher

Abstract

We consider the implementation in hardware of linear-programming (LP) decoding for low-density parity-check (LDPC) codes. Previous work has shown that the alternating direction method of multipliers (ADMM) 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 (FPGA). However, the area footprint and message bit-width of the implemenation was not competitive with classic alternatives such as min-sum decoding. In this paper we leverage recent work by Jiao et al. on implementating the central computational primative of ADMM-LP decoding (a certain Euclidean projection) via look-up tables (LUTs). While Jiao's work indicated the possiblity of significant bit-width reduction, it left open a number of questions about how to translate those ideas into hardware and what algorithmic modifications would be required. In this paper we answer those questions and develop a modified version of Wasson's ADMM-LP decoding algorithm, realizing a bit-width reduction of about 50%, thereby yielding a hardware implementation of ADMM-LP decoding that is competitive with min-sum.

DOI
10.1109/bsc.2018.8494685

Related papers

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

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•20 citations

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

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•88 citations

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

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

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.

IEEE Wireless Communications and Networking Conference•Apr 1, 2018•2 citations
We consider the implementation in hardware of linear-programming (LP) decoding for low-density parity-check (LDPC) codes. Previous work has shown that the alternating direction method of multipliers (ADMM) 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 (FPGA). However, the area footprint and message bit-width of the implemenation was not competitive with classic alternatives such as min-sum decoding. In this paper we leverage recent work by Jiao et al. on implementating the central computational primative of ADMM-LP decoding (a certain Euclidean projection) via look-up tables (LUTs). While Jiao's work indicated the possiblity of significant bit-width reduction, it left open a number of questions about how to translate those ideas into hardware and what algorithmic modifications would be required. In this paper we answer those questions and develop a modified version of Wasson's ADMM-LP decoding algorithm, realizing a bit-width reduction of about 50%, thereby yielding a hardware implementation of ADMM-LP decoding that is competitive with min-sum.
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%.
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.
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.
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 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.