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

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

Victor Zyablov, Rolf Johannesson, Matea Lončar

Published Jun 1, 2009• 17 citations
Publisher

Abstract

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.

DOI
10.1134/s0032946009020021

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

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

Erasure correction by low-density codes

Victor Zyablov, Pavel S. Rybin

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is 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. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

Problems of Information Transmission•Sep 1, 2009•6 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

On the Number of Errors Correctable with Codes on Graphs

Alexander Barg, Arya Mazumdar

We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to codes on hypergraphs. It is known that the average minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes can correct a linearly growing number of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum distance. Previously known results that proved this property for graph codes relied on graph expansion and required the choice of local codes with large distance relative to their length.

arXiv:0911.4522•IEEE Transactions on Information Theory•Jan 21, 2011•12 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
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.
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.
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.
We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is 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. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.
We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to codes on hypergraphs. It is known that the average minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes can correct a linearly growing number of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum distance. Previously known results that proved this property for graph codes relied on graph expansion and required the choice of local codes with large distance relative to their length.
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.