IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC)

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

Ziyi Wang, Yun Jiang, Qiaoqiao Xia

Published Aug 19, 2024• 0 citations

Abstract

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

DOI: 10.1109/icspcc62635.2024.10770364

Related papers

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 AccessJan 1, 20232 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 LettersSep 11, 202012 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 LettersJul 1, 201929 citations

Fast Converging ADMM Penalized Decoding Method Based on Improved Penalty Function for LDPC Codes

Biao Wang

For low-density parity-check (LDPC) codes, the penalized decoding method based on the alternating direction method of multipliers (ADMM) can improve the decoding performance at low signal-to-noise ratios and also has low decoding complexity. There are three effective methods that could increase the ADMM penalized decoding speed, which are reducing the number of Euclidean projections in ADMM penalized decoding, designing an effective penalty function and selecting an appropriate layered scheduling strategy for message transmission. In order to further increase the ADMM penalized decoding speed, through reducing the number of Euclidean projections and using the vertical layered scheduling strategy, this paper designs a fast converging ADMM penalized decoding method based on the improved penalty function. Simulation results show that the proposed method not only improves the decoding performance but also reduces the average number of iterations and the average decoding time.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesMay 7, 20202 citations

Improved Penalty Functions of ADMM Penalized Decoder for LDPC Codes

Biao Wang, Jianjun Mu, Xiaopeng Jiao +1 more

By making the pseudocodewords more costly than codewords, the alternating direction method of multipliers (ADMM) penalized decoder can improve the error rate performances significantly for low-density parity-check (LDPC) codes at low signal-to-noise ratios. In this letter, we design two improved piecewise penalty functions for ADMM penalized decoder by increasing the slope of the penalty function at the points near x = 0 and x = 1. The improved penalty functions can punish pseudocodewords more quickly and thus increase the decoding speed. Simulation results over two LDPC codes show that the proposed method improves the error rate performances and reduces the decoding time considerably.

IEEE Communications LettersNov 10, 201622 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 LettersApr 1, 201551 citations