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 Transactions on Information Theory

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

Badri N. Vellambi, Faramarz Fekri

Published Apr 1, 2007• 24 citations
Publisher

Abstract

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

DOI
10.1109/tit.2007.892812

Related papers

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

Modification of improved decoding algorithm for LDPC codes over BEC

Xiaopeng Jiao, Jianjun Mu, Luping Zhou

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.

Electronics Letters•Apr 10, 2008•1 citation

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

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

Finite-length analysis of turbo decoding on the binary erasure channel

Eirik Rosnes, Øyvind Ytrehus

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•4 citations

Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary Erasure Channels

Chih-chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications

arXiv:cs/0605086•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•8 citations
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 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.
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.
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.
This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results
Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications