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 Signal Processing Letters

Memory-Reduced Look-Up Tables for Efficient ADMM Decoding of LDPC Codes

Xiaopeng Jiao, Yucheng He, Jianjun Mu

Published Oct 2, 2017• 19 citations
Publisher

Abstract

The Euclidean projection involved in the decoding of low-density parity-check (LDPC) codes with the alternating direction method of multipliers (ADMM) can be simplified by jointly using uniform quantization and look-up tables (LUTs). However, the memory requirement for the original LUT-based ADMM decoding is comparatively large. In this letter, a nonuniform quantization method is proposed to save the memory cost by minimizing the mean square error of the outputs of Euclidean projections during quantization. Simulation results over two exemplified LDPC codes show that the proposed method can achieve similar error-rate performances when compared with the original LUT-based ADMM decoding by using significantly less memory units.

DOI
10.1109/lsp.2017.2758809

Related papers

Efficient ADMM Decoding of LDPC Codes Using Lookup Tables

Xiaopeng Jiao, Jianjun Mu, Yucheng He +1 more

Linear programming decoding with the alternating direction method of multipliers (ADMM) is a promising decoding technique for low-density parity-check (LDPC) codes, where the computational complexity of Euclidean projections onto check polytopes becomes a prominent problem. In this paper, the problem is circumvented by building lookup tables (LUTs) and quantizing the inputs to approach approximate Euclidean projections at low computational complexities. To challenge the huge memory cost of LUTs, we first propose two commutative compositions of Euclidean projection and self-map, and show the existence of a small quantization range which does not alter the Euclidean projection. Then, we investigate the design and simplification of the LUTs by exploiting the commutative compositions and check node decomposition techniques. An efficient algorithm for the LUT-based projection is demonstrated by using one simplification method. Simulation results show that for both the regular and irregular LDPC codes, the ADMM decoding using LUT-based projection can substantially reduce the decoding time while maintaining the error rate performance at a comparatively large memory cost.

IEEE Transactions on Communications•Jan 26, 2017•40 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•52 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

Efficient ADMM Decoder for Binary LDPC Codes in Low-Iteration Regime

Yuxin Cheng, Yujie Ma, Qinglin Zhang +1 more

The alternating direction method of multipliers (ADMM) algorithm for decoding low-density parity-check (LDPC) codes has attracted significant attention because of its superior performance. The convergence characteristic has been regarded as a crucial element to enhance its advantage in practice. In this paper, an efficient ADMM decoder for binary LDPC codes is proposed by adjusting the position of the Euclidean projection to enhance the convergence behavior. The simulation results show that the proposed algorithm can improve the FER performance by 1.1dB as well as save average decoding iterations by 13% compared with the existing CSA when the maximum number of iterations is set to 20. The proposed algorithm can be suitable for use at low-iteration regime in high-throughput scenarios.

IEEE Communications Letters•Jul 2, 2025•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

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
The Euclidean projection involved in the decoding of low-density parity-check (LDPC) codes with the alternating direction method of multipliers (ADMM) can be simplified by jointly using uniform quantization and look-up tables (LUTs). However, the memory requirement for the original LUT-based ADMM decoding is comparatively large. In this letter, a nonuniform quantization method is proposed to save the memory cost by minimizing the mean square error of the outputs of Euclidean projections during quantization. Simulation results over two exemplified LDPC codes show that the proposed method can achieve similar error-rate performances when compared with the original LUT-based ADMM decoding by using significantly less memory units.
Linear programming decoding with the alternating direction method of multipliers (ADMM) is a promising decoding technique for low-density parity-check (LDPC) codes, where the computational complexity of Euclidean projections onto check polytopes becomes a prominent problem. In this paper, the problem is circumvented by building lookup tables (LUTs) and quantizing the inputs to approach approximate Euclidean projections at low computational complexities. To challenge the huge memory cost of LUTs, we first propose two commutative compositions of Euclidean projection and self-map, and show the existence of a small quantization range which does not alter the Euclidean projection. Then, we investigate the design and simplification of the LUTs by exploiting the commutative compositions and check node decomposition techniques. An efficient algorithm for the LUT-based projection is demonstrated by using one simplification method. Simulation results show that for both the regular and irregular LDPC codes, the ADMM decoding using LUT-based projection can substantially reduce the decoding time while maintaining the error rate performance at a comparatively large memory cost.
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.
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.
The alternating direction method of multipliers (ADMM) algorithm for decoding low-density parity-check (LDPC) codes has attracted significant attention because of its superior performance. The convergence characteristic has been regarded as a crucial element to enhance its advantage in practice. In this paper, an efficient ADMM decoder for binary LDPC codes is proposed by adjusting the position of the Euclidean projection to enhance the convergence behavior. The simulation results show that the proposed algorithm can improve the FER performance by 1.1dB as well as save average decoding iterations by 13% compared with the existing CSA when the maximum number of iterations is set to 20. The proposed algorithm can be suitable for use at low-iteration regime in high-throughput scenarios.
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%.
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.