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 Symposium on Information Theory (ISIT)

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

Xiaojie Zhang, Paul H. Siegel

Published Jul 1, 2013• 91 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2013.6620477

Related papers

An Iterative Check Polytope Projection Algorithm for ADMM-Based LP Decoding of LDPC Codes

Haoyuan Wei, Amir H. Banihashemi

Alternating direction method of multipliers (ADMM) is a popular technique for linear-programming decoding of low-density parity-check codes. The computational complexity of ADMM is dominated by the Euclidean projection of a real-valued vector onto a parity-check polytope. Existing algorithms for such a projection all require sorting operations, which happen to be the most complex part of the projection. In this letter, we propose an iterative algorithm, without sorting operation, for projection onto the parity-check polytope. The proposed algorithm has a worst case complexity linear in the input dimension compared with the super-linear complexity of existing algorithms.

IEEE Communications Letters•Oct 25, 2017•50 citations

A Concise Polytope Projection Method for ADMM-Assisted LP Decoding of LDPC Codes

Parul Parul, Manish Gupta, Rajesh Kumar Narula +1 more

The alternating direction method of multipliers (ADMM) has proven to be a highly efficient method for implementing linear programming (LP) decoding for low-density parity-check (LDPC) codes. The projection on the parity polytope is the most time-intensive operation involved in the ADMM-assisted LP decoding. The existing projection methods involve sorting operations or complicated iterations which are difficult to perform by hardware systems. In this paper, an efficient parity-polytope projection algorithm is proposed by mapping the projection problem onto an isomorphic problem of probability simplex. The projection on probability simplex is obtained by utilizing its recurrent structure. This algorithm does not require sorting operations. Each iteration fixes at least one component of the input vector and has straightforward iteration steps. The simulation results show a noticeable reduction in the processing time for obtaining the projection of a given vector. Due to these advantages, it is beneficial for the effective implementation of ADMM-assisted LP decoding systems.

International Conference on Quantum Technologies, Communications, Computing, Hardware and Embedded Systems Security (iQ-CCHESS)•Sep 15, 2023•0 citations

A Fast Iterative Check Polytope Projection Algorithm for ADMM Decoding of LDPC Codes by Bisection Method

Yan Lin, Qiaoqiao Xia, Wenwu HE +1 more

Using linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes shows lower complexity than the original LP decoding. However, the development of the ADMM-LP decoding algorithm could still be limited by the computational complexity of Euclidean projections onto parity check polytope. In this paper, we proposed a bisection method iterative algorithm (BMIA) for projection onto parity check polytope avoiding sorting operation and the complexity is linear. In addition, the convergence of the proposed algorithm is more than three times as fast as the existing algorithm, which can even be 10 times in the case of high input dimension.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Sep 30, 2019•10 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

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

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
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.
Alternating direction method of multipliers (ADMM) is a popular technique for linear-programming decoding of low-density parity-check codes. The computational complexity of ADMM is dominated by the Euclidean projection of a real-valued vector onto a parity-check polytope. Existing algorithms for such a projection all require sorting operations, which happen to be the most complex part of the projection. In this letter, we propose an iterative algorithm, without sorting operation, for projection onto the parity-check polytope. The proposed algorithm has a worst case complexity linear in the input dimension compared with the super-linear complexity of existing algorithms.
The alternating direction method of multipliers (ADMM) has proven to be a highly efficient method for implementing linear programming (LP) decoding for low-density parity-check (LDPC) codes. The projection on the parity polytope is the most time-intensive operation involved in the ADMM-assisted LP decoding. The existing projection methods involve sorting operations or complicated iterations which are difficult to perform by hardware systems. In this paper, an efficient parity-polytope projection algorithm is proposed by mapping the projection problem onto an isomorphic problem of probability simplex. The projection on probability simplex is obtained by utilizing its recurrent structure. This algorithm does not require sorting operations. Each iteration fixes at least one component of the input vector and has straightforward iteration steps. The simulation results show a noticeable reduction in the processing time for obtaining the projection of a given vector. Due to these advantages, it is beneficial for the effective implementation of ADMM-assisted LP decoding systems.
Using linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes shows lower complexity than the original LP decoding. However, the development of the ADMM-LP decoding algorithm could still be limited by the computational complexity of Euclidean projections onto parity check polytope. In this paper, we proposed a bisection method iterative algorithm (BMIA) for projection onto parity check polytope avoiding sorting operation and the complexity is linear. In addition, the convergence of the proposed algorithm is more than three times as fast as the existing algorithm, which can even be 10 times in the case of high input dimension.
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.
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.
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.