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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

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

Yan Lin, Qiaoqiao Xia, Wenwu HE, Qinglin Zhang

Published Sep 30, 2019• 10 citations
Publisher

Abstract

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.

DOI
10.1587/transfun.e102.a.1406

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 Reduced-Complexity ADMM Based Decoding Algorithm for LDPC Codes

Zhibiao Liang, Xiang Chen, Xinghua Sun +1 more

Alternating Direction Method of Multipliers (ADM-M) is an effective method for Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes. In the ADMM-based LDPC decoding algorithm, Euclidean projection on the check polytope is the key step. Current Euclidean projection algorithms in general require either sorting or iterative operations. However, when decoding LDPC codes with high coding rate, the sorting operation brings a high level of computation complexity. Moreover, although the current iterative projection algorithms do not involve the complex operation of sorting, its convergence speed is slow. In this paper, based on trend extrapolation, a reduced-complexity iterative check polytope projection algorithm is proposed. In the proposed algorithm, the target projection point can be found based on the variation trend of the geometric position of the projection points obtained from previous iterations. Therefore, it ensures fast convergence and does not sacrifice on bit error rate (BER) performance. The simulation results confirm that the proposed algorithm can effectively reduce the decoding complexity, especially for LDPC codes with high coding rate.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 1, 2019•4 citations

A Fast Approximate Check Polytope Projection Algorithm for ADMM Decoding of LDPC Codes

Qiaoqiao Xia, Yan Lin, Shidi Tang +1 more

Simplifying the Euclidean projection onto check polytope is an efficient way to reduce the computational complexity of alternating direction method of multipliers (ADMM) decoding algorithm for low-density parity-check (LDPC) codes. Existing algorithms for check polytope projection require sorting operation or iterative operation, which happens to be the most complex part of the projection. In this letter, a novel and fast projection algorithm is proposed without sorting and iterative operations. In the proposed algorithm, line segment projection replaces check polytope projection to approach approximate Euclidean projection at low computational complexity. Simulation results show that the proposed algorithm can substantially reduce the projection time while maintaining the frame error rate (FER) performance. In particular, the proposed algorithm can save the average projection time by 43% compared with cut search algorithm (CSA) when the dimension of the input vector is 20.

IEEE Communications Letters•Jul 1, 2019•29 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

Bisection Method Assisted Affine Projection Algorithm in ADMM-LP Decoding of LDPC Codes

Rui Cheng, Yun JIANG, Qinglin Zhang +1 more

Many researchers have proposed optimization methods to reduce the computational complexity of the Euclidean projection onto check polytope in the alternating direction method of multipliers (ADMM) decoding for Low-Density Parity-Check (LDPC) codes. Existing the sparse affine projection algorithm (SAPA) projects the vector to be projected onto an χ-dimension affine hull and the dimension χ is fixed, resulting in deteriorating decoding performance. In this letter, bisection method assisted affine projection algorithm is proposed to determine the correct projection dimension for each the vector to be projected with the bisection method iterative algorithm. Simulation results show that the proposed algorithm can improve the accuracy of projection results by 68.2%. The FER performance of the proposed algorithm is almost the same as that of the exact projection algorithm, and compared with the sparse affine projection algorithm (SAPA), it can improve the FER performance by 0.14 dB as well as save average number of iterations by 3.2%.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 16, 2025•0 citations
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.
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.
Alternating Direction Method of Multipliers (ADM-M) is an effective method for Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes. In the ADMM-based LDPC decoding algorithm, Euclidean projection on the check polytope is the key step. Current Euclidean projection algorithms in general require either sorting or iterative operations. However, when decoding LDPC codes with high coding rate, the sorting operation brings a high level of computation complexity. Moreover, although the current iterative projection algorithms do not involve the complex operation of sorting, its convergence speed is slow. In this paper, based on trend extrapolation, a reduced-complexity iterative check polytope projection algorithm is proposed. In the proposed algorithm, the target projection point can be found based on the variation trend of the geometric position of the projection points obtained from previous iterations. Therefore, it ensures fast convergence and does not sacrifice on bit error rate (BER) performance. The simulation results confirm that the proposed algorithm can effectively reduce the decoding complexity, especially for LDPC codes with high coding rate.
Simplifying the Euclidean projection onto check polytope is an efficient way to reduce the computational complexity of alternating direction method of multipliers (ADMM) decoding algorithm for low-density parity-check (LDPC) codes. Existing algorithms for check polytope projection require sorting operation or iterative operation, which happens to be the most complex part of the projection. In this letter, a novel and fast projection algorithm is proposed without sorting and iterative operations. In the proposed algorithm, line segment projection replaces check polytope projection to approach approximate Euclidean projection at low computational complexity. Simulation results show that the proposed algorithm can substantially reduce the projection time while maintaining the frame error rate (FER) performance. In particular, the proposed algorithm can save the average projection time by 43% compared with cut search algorithm (CSA) when the dimension of the input vector is 20.
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.
Many researchers have proposed optimization methods to reduce the computational complexity of the Euclidean projection onto check polytope in the alternating direction method of multipliers (ADMM) decoding for Low-Density Parity-Check (LDPC) codes. Existing the sparse affine projection algorithm (SAPA) projects the vector to be projected onto an χ-dimension affine hull and the dimension χ is fixed, resulting in deteriorating decoding performance. In this letter, bisection method assisted affine projection algorithm is proposed to determine the correct projection dimension for each the vector to be projected with the bisection method iterative algorithm. Simulation results show that the proposed algorithm can improve the accuracy of projection results by 68.2%. The FER performance of the proposed algorithm is almost the same as that of the exact projection algorithm, and compared with the sparse affine projection algorithm (SAPA), it can improve the FER performance by 0.14 dB as well as save average number of iterations by 3.2%.