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

arXiv:cs/0507068 · IEEE Transactions on Information Theory

On Parity-Check Collections for Iterative Erasure Decoding That Correct all Correctable Erasure Patterns of a Given Size

Henk D. L. Hollmann, Ludo M. G. M. Tolhuizen

Published Jan 23, 2007• 45 citations
arXivHTMLPDF

Abstract

Recently there has been interest in the construction of small parity-check sets for iterative decoding of the Hamming code with the property that each uncorrectable (or stopping) set of size three is the support of a codeword and hence uncorrectable anyway. Here we reformulate and generalize the problem and improve on this construction. We show that a parity-check collection that corrects all correctable erasure patterns of size m for the Hamming code with codimension r provides, in fact, for all codes of codimension r a corresponding "generic" parity-check collection with this property. This leads in a natural way to a necessary and sufficient condition for such generic parity-check collections. We use this condition to construct a generic parity-check collection for codes of codimension r correcting all correctable erasure patterns of size at most m, for all r and mlesr, thus generalizing the known construction for m=3. Then we discuss optimality of our construction and show that it can be improved for mges3 and r large enough. Finally, we discuss some directions for further research

DOI
10.1109/tit.2006.888996

Related papers

Generating parity check equations for bounded-distance iterative erasure decoding

Henk D. L. Hollmann, Ludo M. G. M. Tolhuizen

A generic (r,m)-erasure correcting set is a collection of vectors in F2rwhich can be used to generate, for each binary linear code of codimension r, a collection of parity check equations that enables iterative decoding of all correctable erasure patterns of size at most m. That is to say, the only stopping sets of size at most m for the generated parity check equations are the erasure patterns for which there is more than one manner to fill in the erasures to obtain a codeword. We give an explicit construction of generic (r,m)-erasure correcting sets of cardinality Sigmai=0m-1(ir-1). Using a random-coding-like argument, we show that for fixed m, the minimum size of a generic (r,m)-erasure correcting set is linear in r

arXiv:cs/0606026•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•3 citations

Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes

Khaled Abdel-Ghaffar, Jos H. Weber

Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.

arXiv:cs/0603007•IEEE Transactions on Information Theory•Aug 29, 2007•20 citations

Small stopping sets in projective low-density parity-check codes

Yuichiro Fujiwara, Yu Tsunoda

It is known that redundant parity-check equations can improve the performance of an LDPC code by reducing the number of harmful substructures in the parity-check matrix. However, it is a difficult problem to design a parity-check matrix in such a way that it avoids substructures that are known to be harmful to iterative decoding while keeping the number of redundant parity-check equations moderate and ensuring other desirable properties. We explicitly give redundant parity-check matrices for cyclic regular LDPC codes of length n and minimum distance d ~ √n in which there are only n parity-check equations but no stopping sets of size d+1 or smaller except for those that correspond to the nonzero codewords of the smallest weight. We do this by showing that the well-known projective LDPC codes from the incidence matrices of projective planes PG(2, q) with q even have this property. This result may give insight into how the small number of redundant parity-check equations in the geometric LDPC codes may be contributing to the good performance reported in the literature. We also give a slightly improved upper bound on the size of a smallest generic erasure correcting set.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•0 citations

Improved Stopping Set Elimination by Parity-Check Matrix Extension of LDPC Codes

Saejoon Kim, Jun Heo, Hyuncheol Park

Stopping sets associated with a parity-check matrix of low-density parity-check codes limit the performance of iterative decoding over the binary erasure channel. In this letter, we propose a parity-check matrix extension scheme that eliminates stopping sets of small sizes. The results show that our proposed scheme provides significant performance improvement compared to previously known parity-check matrix extension schemes.

IEEE Communications Letters•Apr 6, 2011•6 citations

Stopping set analysis for Hamming codes

Jos H. Weber, Khaled Abdel-Ghaffar

In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three in a Hamming code. In this paper, we investigate how this number depends on the parity-check matrix used in the decoding process. First, we present basic results on stopping set enumerators for block codes in general. Next, we focus on stopping set enumerators for Hamming codes. Our main result is a parity-check matrix of relatively small size for which the number of stopping sets of size three equals the number of codewords of weight three in the Hamming code.

IEEE Information Theory Workshop (ITW)•Jan 1, 2005•26 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
Recently there has been interest in the construction of small parity-check sets for iterative decoding of the Hamming code with the property that each uncorrectable (or stopping) set of size three is the support of a codeword and hence uncorrectable anyway. Here we reformulate and generalize the problem and improve on this construction. We show that a parity-check collection that corrects all correctable erasure patterns of size m for the Hamming code with codimension r provides, in fact, for all codes of codimension r a corresponding "generic" parity-check collection with this property. This leads in a natural way to a necessary and sufficient condition for such generic parity-check collections. We use this condition to construct a generic parity-check collection for codes of codimension r correcting all correctable erasure patterns of size at most m, for all r and mlesr, thus generalizing the known construction for m=3. Then we discuss optimality of our construction and show that it can be improved for mges3 and r large enough. Finally, we discuss some directions for further research
A generic (r,m)-erasure correcting set is a collection of vectors in F2rwhich can be used to generate, for each binary linear code of codimension r, a collection of parity check equations that enables iterative decoding of all correctable erasure patterns of size at most m. That is to say, the only stopping sets of size at most m for the generated parity check equations are the erasure patterns for which there is more than one manner to fill in the erasures to obtain a codeword. We give an explicit construction of generic (r,m)-erasure correcting sets of cardinality Sigmai=0m-1(ir-1). Using a random-coding-like argument, we show that for fixed m, the minimum size of a generic (r,m)-erasure correcting set is linear in r
It is known that redundant parity-check equations can improve the performance of an LDPC code by reducing the number of harmful substructures in the parity-check matrix. However, it is a difficult problem to design a parity-check matrix in such a way that it avoids substructures that are known to be harmful to iterative decoding while keeping the number of redundant parity-check equations moderate and ensuring other desirable properties. We explicitly give redundant parity-check matrices for cyclic regular LDPC codes of length n and minimum distance d ~ √n in which there are only n parity-check equations but no stopping sets of size d+1 or smaller except for those that correspond to the nonzero codewords of the smallest weight. We do this by showing that the well-known projective LDPC codes from the incidence matrices of projective planes PG(2, q) with q even have this property. This result may give insight into how the small number of redundant parity-check equations in the geometric LDPC codes may be contributing to the good performance reported in the literature. We also give a slightly improved upper bound on the size of a smallest generic erasure correcting set.
In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three in a Hamming code. In this paper, we investigate how this number depends on the parity-check matrix used in the decoding process. First, we present basic results on stopping set enumerators for block codes in general. Next, we focus on stopping set enumerators for Hamming codes. Our main result is a parity-check matrix of relatively small size for which the number of stopping sets of size three equals the number of codewords of weight three in the 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.