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

arXiv:1409.4760 · International Symposium on Telecommunications

A fast convergence density evolution algorithm for optimal rate LDPC codes in BEC

Hassan Tavakoli

Published Sep 1, 2014• 4 citations
arXivHTMLPDF

Abstract

We derive a new fast convergent Density Evolution algorithm for finding optimal rate Low-Density Parity-Check (LDPC) codes used over the binary erasure channel (BEC). The fast convergence property comes from the modified Density Evolution (DE), a numerical method for analyzing the behavior of iterative decoding convergence of a LDPC code. We have used the method of [16] for designing of a LDPC code with optimal rate. This has been done for a given parity check node degree distribution, erasure probability and specified DE constraint. The fast behavior of DE and found optimal rate with this method compare with the previous DE constraint.

DOI
10.1109/istel.2014.7000770

Related papers

On the Design of Fast Convergent LDPC Codes for the BEC: An Optimization Approach

Vahid Jamali, Yasser Karimian, Johannes B. Huber +1 more

The complexity-performance trade-off is a fundamental aspect of the design of low-density parity-check (LDPC) codes. In this paper, we consider LDPC codes for the binary erasure channel (BEC), use code rate for performance metric, and number of decoding iterations to achieve a certain residual erasure probability for complexity metric. We first propose a quite accurate approximation of the number of iterations for the BEC. Moreover, a simple but efficient utility function corresponding to the number of iterations is developed. Using the aforementioned approximation and the utility function, two optimization problems w.r.t. complexity are formulated to find the code degree distributions. We show that both optimization problems are convex. In particular, the problem with the proposed approximation belongs to the class of semi-infinite problems which are computationally challenging to be solved. However, the problem with the proposed utility function falls into the class of semi-definite programming (SDP) and thus, the global solution can be found efficiently using available SDP solvers. Numerical results reveal the superiority of the proposed code design compared to existing code designs from literature.

arXiv:1401.4337•IEEE Transactions on Communications•Dec 24, 2014•6 citations

On Decoding of Low-Density Parity-Check Codes Over the Binary Erasure Channel

Hossein Pishro-Nik, Faramarz Fekri

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.

IEEE Transactions on Information Theory•Mar 1, 2004•146 citations

Design of LDPC code ensembles with fast convergence properties

Ian P. Mulholland, Enrico Paolini, Mark F. Flanagan

The design of low-density parity-check (LDPC) code ensembles optimized for a finite number of decoder iterations is investigated. Our approach employs EXIT chart analysis and differential evolution to design such ensembles for the binary erasure channel and additive white Gaussian noise channel. The error rates of codes optimized for various numbers of decoder iterations are compared and it is seen that in the cases considered, the best performance for a given number of decoder iterations is achieved by codes which are optimized for this particular number. The design of generalized LDPC (GLDPC) codes is also considered, showing that these structures can offer better performance than LDPC codes for low-iteration-number designs. Finally, it is illustrated that LDPC codes which are optimized for a small number of iterations exhibit significant deviations in terms of degree distribution and weight enumerators with respect to LDPC codes returned by more conventional design tools.

arXiv:1410.4086•IEEE International Black Sea Conference on Communications and Networking•May 1, 2015•18 citations

Statistical-Based Density Evolution Algorithm for Nonbinary Low-Density Parity-Check Codes

Jie Wu, Minjian Zhao, Jie Zhong +2 more

A statistical-based density evolution algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. It is applicable to both regular and irregular codes under study. The algorithm proposed serves as a tool to analyze the performance limit for iterative decoding of nonbinary LDPC codes, which in turn guides code design. Specifically, it provides approximated evaluations of convergence thresholds for codes given specific degree distributions. It is shown that, for a class of quasi-cyclic (QC) structured extended irregular repeat-accumulate (SeIRA) nonbinary LDPC codes, degree distributions can be optimized via the algorithm proposed. Simulation results exhibit that the nonbinary LDPC codes designed outperform the optimized binary LDPC codes on the AWGN channel with similar code length and rate in terms of bits. Performance gap between the binary and nonbinary LDPC codes is larger in the scenario of higher order modulation.

IEEE Vehicular Technology Conference•Sep 1, 2011•1 citation

A Decoding Method of Low-Density Parity-Check Codes Over the Binary Erasure Channel

Gou Hosoya, Toshiyasu Matsushima, Shigeichi Hirasawa

