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 International Symposium on Information Theory (ISIT)

On the error correction of regular LDPC codes using the flipping algorithm

David Burshtein

Published Jun 1, 2007• 7 citations
Publisher

Abstract

We apply the iterative bit flipping algorithm to the standard regular low-density parity-check (LDPC) code ensemble. In the past it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct all error patterns with some linear (in the block length) number of errors. We extend this result to the case where the left degree is at least four. For the case where the left degree is larger than four, we obtain an improvement of several orders of magnitude compared to the existing results on the fraction of worst case errors that can be corrected. We also show how our results can be improved when we consider random errors (as opposed to worst case errors) produced by the channel.

DOI
10.1109/isit.2007.4557085

Related papers

On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm

David Burshtein

The iterative bit flipping algorithm is applied to the standard regular low-density parity-check (LDPC) code ensemble. In the past, it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct a linear (in the block length) number of worst case errors. In this paper, this result is extended to the case where the left degree is at least four. For the case where the left degree is larger than four, an improvement, compared to existing results, of several orders of magnitude is obtained on the fraction of worst case errors that can be corrected. It is also shown how the results can be further improved when random errors produced by the channel (as opposed to worst case errors) are considered.

IEEE Transactions on Information Theory•Jan 29, 2008•43 citations

On the Error Correction of Iterative Bounded Distance Decoding of Generalized LDPC Codes

David Burshtein

Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.

arXiv:2507.12073•IEEE Transactions on Information Theory•Sep 16, 2025•0 citations

On the error-correcting capability of LDPC codes

Kamil Sh. Zigangirov, A. E. Pusane, D. K. Zigangirov +1 more

We consider the ensemble of low-density parity-check (LDPC) codes introduced by Gallager [1]. The Zyablov-Pinsker majority-logic iterative algorithm [2] for decoding LDPC codes is analyzed on the binary symmetric channel. An analytical lower bound on the error-correcting capability τ max that grows linearly in the code block length is obtained.

Problems of Information Transmission•Sep 1, 2008•11 citations

Performance Study and Synthesis of the New LDPC Error Correcting Code Using the Bit-Flipping Algorithm

Lagrini Lakbir, El Habti El Idrissi Anas, Moulay Brahim Sedra

The discovery in 1993 of the turbo codes Berrou C., A. and P. Glavieux Thitimajshima at the International Conférence of Communication Florida has revolutionized communication. This innovation made it possible to rediscovery the error correcting codes invented by Robert Gallager in 1963 and rediscovered by Mackay in 1995, currently called Low Density Parity Check (LDPC). This code is one of the error correction codes introduced by the transmission channel that have the fastest and most effective level of protection and correction of the information transmitted during the communication. This code has been almost generalized in communication standards such as satellites. The objective of our article is to minimize the number of iterations and in some cases completely remove the iteration produced by the LDPC code bit flipping algorithm. The result of this algorithm, if we take for example the LDPC code (n, k), the number of possible syndromes which we can find is 2k-1 and for each syndrome different from zero, we can do almost four iterations to correct the errors, which gives 4x(2k-1) iterations in totality. On the other hand, the proposed algorithm removes the iteration for k syndromes and reduces iterations for the rest of the cases from four to two iterations. This study of the new design gave more performance results and the results of the simulation below according to a hardware description language used in digital electronics using quartus software tools show the importance of this algorithm.

Universal Journal of Electrical and Electronic Engineering•Apr 1, 2020•0 citations

Guaranteed error correction of faulty bit-flipping decoders under data-dependent gate failures

Srdan S. Brkic, Predrag Ivaniš, Bane V. Vasic

In this paper we analyze the effect of hardware unreliability to performance of bit-flipping decoders of low-density parity-check (LDPC) codes. We apply expander arguments to show that the simple parallel bit flipping decoder, built partially from faulty gates, can correct a linear fraction of worst case channel errors, when gate failures are correlated and dependent on the switching activity of logic gates. In addition, we provide a lower bound on the guaranteed error correction of LDPC codes with left degree of at least eight.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 citations

