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

arXiv:1901.07806 · IEEE Wireless Communications Letters

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

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

Published Mar 12, 2019• 21 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/lwc.2019.2904565

Related papers

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

Reduced-Complexity Linear Programming Decoding Based on ADMM for LDPC Codes

Haoyuan Wei, Xiaopeng Jiao, Jianjun Mu

The Euclidean projection onto check polytopes is the most time-consuming operation in the linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes. In this letter, instead of reducing the complexity of Euclidean projection itself, we propose a new method to reduce the decoding complexity of ADMM-based LP decoder by decreasing the number of Euclidean projections. In particular, if all absolute values of the element-wise differences between the input vector of Euclidean projection in the current iteration and that in the previous iteration are less than a predefined value, then the Euclidean projection at the current iteration will be no longer performed. Simulation results show that the proposed decoder can still save roughly 20% decoding time even if both the over-relaxation and early termination techniques are used.

IEEE Communications Letters•Apr 1, 2015•51 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

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

Efficient QP-ADMM Decoder for Binary LDPC Codes and Its Performance Analysis

Jing Bai, Yongchao Wang, Qingjiang Shi

This paper presents an efficient quadratic programming (QP) decoder via the alternating direction method of multipliers (ADMM) technique, called QP-ADMM, for binary low-density parity-check (LDPC) codes. Its main contents are as follows: first, we relax the maximum likelihood (ML) decoding problem to a non-convex quadratic program. Then, we develop an ADMM solving algorithm for the formulated non-convex QP decoding model. In the proposed QP-ADMM decoder, complex Euclidean projections onto the check polytope are eliminated and variables in each updated step can be solved analytically in parallel. Moreover, it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence. We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption. Furthermore, by exploiting the inside structures of the QP model, the complexity of the proposed algorithm in each iteration is shown to be linear in terms of LDPC code length. Simulation results demonstrate the effectiveness of the proposed QP-ADMM decoder.

arXiv:1910.12712•IEEE Transactions on Signal Processing•Jan 1, 2020•18 citations

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
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.
The Euclidean projection onto check polytopes is the most time-consuming operation in the linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes. In this letter, instead of reducing the complexity of Euclidean projection itself, we propose a new method to reduce the decoding complexity of ADMM-based LP decoder by decreasing the number of Euclidean projections. In particular, if all absolute values of the element-wise differences between the input vector of Euclidean projection in the current iteration and that in the previous iteration are less than a predefined value, then the Euclidean projection at the current iteration will be no longer performed. Simulation results show that the proposed decoder can still save roughly 20% decoding time even if both the over-relaxation and early termination techniques are used.
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.
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.
This paper presents an efficient quadratic programming (QP) decoder via the alternating direction method of multipliers (ADMM) technique, called QP-ADMM, for binary low-density parity-check (LDPC) codes. Its main contents are as follows: first, we relax the maximum likelihood (ML) decoding problem to a non-convex quadratic program. Then, we develop an ADMM solving algorithm for the formulated non-convex QP decoding model. In the proposed QP-ADMM decoder, complex Euclidean projections onto the check polytope are eliminated and variables in each updated step can be solved analytically in parallel. Moreover, it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence. We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption. Furthermore, by exploiting the inside structures of the QP model, the complexity of the proposed algorithm in each iteration is shown to be linear in terms of LDPC code length. Simulation results demonstrate the effectiveness of the proposed QP-ADMM decoder.
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.