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

Lower Bounds on Stopping Distance of Linear Codes and Their Applications

Mingrui Zhu, K.M. Chugg

Published Sep 28, 2005• 0 citations
OpenAlex

Abstract

One of the most important open problems in the communication society is to determine the performance of iterative message passing algorithms over loopy graphs.Some recent work addresses this problem for loopy Tanner graphs by introducing the concepts of stopping distance and stopping redundancy.By analyzing the eigenvalues and eigenvectors of the normalized incidence matrix representing a Tanner graph, we derive lower bounds on its stopping distance.Using these lower bounds, an upper bound on stopping redundancy of the difference-set codes is derived as well.

Related papers

Bounds on the Expansion Properties of Tanner Graphs

Mingrui Zhu, K.M. Chugg

This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).

IEEE Transactions on Information Theory•Dec 1, 2007•3 citations

On the stopping distance and the stopping redundancy of codes

M. Schwartz, Alexander Vardy

It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of Copf, defined as the minimum number of rows in a parity- check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely, s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes

arXiv:cs/0503058•IEEE Transactions on Information Theory•Mar 1, 2006•176 citations

On the stopping distance and the stopping redundancy of codes

M. Schwartz, Alexander Vardy

It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s = d. We thus introduce a new parameter, termed the stopping redundancy of Copf, defined as the minimum number of rows in a parity-check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely s(H) = d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•27 citations

Code representation and performance of graph -based decoding

Junsheng Han

Key to the success of modern error correcting codes is the effectiveness of message-passing iterative decoding (MPID). Unlike maximum-likelihood (ML) decoding, the performance of MPID depends not only on the code, but on how the code is represented. In particular, the performance of MPID is potentially improved by using a redundant representation. We focus on Tanner graphs and study combinatorial structures therein that help explain the performance disparity among different representations of the same code. Emphasis is placed on the complexity- performance tradeoff, as more and more check nodes are allowed in the graph. Our discussion applies to MPID as well as linear programming decoding (LPD), which we collectively refer to as graph-based decoding. On an erasure channel, it is well-known that the performance of MPID or LPD is determined by stopping sets. Following Schwartz and Vardy, we define the stopping redundancy as the smallest number of check nodes in a Tanner graph such that smallest size of a non-empty stopping set is equal to the minimum Hamming distance of the code. Roughly speaking, stopping redundancy measures the complexity requirement (in number of check nodes) for MPID of a redundant graph representation to achieve performance comparable to ML decoding (up to a constant factor for small channel erasure probability). General upper bounds on stopping redundancy are obtained. One of our main contribution is a new upper bound based on probabilistic analysis, which is shown to be by far the strongest. From this bound, it can be shown, for example, that for a fixed minimum distance, the stopping redundancy grows just linearly with the redundancy (codimension). Specific results on the stopping redundancy of Golay and Reed-Muller codes are also obtained. We show that the stopping redundancy of maximum distance separable (MDS) codes is bounded in between a Turan number and a single-exclusion (SE) number --- a purely combinatorial quantity that we introduce. By studying upper bounds on the SE number, new results on the stopping redundancy of MDS codes are obtained. Schwartz and Vardy conjecture that the stopping redundancy of an MDS code should only depend on its length and minimum distance. Our results provide partial confirmation, both exact and asymptotic, to this conjecture. Stopping redundancy can be large for some codes. We observe that significantly fewer checks are needed if a small number of small stopping sets are allowed. These small stopping sets can then be dealt with by ̀g̀uessing'' during the iterative decoding process. Correspondingly, the guess-g stopping redundancy is defined and it is shown that the savings in number of required check nodes are potentially significant. Another theoretically interesting question is when MPID of a Tanner graph achieves the same word error rate an ML decoder. This prompts us to define and study ML redundancy. Applicability and possible extensions of the current work to a non-erasure channel are discussed. A framework based on pseudo-codewords is considered and shown to be relevant. However, it is also observed that the polytope characterization of pseudo-codewords is not complete enough to be an accurate indicator of MPID performance. Finally, in a separate piece of work, the probability of undetected error (PUE) for over-extended Reed-Solomon codes is studied through the weight distribution bounds of the code. The resulting PUE expressions are shown to be tight in a well-defined sense

•Jan 1, 2008•0 citations

Improved Probabilistic Bounds on Stopping Redundancy

Junsheng Han, Paul H. Siegel, Alexander Vardy

For a linear code C, the stopping redundancy of C is defined as the minimum number of check nodes in a Tanner graph T for C such that the size of the smallest stopping set in T is equal to the minimum distance of C. Han and Siegel recently proved an upper bound on the stopping redundancy of general linear codes, using probabilistic analysis. For most code parameters, this bound is the best currently known. In this correspondence, we present several improvements upon this bound.

IEEE Transactions on Information Theory•Mar 27, 2008•23 citations

The stopping redundancy hierarchy of cyclic codes

Thorsten Hehn, Stefan Laendner, Olgica Milenković +1 more

