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

Erasure correction by low-density codes

Victor Zyablov, Pavel S. Rybin

Published Sep 1, 2009• 6 citations
Publisher

Abstract

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.

DOI
10.1134/s0032946009030028

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

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

Decoding of low-density codes with parity-check matrices composed of permutation matrices in an erasure channel

D. K. Zigangirov, Kamil Sh. Zigangirov

A lower bound for the number of iteratively correctable erasures is given, with application to the ensemble of LDPC codes with parity-check matrices composed of permutation matrices [1]. We assume that the Zyablov-Pinsker iterative decoding algorithm [2] is used. Its complexity is O ( N log N ), where N is the block length.

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

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

Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm

Pavel S. Rybin

This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.

Journal of Communications Technology and Electronics•Dec 1, 2016•2 citations
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.
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.
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.
This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.