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

Canadian Workshop on Information Theory (CWIT)

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

Amirreza Asadzadeh, Masoud Barakatain, Stark Christiaan Draper, Jeebak Mitra

Published Jun 5, 2022• 8 citations
Publisher

Abstract

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.

DOI
10.1109/cwit55308.2022.9817674

Related papers

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

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

Exploiting Parity-Polytope Geometry in Approximate and Randomized Scheduled ADMM-LP Decoding

Amirreza Asadzadeh, Anthony Ho, Frank R. Kschischang +1 more

We present two strategies to reduce the complexity of the alternating direction method of multipliers when applied to linear programming (ADMM-LP) decoding of low-density parity-check codes. First, to address the high complexity of computing a projection onto the parity polytope, the complexity bottleneck of ADMM-LP decoding, we propose the sparse affine projection algorithm (SAPA). SAPA projects onto the affine hull of χ ≤dnearby local codewords where the check degree isdand where χ can be significantly smaller thand. Unlike exact projection, SAPA does not require a water-filling process, and thus can be implemented with lower per-iteration complexity. Second, to reduce the number of effective iterations needed for ADMM-LP decoding, we propose a randomized layered scheduling framework. Rather than updating checks in round-robin fashion in each iteration, more “problematic” checks have a higher probability of being updated. The probability mass function that governs the selection of which checks to update is based upon the location of replica vectors inside (or on) the parity polytope. The resultant decoder converges significantly faster under this randomized scheduling than under round-robin scheduling. This makes it well suited for use in applications that limit the number of iterations.

IEEE Transactions on Communications•Mar 27, 2024•1 citation

Triangle Projection Algorithm in ADMM-LP Decoding of LDPC Codes

Jiang Yun, Huiyang Liu, Xiaopeng Jiao +2 more

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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 17, 2024•1 citation

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
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.
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.
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%.
We present two strategies to reduce the complexity of the alternating direction method of multipliers when applied to linear programming (ADMM-LP) decoding of low-density parity-check codes. First, to address the high complexity of computing a projection onto the parity polytope, the complexity bottleneck of ADMM-LP decoding, we propose the sparse affine projection algorithm (SAPA). SAPA projects onto the affine hull of χ ≤dnearby local codewords where the check degree isdand where χ can be significantly smaller thand. Unlike exact projection, SAPA does not require a water-filling process, and thus can be implemented with lower per-iteration complexity. Second, to reduce the number of effective iterations needed for ADMM-LP decoding, we propose a randomized layered scheduling framework. Rather than updating checks in round-robin fashion in each iteration, more “problematic” checks have a higher probability of being updated. The probability mass function that governs the selection of which checks to update is based upon the location of replica vectors inside (or on) the parity polytope. The resultant decoder converges significantly faster under this randomized scheduling than under round-robin scheduling. This makes it well suited for use in applications that limit the number of iterations.
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%.
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.