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

Triangle Projection Algorithm in ADMM-LP Decoding of LDPC Codes

Jiang Yun, Huiyang Liu, Xiaopeng Jiao, Ji Wang, Qiaoqiao Xia

Published Mar 17, 2024• 1 citation
Publisher

Abstract

In this letter, a novel projection algorithm is proposed in which projection onto a triangle consisting of the three even-vertices closest to the vector to be projected replaces check polytope projection, achieving the same FER performance as exact projection algorithm in both high-iteration and low-iteration regime. Simulation results show that compared with the sparse affine projection algorithm (SAPA), it can improve the FER performance by 0.2dB as well as save average number of iterations by 4.3%.

DOI
10.1587/transfun.2023eal2104

Related papers

SAPA: Sparse Affine Projection Algorithm in ADMM-LP Decoding of LDPC Codes

Amirreza Asadzadeh, Masoud Barakatain, Stark Christiaan Draper +1 more

We present a simplified alternating direction method of multipliers with linear programming (ADMM-LP) decoder for LDPC codes by developing a method of approximate projection onto the parity polytope. The algorithm projects onto the affine hull of the$X$closest local codewords for each check of degree d, where$X$can be much smaller than d. We name this SAPA, the “sparse affine projection algorithm”. In contrast to exact projection, SAPA does not require a water-filling step and thus can be implemented with lower per-iteration complexity. We present numerical results which demonstrate not only that SAPA's performance, when used as part of an overall decoder, is close to that of exact projection, but also that the use of SAPA does not incur many additional iterations. This is in contrast to other approximate algorithms. Thus, SAPA is appropriate for use in limited-iteration decoders in high-throughput applications. Moreover, we analyze sparsity of polytope projections in the exact ADMM-LP decoding to explain the suitability of the proposed sparse approximation.

Canadian Workshop on Information Theory (CWIT)•Jun 5, 2022•8 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

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

A Simple Check Polytope Projection Penalized Algorithm for ADMM Decoding of LDPC Codes

Huiyang Liu, Pingquan He, Yun Jiang +2 more

ADMM penalized decoding method for Low-Density Parity-Check (LDPC) Codes can improve the frame error rate (FER) performance than the standard ADMM decoder by adding penalty terms to the objective function. However, penalty parameter optimization of the penalty terms is very difficult and extremely time-consuming. Additionally, the Euclidean projection onto the check polytope is the most complex part of ADMM-based decoding algorithms. In this paper, by dynamically choosing even-vertex in the check polytope closest to the input vector as the approximate projection, a simple and novel check polytope projection penalized algorithm for ADMM decoding is proposed which can avoid the tedious work of penalty parameter optimization and simplify the check polytope projection. The simulation results show that the proposed algorithm can substantially reduce the projection time while achieving better FER performance when compared with the existing penalized decoding. In particular, the proposed algorithm can save the decoding time by 23% to 41% compared with ADMM-PD-LSA algorithm.

IEEE Access•Jan 1, 2023•2 citations

A Hybrid Check Polytope Projection Algorithm for ADMM Decoding of LDPC Codes

Qiaoqiao Xia, Xin Wang, Huajun Liu +1 more

The Euclidean projection onto check polytope is the most complicated and time-consuming operation in the alternating direction method of multipliers (ADMM) decoding algorithm for low-density parity-check (LDPC) codes. Existing approximate even-vertex projection algorithm (EVA) can simplify the projection operation, but yields poor decoding performance. By alternately adopting EVA and other accurate projection algorithms, this letter proposes an innovative and simple hybrid projection algorithm (HPA) which can increase the percentage of unuseful projections. Simulation results show that the proposed algorithm can substantially reduce the projection time while achieving better frame error rate (FER) performance when compared with the standard ADMM decoding and the ADMM penalized decoding in the case of avoiding the tedious work of penalty parameter optimization. More importantly, compared with cut search algorithm (CSA), the proposed algorithm can significantly save the average projection time by nearly 80%, and the average decoding time by about 85%.

IEEE Communications Letters•Sep 11, 2020•12 citations

Approximate and Randomized ADMM-LP Decoding using Geometric Information of the Parity Polytope

Amirreza Asadzadeh

