REVIEW
Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes
Information Theory · Submitted 2 Mar 2006 · 8 references
Pith's verdict: Completes the exact enumeration of stopping sets for the full-rank Hamming parity-check matrix; the proof holds up, with only a minor typo in Corollary 1.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
This paper proves a closed-form formula for the number of stopping sets of every size in the full-rank parity-check matrix of a Hamming code.
The reading
What carries the argument
The central object is the stopping set enumerator $S(x) = \sum_{l=0}^n S_l x^l$, the polynomial whose $l$-th coefficient counts stopping sets of size $l$ in the parity-check matrix. The argument is carried by an inclusion-exclusion formula (Theorem 1) that expresses $S_l$ as a signed sum over row subsets $T$ of the matrix; each term is determined by $z_T$, the number of all-zero columns in the restricted submatrix $H_T$, and $Y(T,p)$, the number of $p$-element column subsets for which every row of $H_T$ has weight one and every column is nonzero. For the full-rank Hamming matrix, Lemma 2 computes these quantities exactly: $z_T = 2^{m-|T|}-1$ and $Y(T,p)$ equals the Stirling number of the second kind for $|T|$ and $p$, multiplied by $2^{(m-|T|)p}$. Substituting these values and applying binomial and Stirling identities produces the closed form of Theorem 2.
Extended reading notes
Core claim
The paper's main result, Theorem 2, states that for the $m \times (2^m-1)$ parity-check matrix $H$ whose columns are all distinct nonzero binary vectors of length $m$, the number $S_l$ of stopping sets of size $l$ equals the finite sum $$S_l = \frac{1}{l!} \sum_{q=0}^{l} \sum_{v=q}^{\min\{2q,l\}} (-1)^v \binom{l}{v} b(q,v) \left($2^{{l-q}}$ - (l-v)\right)^m,$$ where $b(q,v)$ is a signed integer defined by a recursion and an explicit combinatorial sum in Lemmas 5 and 6. The paper proves this by first deriving a general inclusion-exclusion formula for $S_l$ in terms of row-subset restrictions of any parity-check matrix, then evaluating the two quantities that arise, $z_T$ and $Y(T,p)$, for the full-rank Hamming matrix using Stirling numbers. The result reproduces the known size-three count and yields new explicit enumerators for sizes four and five, together with the asymptotic law $S_l \sim n^{\log_2(2^l-l)}/l!$ for fixed $l$.
Load-bearing premise
The formula stands or falls on the special structure of the full-rank Hamming matrix, where every nonzero binary column appears exactly once; if the parity-check matrix of the same code is not of this form, the closed-form count does not apply.
Editorial extensions
If this is right
- For every $m \ge 3$, the stopping set enumerator of the full-rank Hamming matrix is completely determined, so exact iterative-decoding failure probabilities on the binary erasure channel become computable in principle for this matrix.
- The formula specializes to $S_3 = \frac{1}{6}(5^m - 3\cdot 3^m + 2\cdot 2^m)$ and yields explicit enumerators for $S_4$, $S_5$, and all larger sizes by substitution.
- For any fixed size $l \ge 3$, $S_l \sim n^{\log_2(2^l-l)}/l!$ as $n=2^m-1$ grows, while the codeword count satisfies $A_l \sim n^{l-1}/l!$, so stopping sets are asymptotically more numerous than codewords at each fixed small size.
- Since row and column permutations of the same parity-check matrix preserve stopping set counts, the formula applies to every matrix obtained by permuting the rows or columns of the canonical full-rank Hamming matrix.
Reading between the lines
- One could use the inclusion-exclusion framework with recomputed values of $z_T$ and $Y(T,p)$ to derive enumerators for other matrices of the same code, providing a quantitative comparison of how the choice of parity-check matrix alters decoding performance.
- The recursive definition of $b(q,v)$ suggests a dynamic-programming evaluation of the formula, which would allow computation of $S_l$ for code lengths far beyond the explicit small cases listed in the paper.
- The same closed-form strategy might adapt to codes whose parity-check columns form the nonzero vectors of a vector space over another field, although the count of zero and repeated columns would change the factors in Lemma 2.
Original abstract
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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.04 | 0.03 | asserted 1.00 |
| s1 | 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. | background 0.99 | 0.03 | 0.04 | asserted 1.00 |
| s2 | In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix. | contribution 0.97 | 0.97 | 0.87 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.