pith. sign in

arxiv: 2605.01213 · v1 · submitted 2026-05-02 · 💻 cs.IT · math.CO· math.IT

Improved Rate-versus-Distance Upper Bounds for LDPC Codes

Chong Shangguan , Yulin Yang This is my paper

Pith reviewed 2026-05-09 18:25 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords LDPC codesrate-distance tradeoffcoset graphsball sizesupper boundscoset-weight generating functionlocal growth analysiserror-correcting codes
0
0 comments X

The pith

New framework sharpens ball size estimates to improve LDPC rate upper bounds

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a new framework for estimating ball sizes in the coset graphs of LDPC codes. It centers on upper-bounding the coset-weight generating function by analyzing local growth in codes spanned by low-weight vectors. This sharpens an earlier estimate and, when combined with a method relating ball sizes to code rates, gives better upper bounds on LDPC code rates for a range of relative distances. Readers would care because LDPC codes are widely used, and tighter theoretical limits help assess how close practical codes can get to optimal performance.

Core claim

By introducing the coset-weight generating function and bounding it via local growth analysis for low-weight vector codes, the authors obtain a sharper estimate of ball sizes in LDPC coset graphs. Integrated with the Friedman-Tillich relation between these balls and error-correcting code sizes, the framework yields improved upper bounds on the rate of LDPC codes for a significant range of relative distances.

What carries the argument

The coset-weight generating function, which encodes the minimum Hamming weights of all cosets, bounded through local growth analysis of low-weight spanned codes to estimate ball sizes.

Load-bearing premise

The coset-weight generating function can be usefully upper-bounded by local growth analysis applied to codes spanned by low-weight vectors, and this bound holds when the code is LDPC.

What would settle it

Constructing or identifying an LDPC code with a rate higher than the new upper bound at a relative distance where the improvement is claimed, or finding coset weights that exceed the proposed generating function bound.

Figures

Figures reproduced from arXiv: 2605.01213 by Chong Shangguan, Yulin Yang.

Figure 1
Figure 1. Figure 1: Comparison with [7] for w = 3. 5 view at source ↗
read the original abstract

LDPC codes play a vital role in coding theory and practical error correction. A central problem in this direction is to understand their rate--distance tradeoff. In this paper, we introduce a new framework for estimating ball sizes in the coset graphs of LDPC codes. The key new object is the coset-weight generating function, which encodes the minimum Hamming weights of all cosets of a linear code. Rather than estimating coset balls directly, we upper-bound this generating function through a local growth analysis for codes spanned by low-weight vectors. This framework sharpens the previous ball-size estimate of Iceland and Samorodnitsky. Combined with a general method of Friedman and Tillich that relates balls in coset graphs to sizes of error-correcting codes, it further improves the upper bounds on the rate of LDPC codes for a significant range of relative distances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces a new framework for upper-bounding ball sizes in the coset graphs of LDPC codes. The central object is the coset-weight generating function, which records the minimum Hamming weights of all cosets. This generating function is upper-bounded via local growth analysis applied to the subcode spanned by low-weight vectors. The resulting ball-size estimate is claimed to sharpen the earlier bound of Iceland and Samorodnitsky; when inserted into the Friedman-Tillich relation between coset-graph balls and code cardinality, it yields improved upper bounds on the rate of LDPC codes over a significant interval of relative distances.

Significance. If the technical steps are valid, the work supplies sharper rate-versus-distance upper bounds for LDPC codes, a longstanding question in coding theory. The approach re-uses the Friedman-Tillich machinery but replaces a generic ball-size estimate with one derived from a generating-function analysis tailored to low-weight generators; this is a concrete, falsifiable improvement over prior bounds if the local-growth step remains valid under the LDPC sparsity constraint.

major comments (2)
  1. [Framework description (around the definition of the coset-weight generating function and its local-growth bound)] The central claim that the local-growth upper bound on the coset-weight generating function remains valid (and strictly tighter) once the code is required to be LDPC is load-bearing for the asserted improvement. The manuscript does not explicitly verify that the growth-rate calculation is insensitive to the global sparsity constraint on the parity-check matrix or that the low-weight generators already encode the LDPC property; if either fails, the sharpening over Iceland-Samorodnitsky disappears for the LDPC case.
  2. [Application to rate bounds (the section combining the new estimate with Friedman-Tillich)] The transition from the generating-function bound to the final rate upper bound via Friedman-Tillich is presented as direct, but the manuscript supplies neither explicit constants nor a numerical comparison table showing the improvement for concrete relative distances. Without these, it is impossible to confirm that the claimed sharpening is realized for LDPC codes rather than only for general linear codes.
