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

Electronics Letters

Modification of improved decoding algorithm for LDPC codes over BEC

Xiaopeng Jiao, Jianjun Mu, Luping Zhou

Published Apr 10, 2008• 1 citation
Publisher

Abstract

A modification of the improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC) is presented. The proposed modification has better performance since it decreases the number of guesses efficiently by using a new guessing set selection scheme. Simulations show that the modification decreases error rate considerably, whereas having almost the same complexity as the message passing algorithm.

DOI
10.1049/el:20080511

Related papers

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

Badri N. Vellambi, Faramarz Fekri

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates

IEEE Transactions on Information Theory•Apr 1, 2007•24 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•147 citations

An improved decoding algorithm for low-density parity-check codes over the binary erasure channel

Badri N. Vellambi, Faramarz Fekri

This paper presents a new improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). The proposed algorithm combines the fact that a considerable fraction of unsatisfied check nodes are of degree two with the concept of guessing bits to perform simple graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to present improved decoding algorithms [H. Pishro-Nik et al., 2004]. Simulations of codes of very short lengths over BEC reveal the superiority of our algorithm over present improved decoding algorithms for a wide range of bit error rates.

Globecom•Jan 1, 2005•0 citations

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

Low Decoding Complexity of LDPC Codes Over the Binary Erasure Channel

Sareh Majidi Ivari, M. Reza Soleymani, Yousef R. Shayan

In this paper, we present a new low complexity decoding algorithm outperforming existing schemes. When the Belief Propagation fails and cannot solve all the erased bits, the guessing algorithm makes assumptions on a set of erased bits. However, in our new algorithm instead of guessing the values of a set of message bits, the decoder selects a set of check nodes and makes assumption on bits connected to them. The number of possibilities is reduced by half because the field is binary resulting in lower decoding complexity. The proposed decoding algorithm is applied to two regular half rate LDPC codes with lengths of 1000 and 2000. The theoretical belief propagation (BP) threshold for these two codes is 0.429. It is shown that the actual BP threshold is improved using the new algorithm. Setting the number of possibilities to two, we achieve a threshold of 0.43 which is higher than the BP theoretical.

Iranian Conference on Electrical Engineering•May 1, 2018•0 citations

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations
A modification of the improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC) is presented. The proposed modification has better performance since it decreases the number of guesses efficiently by using a new guessing set selection scheme. Simulations show that the modification decreases error rate considerably, whereas having almost the same complexity as the message passing algorithm.
In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates
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.
This paper presents a new improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). The proposed algorithm combines the fact that a considerable fraction of unsatisfied check nodes are of degree two with the concept of guessing bits to perform simple graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to present improved decoding algorithms [H. Pishro-Nik et al., 2004]. Simulations of codes of very short lengths over BEC reveal the superiority of our algorithm over present improved decoding algorithms for a wide range of bit error rates.
In this paper, we present a new low complexity decoding algorithm outperforming existing schemes. When the Belief Propagation fails and cannot solve all the erased bits, the guessing algorithm makes assumptions on a set of erased bits. However, in our new algorithm instead of guessing the values of a set of message bits, the decoder selects a set of check nodes and makes assumption on bits connected to them. The number of possibilities is reduced by half because the field is binary resulting in lower decoding complexity. The proposed decoding algorithm is applied to two regular half rate LDPC codes with lengths of 1000 and 2000. The theoretical belief propagation (BP) threshold for these two codes is 0.429. It is shown that the actual BP threshold is improved using the new algorithm. Setting the number of possibilities to two, we achieve a threshold of 0.43 which is higher than the BP theoretical.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.