We extend the framework for studying the stopping redundancy of a linear block code by introducing and analyzing the stopping redundancy hierarchy.The stopping redundancy hierarchy of a code represents a measure of the trade-off between performance and complexity of iteratively decoding a code used over the binary erasure channel.It is defined as an ordered list of positive integers in which the ith entry, termed the i-th stopping redundancy, corresponds to the minimum number of rows in any parity-check matrix of the code that has stopping distance at least i.In particular, we derive lower and upper bounds for the i-th stopping redundancy of a code by using probabilistic methods and Bonferroni-type inequalities.Furthermore, we specialize the findings for cyclic codes, and show that parity-check matrices in cyclic form have some desirable redundancy properties.We also propose to investigate the influence of the generator codeword of the cyclic parity-check matrix on its stopping distance properties.

Allerton Conference on Communication, Control, and Computing•Jan 1, 2006•10 citations
One of the most important open problems in the communication society is to determine the performance of iterative message passing algorithms over loopy graphs.Some recent work addresses this problem for loopy Tanner graphs by introducing the concepts of stopping distance and stopping redundancy.By analyzing the eigenvalues and eigenvectors of the normalized incidence matrix representing a Tanner graph, we derive lower bounds on its stopping distance.Using these lower bounds, an upper bound on stopping redundancy of the difference-set codes is derived as well.
This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).
It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of Copf, defined as the minimum number of rows in a parity- check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely, s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes
It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s = d. We thus introduce a new parameter, termed the stopping redundancy of Copf, defined as the minimum number of rows in a parity-check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely s(H) = d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes
Key to the success of modern error correcting codes is the effectiveness of message-passing iterative decoding (MPID). Unlike maximum-likelihood (ML) decoding, the performance of MPID depends not only on the code, but on how the code is represented. In particular, the performance of MPID is potentially improved by using a redundant representation. We focus on Tanner graphs and study combinatorial structures therein that help explain the performance disparity among different representations of the same code. Emphasis is placed on the complexity- performance tradeoff, as more and more check nodes are allowed in the graph. Our discussion applies to MPID as well as linear programming decoding (LPD), which we collectively refer to as graph-based decoding. On an erasure channel, it is well-known that the performance of MPID or LPD is determined by stopping sets. Following Schwartz and Vardy, we define the stopping redundancy as the smallest number of check nodes in a Tanner graph such that smallest size of a non-empty stopping set is equal to the minimum Hamming distance of the code. Roughly speaking, stopping redundancy measures the complexity requirement (in number of check nodes) for MPID of a redundant graph representation to achieve performance comparable to ML decoding (up to a constant factor for small channel erasure probability). General upper bounds on stopping redundancy are obtained. One of our main contribution is a new upper bound based on probabilistic analysis, which is shown to be by far the strongest. From this bound, it can be shown, for example, that for a fixed minimum distance, the stopping redundancy grows just linearly with the redundancy (codimension). Specific results on the stopping redundancy of Golay and Reed-Muller codes are also obtained. We show that the stopping redundancy of maximum distance separable (MDS) codes is bounded in between a Turan number and a single-exclusion (SE) number --- a purely combinatorial quantity that we introduce. By studying upper bounds on the SE number, new results on the stopping redundancy of MDS codes are obtained. Schwartz and Vardy conjecture that the stopping redundancy of an MDS code should only depend on its length and minimum distance. Our results provide partial confirmation, both exact and asymptotic, to this conjecture. Stopping redundancy can be large for some codes. We observe that significantly fewer checks are needed if a small number of small stopping sets are allowed. These small stopping sets can then be dealt with by ̀g̀uessing'' during the iterative decoding process. Correspondingly, the guess-g stopping redundancy is defined and it is shown that the savings in number of required check nodes are potentially significant. Another theoretically interesting question is when MPID of a Tanner graph achieves the same word error rate an ML decoder. This prompts us to define and study ML redundancy. Applicability and possible extensions of the current work to a non-erasure channel are discussed. A framework based on pseudo-codewords is considered and shown to be relevant. However, it is also observed that the polytope characterization of pseudo-codewords is not complete enough to be an accurate indicator of MPID performance. Finally, in a separate piece of work, the probability of undetected error (PUE) for over-extended Reed-Solomon codes is studied through the weight distribution bounds of the code. The resulting PUE expressions are shown to be tight in a well-defined sense
We extend the framework for studying the stopping redundancy of a linear block code by introducing and analyzing the stopping redundancy hierarchy.The stopping redundancy hierarchy of a code represents a measure of the trade-off between performance and complexity of iteratively decoding a code used over the binary erasure channel.It is defined as an ordered list of positive integers in which the ith entry, termed the i-th stopping redundancy, corresponds to the minimum number of rows in any parity-check matrix of the code that has stopping distance at least i.In particular, we derive lower and upper bounds for the i-th stopping redundancy of a code by using probabilistic methods and Bonferroni-type inequalities.Furthermore, we specialize the findings for cyclic codes, and show that parity-check matrices in cyclic form have some desirable redundancy properties.We also propose to investigate the influence of the generator codeword of the cyclic parity-check matrix on its stopping distance properties.