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 Transactions on Communications

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

Amirreza Asadzadeh, Anthony Ho, Frank R. Kschischang, Stark Christiaan Draper

Published Mar 27, 2024• 1 citation
Publisher

Abstract

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.

DOI
10.1109/tcomm.2024.3382328

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

Randomized Scheduling of ADMM-LP Decoding Based on Geometric Priors

Amirreza Asadzadeh, Masoud Barakatain, Jeebak Mitra +2 more

We present a randomized schedule for alternating direction method of multipliers with linear programming (ADMM-LP) decoding of low-density parity check (LDPC) codes. The randomized schedule is based on horizontal layered decoding, where nodes are updated sequentially. Unlike existing layered decoding frameworks where all check nodes are updated exactly once per iteration, we propose a randomized schedule where more problematic nodes are updated more frequently. To do so, we sample from a probability mass function (PMF) over all check nodes and the check with sampled index is updated. The probability of each check to be updated is determined by its state. The PMF is constructed based on the distribution of replica (check) vectors inside or on the parity polytope. The randomized decoder usually converges faster than both standard and horizontal layered decoders, making it suitable for limited-iteration decoding in high-throughput applications.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•1 citation

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

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

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

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
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.
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.
We present a randomized schedule for alternating direction method of multipliers with linear programming (ADMM-LP) decoding of low-density parity check (LDPC) codes. The randomized schedule is based on horizontal layered decoding, where nodes are updated sequentially. Unlike existing layered decoding frameworks where all check nodes are updated exactly once per iteration, we propose a randomized schedule where more problematic nodes are updated more frequently. To do so, we sample from a probability mass function (PMF) over all check nodes and the check with sampled index is updated. The probability of each check to be updated is determined by its state. The PMF is constructed based on the distribution of replica (check) vectors inside or on the parity polytope. The randomized decoder usually converges faster than both standard and horizontal layered decoders, making it suitable for limited-iteration decoding in high-throughput applications.
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.
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.
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.
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.