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

International Symposium on Turbo Codes and Iterative Information Processing

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

Victor Zyablov, Maja Lončar, Rolf Johannesson, Pavel S. Rybin

Published Sep 1, 2008• 5 citations
Publisher

Abstract

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.

DOI
10.1109/turbocoding.2008.4658693

Related papers

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

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

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

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

Alexey Frolov, Victor Zyablov

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.

Problems of Information Transmission•Jun 1, 2010•16 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

The error-correcting capabilities of low-complexity decoded H-LDPC code as irregular LDPC code

Pavel S. Rybin

This paper deals with the Low-Density Parity-Check codes with the constituent Hamming codes (H-LDPC codes) and two different iterative hard-decision low-complexity decoding algorithms. Both algorithms are based on the same main idea: the decreasing of the syndrome weight on each step of the decoding algorithm. The first decoding algorithm uses the properties of the constituent Hamming code. The best known lower-bound on the guaranteed corrected errors fraction for the H-LDPC codes under the first decoding algorithm was obtained in 2011. The second decoding algorithm considers H-LDPC as the irregular LDPC code and uses the well-known majority decoding algorithm. The lower-bound on the guaranteed corrected errors fraction for H-LDPC code under the second decoding algorithm is introduced for the first time in this paper. Numerical results for the lower-bound, obtained in this paper for H-LDPC code under the second decoding algorithm, significantly exceed the numerical results for the best known lower-bounds, obtained previously for H-LDPC code under the first decoding algorithm.

International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)•Jun 1, 2014•0 citations
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.
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.
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.
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.
This paper deals with the Low-Density Parity-Check codes with the constituent Hamming codes (H-LDPC codes) and two different iterative hard-decision low-complexity decoding algorithms. Both algorithms are based on the same main idea: the decreasing of the syndrome weight on each step of the decoding algorithm. The first decoding algorithm uses the properties of the constituent Hamming code. The best known lower-bound on the guaranteed corrected errors fraction for the H-LDPC codes under the first decoding algorithm was obtained in 2011. The second decoding algorithm considers H-LDPC as the irregular LDPC code and uses the well-known majority decoding algorithm. The lower-bound on the guaranteed corrected errors fraction for H-LDPC code under the second decoding algorithm is introduced for the first time in this paper. Numerical results for the lower-bound, obtained in this paper for H-LDPC code under the second decoding algorithm, significantly exceed the numerical results for the best known lower-bounds, obtained previously for H-LDPC code under the first decoding algorithm.