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

Scientific Reports

Improved approximate check polytope projection algorithm of ADMM penalized decoding for LDPC codes in IoTs

Yue Zhao, Biao Wang

Published Apr 17, 2025• 1 citation
Publisher

Abstract

The alternating direction method of multipliers (ADMM) penalized decoding method is a popular technology for low-density parity-check (LDPC) codes in Internet of Things (IoT) communications. In this method, Euclidean projection is a key factor affecting computational complexity. Existing projection algorithms require either sorting operation or iterative execution, resulting in greater computational complexity. By binarizing the indicator vector, this paper proposes an improved approximate check polytope projection algorithm (I-APPA) to improve projection efficiency. The simulation results indicate that I-APPA can reduce calculation steps and improve projection efficiency. Therefore, the proposed I-APPA algorithm is convenient for hardware implementation in IoT devices.

DOI
10.1038/s41598-025-97807-5

Related papers

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

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

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

Novel Early Termination Method of an ADMM-Penalized Decoder for LDPC Codes in the IoT

Biao Wang

As a critical communication technology, low-density parity-check (LDPC) codes are widely concerned with the Internet of things (IoT). To increase the convergence rate of the alternating direction method of multiplier (ADMM)-penalized decoder for LDPC codes, a novel early termination (ET) method is presented by computing the average sum of the hard decision (ASHD) during each ADMM iteration. In terms of the flooding scheduling and layered scheduling ADMM-penalized decoders, the simulation results show that the proposed ET method can significantly reduce the average number of iterations at low signal-to-noise ratios (SNRs) with negligible decoding performance loss.

Security and Communication Networks•Oct 14, 2022•0 citations
The alternating direction method of multipliers (ADMM) penalized decoding method is a popular technology for low-density parity-check (LDPC) codes in Internet of Things (IoT) communications. In this method, Euclidean projection is a key factor affecting computational complexity. Existing projection algorithms require either sorting operation or iterative execution, resulting in greater computational complexity. By binarizing the indicator vector, this paper proposes an improved approximate check polytope projection algorithm (I-APPA) to improve projection efficiency. The simulation results indicate that I-APPA can reduce calculation steps and improve projection efficiency. Therefore, the proposed I-APPA algorithm is convenient for hardware implementation in IoT devices.
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.
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.
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.
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%.
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.
As a critical communication technology, low-density parity-check (LDPC) codes are widely concerned with the Internet of things (IoT). To increase the convergence rate of the alternating direction method of multiplier (ADMM)-penalized decoder for LDPC codes, a novel early termination (ET) method is presented by computing the average sum of the hard decision (ASHD) during each ADMM iteration. In terms of the flooding scheduling and layered scheduling ADMM-penalized decoders, the simulation results show that the proposed ET method can significantly reduce the average number of iterations at low signal-to-noise ratios (SNRs) with negligible decoding performance loss.