minor comments (2)
  1. [Introduction of the coset-weight generating function] Notation for the coset-weight generating function is introduced without a compact equation label; adding an explicit displayed equation would improve readability when the bound is later invoked.
  2. [Abstract and concluding remarks] The abstract states that the improvement holds 'for a significant range of relative distances,' but the manuscript does not indicate the precise interval or the method used to determine it; a short remark or plot would clarify the scope.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each major comment point by point below, providing clarifications and committing to revisions where appropriate to strengthen the presentation.

read point-by-point responses

  1. Referee: The central claim that the local-growth upper bound on the coset-weight generating function remains valid (and strictly tighter) once the code is required to be LDPC is load-bearing for the asserted improvement. The manuscript does not explicitly verify that the growth-rate calculation is insensitive to the global sparsity constraint on the parity-check matrix or that the low-weight generators already encode the LDPC property; if either fails, the sharpening over Iceland-Samorodnitsky disappears for the LDPC case.

    Authors: We thank the referee for highlighting this important point. The local-growth analysis (Section 3) is performed exclusively on the subcode spanned by low-weight vectors and relies only on their minimum weights and local expansion properties in the coset graph; it does not invoke the global row-sparsity of the parity-check matrix. The LDPC constraint is used to guarantee the existence of a sufficiently rich set of low-weight generators, but the upper bound derivation itself is insensitive to further global sparsity details and remains valid (and strictly tighter than the generic Iceland-Samorodnitsky estimate) for any linear code possessing such a subcode. We will add an explicit clarifying remark in the revised Section 3 stating this independence, confirming that the improvement applies directly to LDPC codes. revision: partial

  2. Referee: The transition from the generating-function bound to the final rate upper bound via Friedman-Tillich is presented as direct, but the manuscript supplies neither explicit constants nor a numerical comparison table showing the improvement for concrete relative distances. Without these, it is impossible to confirm that the claimed sharpening is realized for LDPC codes rather than only for general linear codes.

    Authors: We agree that explicit constants and a numerical comparison would make the improvement more transparent and verifiable. In the revised manuscript we will insert a new table (or subsection) in Section 4 that evaluates the resulting rate upper bounds at concrete relative distances δ (e.g., 0.05, 0.1, 0.15, 0.2, 0.25) using the explicit constants obtained from the coset-weight generating-function bound. Side-by-side comparison with the Iceland-Samorodnitsky bounds will be provided under parameter choices consistent with LDPC constructions, thereby demonstrating the sharpening specifically for the LDPC setting. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation introduces independent local-growth bound on coset-weight generating function

full rationale

The paper defines a new object (coset-weight generating function) and applies local growth analysis to bound it for subcodes spanned by low-weight vectors, then feeds the result into the external Friedman-Tillich relation to obtain rate upper bounds. This sharpens the prior Iceland-Samorodnitsky estimate without any quoted self-definition, fitted-parameter-as-prediction, or load-bearing self-citation chain. The abstract and description present the steps as additive analysis rather than tautological rearrangement of inputs, satisfying the self-contained criterion.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Only the abstract is available; the ledger is therefore limited to the explicitly introduced object and standard background assumptions of coding theory.

axioms (1)
  • standard math Standard properties of linear codes, cosets, and Hamming weights over finite fields
    Invoked implicitly when defining the coset-weight generating function and coset graphs.
invented entities (1)
  • coset-weight generating function no independent evidence
    purpose: Encodes the minimum Hamming weights of all cosets of a linear code to enable ball-size estimation
    Explicitly introduced as the key new object in the framework; no independent evidence outside the paper is supplied in the abstract.