We propose a new decoding algorithm of LDPC codes over the binary erasure channel (BEC). The proposed decoding algorithm is an iterative one which uses the sparse- ness structure of the parity-check matrix of LDPC codes. We show by simulation results that the proposed decoding algorithm and the conventional decoding algorithm have a trade-o between remaining erasure rate and complexity.

IEEE International Symposium on Information Theory (ISIT)•Dec 14, 2004•6 citations

Optimal Puncturing of Block-Type LDPC Codes and Their Fast Convergence Decoding

Song‐Nam Hong, Hyeong‐Gun Joo, Dong‐Joon Shin

In this paper, we study and propose a puncturing algorithm of block-type low-density parity-check (B-LDPC) codes. This optimal puncturing algorithm is derived from the fact that puncturing of parity bits is equivalent to merging the check nodes. Furthermore, we propose a new decoding algorithm suitable for the punctured B-LDPC codes. This decoding algorithm needs not only smaller number of operations at each iteration, but also shows faster decoding convergence speed than the conventional erasure decoding algorithm. If the optimally punctured B-LDPC code is decoded by the new decoding algorithm, it results in the same performance as the unpunctured B-LDPC code of the same code rate.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•8 citations
We derive a new fast convergent Density Evolution algorithm for finding optimal rate Low-Density Parity-Check (LDPC) codes used over the binary erasure channel (BEC). The fast convergence property comes from the modified Density Evolution (DE), a numerical method for analyzing the behavior of iterative decoding convergence of a LDPC code. We have used the method of [16] for designing of a LDPC code with optimal rate. This has been done for a given parity check node degree distribution, erasure probability and specified DE constraint. The fast behavior of DE and found optimal rate with this method compare with the previous DE constraint.
The complexity-performance trade-off is a fundamental aspect of the design of low-density parity-check (LDPC) codes. In this paper, we consider LDPC codes for the binary erasure channel (BEC), use code rate for performance metric, and number of decoding iterations to achieve a certain residual erasure probability for complexity metric. We first propose a quite accurate approximation of the number of iterations for the BEC. Moreover, a simple but efficient utility function corresponding to the number of iterations is developed. Using the aforementioned approximation and the utility function, two optimization problems w.r.t. complexity are formulated to find the code degree distributions. We show that both optimization problems are convex. In particular, the problem with the proposed approximation belongs to the class of semi-infinite problems which are computationally challenging to be solved. However, the problem with the proposed utility function falls into the class of semi-definite programming (SDP) and thus, the global solution can be found efficiently using available SDP solvers. Numerical results reveal the superiority of the proposed code design compared to existing code designs from literature.
This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.
The design of low-density parity-check (LDPC) code ensembles optimized for a finite number of decoder iterations is investigated. Our approach employs EXIT chart analysis and differential evolution to design such ensembles for the binary erasure channel and additive white Gaussian noise channel. The error rates of codes optimized for various numbers of decoder iterations are compared and it is seen that in the cases considered, the best performance for a given number of decoder iterations is achieved by codes which are optimized for this particular number. The design of generalized LDPC (GLDPC) codes is also considered, showing that these structures can offer better performance than LDPC codes for low-iteration-number designs. Finally, it is illustrated that LDPC codes which are optimized for a small number of iterations exhibit significant deviations in terms of degree distribution and weight enumerators with respect to LDPC codes returned by more conventional design tools.
A statistical-based density evolution algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. It is applicable to both regular and irregular codes under study. The algorithm proposed serves as a tool to analyze the performance limit for iterative decoding of nonbinary LDPC codes, which in turn guides code design. Specifically, it provides approximated evaluations of convergence thresholds for codes given specific degree distributions. It is shown that, for a class of quasi-cyclic (QC) structured extended irregular repeat-accumulate (SeIRA) nonbinary LDPC codes, degree distributions can be optimized via the algorithm proposed. Simulation results exhibit that the nonbinary LDPC codes designed outperform the optimized binary LDPC codes on the AWGN channel with similar code length and rate in terms of bits. Performance gap between the binary and nonbinary LDPC codes is larger in the scenario of higher order modulation.
In this paper, we study and propose a puncturing algorithm of block-type low-density parity-check (B-LDPC) codes. This optimal puncturing algorithm is derived from the fact that puncturing of parity bits is equivalent to merging the check nodes. Furthermore, we propose a new decoding algorithm suitable for the punctured B-LDPC codes. This decoding algorithm needs not only smaller number of operations at each iteration, but also shows faster decoding convergence speed than the conventional erasure decoding algorithm. If the optimally punctured B-LDPC code is decoded by the new decoding algorithm, it results in the same performance as the unpunctured B-LDPC code of the same code rate.