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

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

Omar Samhan

Published Jun 1, 2019• 1 citation
OpenAlex

Abstract

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%.

Related papers

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

Omar Samhan, Stark Christiaan Draper

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.

Biennial Symposium on Communications•Jun 1, 2018•3 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

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

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

Low-Density Parity-Check Decoding Algorithm Based on Symmetric Alternating Direction Method of Multipliers

Ji Zhang, Anmin Chen, Ying Zhang +3 more

The Alternating Direction Method of Multipliers (ADMM) has proven to be an efficient approach for implementing linear programming (LP) decoding of low-density parity-check (LDPC) codes. By introducing penalty terms into the LP decoding model's objective function, ADMM-based variable node penalized decoding effectively mitigates non-integral solutions, thereby improving frame error rate (FER) performance, especially in the low signal-to-noise ratio (SNR) region. In this paper, we leverage the ADMM framework to derive explicit iterative steps for solving the LP decoding problem for LDPC codes with penalty functions. To further enhance decoding efficiency and accuracy, We propose an LDPC code decoding algorithm based on the symmetric ADMM (S-ADMM). We also establish some contraction properties satisfied by the iterative sequence of the algorithm. Through simulation experiments, we evaluate the proposed S-ADMM decoder using three standard LDPC codes and three representative fifth-generation (5G) codes. The results show that the S-ADMM decoder consistently outperforms conventional ADMM penalized decoders, offering significant improvements in decoding performance.

Entropy•Apr 9, 2025•1 citation

ADMM decoding of non-binary LDPC codes in F2m

Xishuo Liu, Stark Christiaan Draper

In this paper, we develop an efficient algorithm for linear programming (LP) decoding of non-binary low-density parity-check (LDPC) codes. We build our algorithm on the decomposition method based on the alternating direction method of multipliers (ADMM). Although expressing the LP decoding problem using ADMM is not hard, a sub-routine of ADMM - projection onto a polytope formed from embeddings of the non-binary single parity-check code - is not straightforward. In this work, we focus on non-binary codes in fields of characteristic two. This allows us to use operations in F2to relax the polytope under consideration into a form that is computational friendly. We introduce a rotation step that normalizes the geometry under consideration. We then apply ADMM a second time to solve the projection problem, which is a quadratic program (QP). Our decoding algorithm scales linearly with block length, linearly with check degree, and quadratically with field size.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•2 citations
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 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 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.
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.
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.
The Alternating Direction Method of Multipliers (ADMM) has proven to be an efficient approach for implementing linear programming (LP) decoding of low-density parity-check (LDPC) codes. By introducing penalty terms into the LP decoding model's objective function, ADMM-based variable node penalized decoding effectively mitigates non-integral solutions, thereby improving frame error rate (FER) performance, especially in the low signal-to-noise ratio (SNR) region. In this paper, we leverage the ADMM framework to derive explicit iterative steps for solving the LP decoding problem for LDPC codes with penalty functions. To further enhance decoding efficiency and accuracy, We propose an LDPC code decoding algorithm based on the symmetric ADMM (S-ADMM). We also establish some contraction properties satisfied by the iterative sequence of the algorithm. Through simulation experiments, we evaluate the proposed S-ADMM decoder using three standard LDPC codes and three representative fifth-generation (5G) codes. The results show that the S-ADMM decoder consistently outperforms conventional ADMM penalized decoders, offering significant improvements in decoding performance.
In this paper, we develop an efficient algorithm for linear programming (LP) decoding of non-binary low-density parity-check (LDPC) codes. We build our algorithm on the decomposition method based on the alternating direction method of multipliers (ADMM). Although expressing the LP decoding problem using ADMM is not hard, a sub-routine of ADMM - projection onto a polytope formed from embeddings of the non-binary single parity-check code - is not straightforward. In this work, we focus on non-binary codes in fields of characteristic two. This allows us to use operations in F2to relax the polytope under consideration into a form that is computational friendly. We introduce a rotation step that normalizes the geometry under consideration. We then apply ADMM a second time to solve the projection problem, which is a quadratic program (QP). Our decoding algorithm scales linearly with block length, linearly with check degree, and quadratically with field size.