pith-pipeline@v0.9.0 · 5440 in / 1451 out tokens · 34612 ms · 2026-05-09T18:25:56.079370+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Upper bounds on the rate of LDPC codes as a function of minimum distance.IEEE Transactions on Information Theory, 52(5):2092–2100, 2006

    Yael Ben-Haim and Simon Litsyn. Upper bounds on the rate of LDPC codes as a function of minimum distance.IEEE Transactions on Information Theory, 52(5):2092–2100, 2006

    work page 2092

  2. [2]

    Upper bounds on the rate of LDPC codes.IEEE Transactions on Information Theory, 48(9):2437–2449, 2002

    David Burshtein, Michael Krivelevich, Simon Litsyn, and Gadi Miller. Upper bounds on the rate of LDPC codes.IEEE Transactions on Information Theory, 48(9):2437–2449, 2002

    work page 2002

  3. [3]

    Improved decoding of expander codes

    Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. Improved decoding of expander codes. IEEE Transactions on Information Theory, 69(6):3574–3589, 2023

    work page 2023

  4. [4]

    Generalized Alon–Boppana theorems and error-correcting codes.SIAM Journal on Discrete Mathematics, 19(3):700–718, 2005

    Joel Friedman and Jean-Pierre Tillich. Generalized Alon–Boppana theorems and error-correcting codes.SIAM Journal on Discrete Mathematics, 19(3):700–718, 2005

    work page 2005

  5. [5]

    Gallager

    Robert G. Gallager. Low-density parity-check codes.IRE Transactions on Information Theory, 8(1):21–28, 1962

    work page 1962

  6. [6]

    Edgar N. Gilbert. A comparison of signalling alphabets.The Bell System Technical Journal, 31(3):504–522, 1952

    work page 1952

  7. [7]

    On coset leader graphs of LDPC codes.IEEE Transactions on Information Theory, 61(8):4158–4163, 2015

    Eran Iceland and Alex Samorodnitsky. On coset leader graphs of LDPC codes.IEEE Transactions on Information Theory, 61(8):4158–4163, 2015

    work page 2015

  8. [8]

    On ensembles of low-density parity-check codes: Asymptotic distance distributions.IEEE Transactions on Information Theory, 48(4):887–908, 2002

    Simon Litsyn and Vladimir Shevelev. On ensembles of low-density parity-check codes: Asymptotic distance distributions.IEEE Transactions on Information Theory, 48(4):887–908, 2002. 11

    work page 2002

  9. [9]

    Distance distributions in ensembles of irregular low-density parity-check codes.IEEE Transactions on Information Theory, 49(12):3140–3159, 2003

    Simon Litsyn and Vladimir Shevelev. Distance distributions in ensembles of irregular low-density parity-check codes.IEEE Transactions on Information Theory, 49(12):3140–3159, 2003

    work page 2003

  10. [10]

    David J. C. MacKay and Radford M. Neal. Near Shannon limit performance of low density parity check codes.Electronics Letters, 32(18):1645–1646, 1996

    work page 1996

  11. [11]

    MacWilliams and Neil J

    Florence J. MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes. North- Holland, Amsterdam, 1977

    work page 1977

  12. [12]

    McEliece, Eugene R

    Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey, Jr., and Lloyd R. Welch. New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities.IEEE Transactions on Information Theory, 23(2):157–166, 1977

    work page 1977

  13. [13]

    Low-density parity-check codes achieve list-decoding capacity.SIAM Journal on Computing, 53(6):FOCS20–38, 2021

    Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. Low-density parity-check codes achieve list-decoding capacity.SIAM Journal on Computing, 53(6):FOCS20–38, 2021

    work page 2021

  14. [14]

    Binary codes with specified minimum distance.IRE Transactions on Information Theory, 6(4):445–450, 1960

    Morris Plotkin. Binary codes with specified minimum distance.IRE Transactions on Information Theory, 6(4):445–450, 1960

    work page 1960

  15. [15]

    Urbanke.Modern Coding Theory

    Thomas Richardson and R¨ udiger L. Urbanke.Modern Coding Theory. Cambridge University Press, 2008

    work page 2008

  16. [16]

    Richardson, Mohammad Amin Shokrollahi, and R¨ udiger L

    Thomas J. Richardson, Mohammad Amin Shokrollahi, and R¨ udiger L. Urbanke. Design of capacity- approaching irregular low-density parity-check codes.IEEE Transactions on Information Theory, 47(2):619–637, 2001

    work page 2001

  17. [17]

    Roth and Vitaly Skachek

    Ron M. Roth and Vitaly Skachek. Improved nearly-MDS expander codes.IEEE Transactions on Information Theory, 52(8):3650–3661, 2006

    work page 2006

  18. [18]

    Spielman

    Michael Sipser and Daniel A. Spielman. Expander codes.IEEE Transactions on Information Theory, 42(6):1710–1722, 1996

    work page 1996

  19. [19]

    Vitaly Skachek and Ron M. Roth. Generalized minimum distance iterative decoding of expander codes. InProceedings of the 2003 IEEE Information Theory Workshop, pages 245–248. IEEE, 2003

    work page 2003

  20. [20]

    Varshamov

    Rom R. Varshamov. Estimate of the number of signals in error correcting codes.Doklady Akademii Nauk SSSR, 117:739–741, 1957. Appendix Proof of Lemma 3.3. If v = 0, then Φ0,∆(λ) = 1/(1 + λ∆) ≤ 1 = (1 + 3λ)0. Assume v≥ 1. Since v+ ∆≤3, the possible pairs are (1,0),(1,1),(1,2),(2,0),(2,1),(3,0). A direct calculation gives Φ1,0 =Φ 1,1 = 1, Φ 1,2 = 1 +λ 1 +λ 2...

    work page 1957