On the asymptotic performance of low-complexity decoded LDPC codes with constituent hamming codes

Victor Zyablov, Maja Lončar, Rolf Johannesson +1 more

Hamming code-based LDPC (H-LDPC) block codes are obtained by replacing single parity-check codes in Gallager’s LDPC codes with Hamming constituent codes. This paper investigates the asymptotic error-correcting capabilities of ensembles of random H-LDPC codes, used over the binary symmetric channel and decoded with a low-complexity hard-decision iterative decoding algorithm. The number of required decoding iterations is a logarithmic function of the code length. It is shown that there exist H-LDPC codes for which such an iterative decoding corrects any error pattern with a number of errors that grows linearly with the code length. For various choices of code parameters the results are supported by numerical examples.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•5 citations
We apply the iterative bit flipping algorithm to the standard regular low-density parity-check (LDPC) code ensemble. In the past it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct all error patterns with some linear (in the block length) number of errors. We extend this result to the case where the left degree is at least four. For the case where the left degree is larger than four, we obtain an improvement of several orders of magnitude compared to the existing results on the fraction of worst case errors that can be corrected. We also show how our results can be improved when we consider random errors (as opposed to worst case errors) produced by the channel.
The iterative bit flipping algorithm is applied to the standard regular low-density parity-check (LDPC) code ensemble. In the past, it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct a linear (in the block length) number of worst case errors. In this paper, this result is extended to the case where the left degree is at least four. For the case where the left degree is larger than four, an improvement, compared to existing results, of several orders of magnitude is obtained on the fraction of worst case errors that can be corrected. It is also shown how the results can be further improved when random errors produced by the channel (as opposed to worst case errors) are considered.
Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.
The discovery in 1993 of the turbo codes Berrou C., A. and P. Glavieux Thitimajshima at the International Conférence of Communication Florida has revolutionized communication. This innovation made it possible to rediscovery the error correcting codes invented by Robert Gallager in 1963 and rediscovered by Mackay in 1995, currently called Low Density Parity Check (LDPC). This code is one of the error correction codes introduced by the transmission channel that have the fastest and most effective level of protection and correction of the information transmitted during the communication. This code has been almost generalized in communication standards such as satellites. The objective of our article is to minimize the number of iterations and in some cases completely remove the iteration produced by the LDPC code bit flipping algorithm. The result of this algorithm, if we take for example the LDPC code (n, k), the number of possible syndromes which we can find is 2k-1 and for each syndrome different from zero, we can do almost four iterations to correct the errors, which gives 4x(2k-1) iterations in totality. On the other hand, the proposed algorithm removes the iteration for k syndromes and reduces iterations for the rest of the cases from four to two iterations. This study of the new design gave more performance results and the results of the simulation below according to a hardware description language used in digital electronics using quartus software tools show the importance of this algorithm.
In this paper we analyze the effect of hardware unreliability to performance of bit-flipping decoders of low-density parity-check (LDPC) codes. We apply expander arguments to show that the simple parallel bit flipping decoder, built partially from faulty gates, can correct a linear fraction of worst case channel errors, when gate failures are correlated and dependent on the switching activity of logic gates. In addition, we provide a lower bound on the guaranteed error correction of LDPC codes with left degree of at least eight.
Hamming code-based LDPC (H-LDPC) block codes are obtained by replacing single parity-check codes in Gallager’s LDPC codes with Hamming constituent codes. This paper investigates the asymptotic error-correcting capabilities of ensembles of random H-LDPC codes, used over the binary symmetric channel and decoded with a low-complexity hard-decision iterative decoding algorithm. The number of required decoding iterations is a logarithmic function of the code length. It is shown that there exist H-LDPC codes for which such an iterative decoding corrects any error pattern with a number of errors that grows linearly with the code length. For various choices of code parameters the results are supported by numerical examples.