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 Communications Letters

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

Qiaoqiao Xia, Xin Wang, Huajun Liu, Qinglin Zhang

Published Sep 11, 2020• 12 citations
Publisher

Abstract

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

DOI
10.1109/lcomm.2020.3023600

Related papers

An Improved Check Polytope Projection Penalized Algorithm for ADMM Decoding of LDPC Codes

Ziyi Wang, Yun Jiang, Qiaoqiao Xia

The Euclidean projection onto check polytope is the most complicated and time-consuming operation in the alternating direction method of multipliers (ADMM) decoding for Low-Density Parity-Check (LDPC) codes. The check polytope projection penalized algorithm can avoid the tedious work of penalty parameter optimization and simplified the calculation process of check polytope projection. However, the over-punishment of check polytope projection penalized algorithm may lead to poor decoding performance, when combined with the over-relaxation technique. In this paper, an improved check polytope projection penalized algorithm is proposed. In order to reduce the ratio of even-vertex projection, we restrict the points far away from the even-vertex of the check polytope by introducing the penalty constraint condition. Simulation results show that the frame error rate (FER) performance of the proposed algorithm is almost the same as that of the cut search projection algorithm (CSA), and it can save the average decoding time by 22.9%–52%.

IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC)•Aug 19, 2024•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

An Enhanced HDPC-EVA Decoder Based on ADMM

Yujin Zheng, Yan Lin, Zhuo Zhang +2 more

Linear programming (LP) decoding based on the alternating direction method of multipliers (ADMM) has proved to be effective for low-density parity-check (LDPC) codes. However, for high-density parity-check (HDPC) codes, the ADMM-LP decoder encounters two problems, namely a high-density check matrix in HDPC codes and a great number of pseudocodewords in HDPC codes' fundamental polytope. The former problem makes the check polytope projection extremely complex, and the latter one leads to poor frame error rates (FER) performance. To address these issues, we introduce the even vertex algorithm (EVA) into the ADMM-LP decoding algorithm for HDPC codes, named as HDPC-EVA. HDPC-EVA can reduce the complexity of the projection process and improve the FER performance. We further enhance the proposed decoder by the automorphism groups of codes, creating diversity in the parity-check matrix. The simulation results show that the proposed decoder is capable of cutting down the average decoding time for each iteration by 30%-60%, as well as achieving near maximum likelihood (ML) performance on some BCH codes.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Apr 1, 2021•5 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

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
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%.
The Euclidean projection onto check polytope is the most complicated and time-consuming operation in the alternating direction method of multipliers (ADMM) decoding for Low-Density Parity-Check (LDPC) codes. The check polytope projection penalized algorithm can avoid the tedious work of penalty parameter optimization and simplified the calculation process of check polytope projection. However, the over-punishment of check polytope projection penalized algorithm may lead to poor decoding performance, when combined with the over-relaxation technique. In this paper, an improved check polytope projection penalized algorithm is proposed. In order to reduce the ratio of even-vertex projection, we restrict the points far away from the even-vertex of the check polytope by introducing the penalty constraint condition. Simulation results show that the frame error rate (FER) performance of the proposed algorithm is almost the same as that of the cut search projection algorithm (CSA), and it can save the average decoding time by 22.9%–52%.
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.
Linear programming (LP) decoding based on the alternating direction method of multipliers (ADMM) has proved to be effective for low-density parity-check (LDPC) codes. However, for high-density parity-check (HDPC) codes, the ADMM-LP decoder encounters two problems, namely a high-density check matrix in HDPC codes and a great number of pseudocodewords in HDPC codes' fundamental polytope. The former problem makes the check polytope projection extremely complex, and the latter one leads to poor frame error rates (FER) performance. To address these issues, we introduce the even vertex algorithm (EVA) into the ADMM-LP decoding algorithm for HDPC codes, named as HDPC-EVA. HDPC-EVA can reduce the complexity of the projection process and improve the FER performance. We further enhance the proposed decoder by the automorphism groups of codes, creating diversity in the parity-check matrix. The simulation results show that the proposed decoder is capable of cutting down the average decoding time for each iteration by 30%-60%, as well as achieving near maximum likelihood (ML) performance on some BCH codes.
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.
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.