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

Problems of Information Transmission

Asymptotic estimation of the fraction of errors correctable by q-ary LDPC codes

Alexey Frolov, Victor Zyablov

Published Jun 1, 2010• 16 citations
Publisher

Abstract

We consider an ensemble of random q -ary LDPC codes. As constituent codes, we use q -ary single-parity-check codes with d = 2 and Reed-Solomon codes with d = 3. We propose a hard-decision iterative decoding algorithm with the number of iterations of the order of the logarithm of the code length. We show that under this decoding algorithm there are codes in the ensemble with the number of correctable errors linearly growing with the code length. We weaken a condition on the vertex expansion of the Tanner graph corresponding to the code.

DOI
10.1134/s0032946010020043

Related papers

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

Asymptotic estimation of error fraction corrected by binary LDPC code

Pavel S. Rybin, Victor Zyablov

This paper considers new lower bound on fraction of guaranteed corrected errors while decoding the same binary low-density parity-check (LDPC) codes with constituent single parity-check (SPC) and Hamming codes using the same iterative low-complex hard-decision algorithm as in previous works of V. Zyablov and M. Pinsker in 1975 and V. Zyablov, R. Johannesson and M. Loncar in 2009. The number of decoding iterations, required to correct the errors, is a logarithmic function of the code length. The fraction of guaranteed correctable errors computed numerically for various choices of LDPC code parameters with constituent SPC and Hamming codes shows that proposed lower bound gives the better results than previously known best lower bounds obtained by V. Zyablov and M. Pinsker in 1975 for Gallager's LDPC codes and A. Barg and A. Mazumrad for Hamming code-based LDPC (H-LDPC) codes in 2011. Some of obtained numerical results are represented at the end of the paper to demonstrate these improvements.

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

Low-complexity error correction of Hamming-code-based LDPC codes

Victor Zyablov, Rolf Johannesson, Matea Lončar

Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.

Problems of Information Transmission•Jun 1, 2009•17 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 erasure-correcting capabilities of low-complexity decoded LDPC codes with constituent Hamming codes

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

Low-density parity-check (LDPC) codes can be constructed using constituent block codes other than single parity-check (SPC) codes. This paper considers random LDPC codes with constituent Hamming codes and investigates their asymptotic performance over the binary erasure channel. It is shown that there exist Hamming code-based LDPC codes which, when decoded with a low-complexity iterative algorithm, are capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. The fraction of correctable erasures is computed numerically for various choices of code parameters.

•Jan 1, 2008•6 citations

Analysis of the relation between properties of LDPC codes and the tanner graph

Victor Zyablov, Pavel S. Rybin

A new method for estimating the number of errors guaranteed to be corrected by a low-density parity-check code is proposed. The method is obtained by analyzing edges with special properties of an appropriate Tanner graph. In this paper we consider binary LDPC codes with constituent single-parity-check and Hamming codes and an iterative decoding algorithm. Numerical results obtained for the proposed lower bound exceed similar results for the best previously known lower bounds.

Problems of Information Transmission•Oct 1, 2012•8 citations
We consider an ensemble of random q -ary LDPC codes. As constituent codes, we use q -ary single-parity-check codes with d = 2 and Reed-Solomon codes with d = 3. We propose a hard-decision iterative decoding algorithm with the number of iterations of the order of the logarithm of the code length. We show that under this decoding algorithm there are codes in the ensemble with the number of correctable errors linearly growing with the code length. We weaken a condition on the vertex expansion of the Tanner graph corresponding to the code.
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.
This paper considers new lower bound on fraction of guaranteed corrected errors while decoding the same binary low-density parity-check (LDPC) codes with constituent single parity-check (SPC) and Hamming codes using the same iterative low-complex hard-decision algorithm as in previous works of V. Zyablov and M. Pinsker in 1975 and V. Zyablov, R. Johannesson and M. Loncar in 2009. The number of decoding iterations, required to correct the errors, is a logarithmic function of the code length. The fraction of guaranteed correctable errors computed numerically for various choices of LDPC code parameters with constituent SPC and Hamming codes shows that proposed lower bound gives the better results than previously known best lower bounds obtained by V. Zyablov and M. Pinsker in 1975 for Gallager's LDPC codes and A. Barg and A. Mazumrad for Hamming code-based LDPC (H-LDPC) codes in 2011. Some of obtained numerical results are represented at the end of the paper to demonstrate these improvements.
Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.
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.
Low-density parity-check (LDPC) codes can be constructed using constituent block codes other than single parity-check (SPC) codes. This paper considers random LDPC codes with constituent Hamming codes and investigates their asymptotic performance over the binary erasure channel. It is shown that there exist Hamming code-based LDPC codes which, when decoded with a low-complexity iterative algorithm, are capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. The fraction of correctable erasures is computed numerically for various choices of code parameters.