IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

An Enhanced HDPC-EVA Decoder Based on ADMM

Yujin Zheng, Yan Lin, Zhuo Zhang, Qinglin Zhang, Qiaoqiao Xia

Published Apr 1, 2021• 5 citations

Abstract

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.

DOI: 10.1587/transfun.2020eal2116

Related papers

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

Low-Density Parity-Check Decoding Algorithm Based on Symmetric Alternating Direction Method of Multipliers

Ji Zhang, Anmin Chen, Ying Zhang +3 more

The Alternating Direction Method of Multipliers (ADMM) has proven to be an efficient approach for implementing linear programming (LP) decoding of low-density parity-check (LDPC) codes. By introducing penalty terms into the LP decoding model's objective function, ADMM-based variable node penalized decoding effectively mitigates non-integral solutions, thereby improving frame error rate (FER) performance, especially in the low signal-to-noise ratio (SNR) region. In this paper, we leverage the ADMM framework to derive explicit iterative steps for solving the LP decoding problem for LDPC codes with penalty functions. To further enhance decoding efficiency and accuracy, We propose an LDPC code decoding algorithm based on the symmetric ADMM (S-ADMM). We also establish some contraction properties satisfied by the iterative sequence of the algorithm. Through simulation experiments, we evaluate the proposed S-ADMM decoder using three standard LDPC codes and three representative fifth-generation (5G) codes. The results show that the S-ADMM decoder consistently outperforms conventional ADMM penalized decoders, offering significant improvements in decoding performance.

EntropyApr 9, 20251 citation

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.07806IEEE Wireless Communications LettersMar 12, 201921 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, 20230 citations

Improved Free-of-CPP ADMM-Based Iterative Decoding Algorithm of Binary LDPC Codes

Jing Bai, Zedong An, Yuhao Chi +2 more

Iterative decoding algorithms based on the alternating direction method of multipliers (ADMM) decoding of low density parity check (LDPC) codes has emerged as an alternating decoding method and bringed a boom of research on drawing upon mathematical optimization to LDPC decoding. Improving error-correcting performance is a key issue to enhance the superiority of ADMM decoding. In this letter, we investigate an efficient ADMM-based iterative decoder for binary LDPC codes. First, we build an mathematical programming equivalence of the maximum likelihood (ML) decoding problem by transforming parity-check constraints to multiple equivalent linear constraints and eliminating check-polytope projection (CPP). Then, an iterative algorithm based on ADMM technique is developed to solve this free-of-CPP (FCPP) equivalence and each ADMM update can be computed efficiently. Moreover, the proposed ADMM-FCPP decoding algorithm is analyzed to display a linear complexity to the length of the LDPC code at each iteration. Finally, simulation results demonstrate the superiority of the proposed decoder in error-correcting performance compared with the state-of-the-art ADMM-based decoders.

IEEE Signal Processing LettersDec 4, 20243 citations

ADMM LP Decoding of Non-Binary LDPC Codes in $ \mathbb {F}_{2^{m}}$

Xishuo Liu, Stark Christiaan Draper

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in F2m to a set of constraints in F2that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.

IEEE Transactions on Information TheoryApr 15, 201610 citations