We present two strategies to reduce the complexity of the alternating direction method of multipliers with linear programming (ADMM-LP) decoder for LDPC codes. The complexity bottleneck of ADMM-LP decoding is projection onto the parity polytope. We propose the sparse affine projection algorithm (SAPA), which projects onto the affine hull of the χ closest local codewords for each check of degree d, where χ can be significantly smaller than d. Unlike exact projection, SAPA does not require a water-filling process, thus can be implemented with lower per-iteration complexity. Furthermore, we present a randomized layered scheduling framework for ADMM-LP decoding. In the randomized schedule, instead of updating all checks in a single iteration, more problematic checks are updated more often by using priors based the location of replica vectors inside or on the parity polytope. We demonstrate the decoder converges significantly faster with this randomized scheduling, thus it is well suited for limited-iteration applications.

•Nov 1, 2022•0 citations
In this letter, a novel projection algorithm is proposed in which projection onto a triangle consisting of the three even-vertices closest to the vector to be projected replaces check polytope projection, achieving the same FER performance as exact projection algorithm in both high-iteration and low-iteration regime. Simulation results show that compared with the sparse affine projection algorithm (SAPA), it can improve the FER performance by 0.2dB as well as save average number of iterations by 4.3%.
We present a simplified alternating direction method of multipliers with linear programming (ADMM-LP) decoder for LDPC codes by developing a method of approximate projection onto the parity polytope. The algorithm projects onto the affine hull of theXXXclosest local codewords for each check of degree d, whereXXXcan be much smaller than d. We name this SAPA, the “sparse affine projection algorithm”. In contrast to exact projection, SAPA does not require a water-filling step and thus can be implemented with lower per-iteration complexity. We present numerical results which demonstrate not only that SAPA's performance, when used as part of an overall decoder, is close to that of exact projection, but also that the use of SAPA does not incur many additional iterations. This is in contrast to other approximate algorithms. Thus, SAPA is appropriate for use in limited-iteration decoders in high-throughput applications. Moreover, we analyze sparsity of polytope projections in the exact ADMM-LP decoding to explain the suitability of the proposed sparse approximation.
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%.
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.
ADMM penalized decoding method for Low-Density Parity-Check (LDPC) Codes can improve the frame error rate (FER) performance than the standard ADMM decoder by adding penalty terms to the objective function. However, penalty parameter optimization of the penalty terms is very difficult and extremely time-consuming. Additionally, the Euclidean projection onto the check polytope is the most complex part of ADMM-based decoding algorithms. In this paper, by dynamically choosing even-vertex in the check polytope closest to the input vector as the approximate projection, a simple and novel check polytope projection penalized algorithm for ADMM decoding is proposed which can avoid the tedious work of penalty parameter optimization and simplify the check polytope projection. The simulation results show that the proposed algorithm can substantially reduce the projection time while achieving better FER performance when compared with the existing penalized decoding. In particular, the proposed algorithm can save the decoding time by 23% to 41% compared with ADMM-PD-LSA algorithm.
The Euclidean projection onto check polytope is the most complicated and time-consuming operation in the alternating direction method of multipliers (ADMM) decoding algorithm for low-density parity-check (LDPC) codes. Existing approximate even-vertex projection algorithm (EVA) can simplify the projection operation, but yields poor decoding performance. By alternately adopting EVA and other accurate projection algorithms, this letter proposes an innovative and simple hybrid projection algorithm (HPA) which can increase the percentage of unuseful projections. Simulation results show that the proposed algorithm can substantially reduce the projection time while achieving better frame error rate (FER) performance when compared with the standard ADMM decoding and the ADMM penalized decoding in the case of avoiding the tedious work of penalty parameter optimization. More importantly, compared with cut search algorithm (CSA), the proposed algorithm can significantly save the average projection time by nearly 80%, and the average decoding time by about 85%.
We present two strategies to reduce the complexity of the alternating direction method of multipliers with linear programming (ADMM-LP) decoder for LDPC codes. The complexity bottleneck of ADMM-LP decoding is projection onto the parity polytope. We propose the sparse affine projection algorithm (SAPA), which projects onto the affine hull of the χ closest local codewords for each check of degree d, where χ can be significantly smaller than d. Unlike exact projection, SAPA does not require a water-filling process, thus can be implemented with lower per-iteration complexity. Furthermore, we present a randomized layered scheduling framework for ADMM-LP decoding. In the randomized schedule, instead of updating all checks in a single iteration, more problematic checks are updated more often by using priors based the location of replica vectors inside or on the parity polytope. We demonstrate the decoder converges significantly faster with this randomized scheduling, thus it is well suited for limited-iteration applications.