pith. sign in

arxiv: 2601.00435 · v2 · submitted 2026-01-01 · 💻 cs.IT · math.IT

On the burst-covering radius of binary cyclic codes

Gabriel Sac Himelfarb , Moshe Schwartz This is my paper

Pith reviewed 2026-05-16 17:48 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords burst-covering radiusbinary cyclic codesBCH codesMelas codesLFSR sequencespattern frequenciescovering radiuscritical exponent
0
0 comments X

The pith

A new bound on pattern frequencies in LFSR sequences controls the burst-covering radius of binary primitive BCH codes and Melas codes.

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

The paper defines the burst-covering radius of a code and gives general bounds linking it to standard code parameters. It strengthens these bounds for cyclic codes by analyzing the linear-feedback shift-register sequences produced by the code's feedback polynomial. For BCH codes the authors prove a fresh upper bound on how often short patterns occur inside those sequences; the bound is independent of certain code details and directly limits the burst-covering radius. The same tool yields explicit radius estimates for binary primitive BCH codes and for Melas codes. The work also supplies an efficient algorithm that finds a burst-covering set for any cyclic code and derives a bound on the critical exponent of such codes.

Core claim

By proving a new bound on the frequencies of patterns appearing in LFSR sequences generated by BCH feedback polynomials, the burst-covering radius of binary primitive BCH codes and Melas codes can be upper-bounded in terms of the code length and designed distance.

What carries the argument

The bound on pattern frequencies in LFSR sequences generated by the feedback polynomial of BCH codes, which directly limits the longest uncovered burst.

If this is right

  • General parameter bounds relate minimum distance and length to burst-covering radius for any code.
  • Stronger radius bounds hold for all cyclic codes once LFSR sequence properties are known.
  • An efficient algorithm computes a burst-covering set for any given cyclic code.
  • The critical exponent of a cyclic code is at most a simple function of its burst-covering radius.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The frequency bound may be reusable for analyzing other statistical properties of LFSR sequences outside coding theory.
  • The radius estimates could guide code selection for channels dominated by burst errors.
  • Analogous frequency arguments might extend the results to non-primitive or non-binary cyclic codes.

Load-bearing premise

The frequencies of short patterns inside the LFSR sequences can be bounded independently of specific code parameters in a way that directly determines the burst-covering radius.

What would settle it

A concrete binary primitive BCH code whose measured burst-covering radius exceeds the upper bound obtained from the LFSR pattern-frequency result.

Figures

Figures reproduced from arXiv: 2601.00435 by Gabriel Sac Himelfarb, Moshe Schwartz.

Figure 1
Figure 1. Figure 1: Generating a binary sequence with connection polynomial [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original abstract

We define and study burst-covering codes. We provide some general bounds connecting the parameters of a code with its burst-covering radius. We then provide stronger bounds on the burst-covering radius of cyclic codes, by employing linear-feedback shift-register (LFSR) sequences. For the case of BCH codes we prove a new bound on pattern frequencies in LFSR sequences, which is of independent interest. Using this tool, we can bound the burst-covering radius of binary primitive BCH codes and Melas codes. We then present an efficient burst-covering algorithm for cyclic codes. Finally, we present a bound on the critical exponent of cyclic codes based on the burst-covering radius.

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

1 major / 3 minor

Summary. The paper defines burst-covering codes and derives general bounds relating code parameters to the burst-covering radius. It obtains stronger bounds for cyclic codes by analyzing LFSR sequences generated by the code's feedback polynomial. For binary primitive BCH codes and Melas codes, it proves a new bound on pattern frequencies in these LFSR sequences (claimed to be of independent interest) and applies it to bound the burst-covering radius. The manuscript also presents an efficient burst-covering algorithm for cyclic codes and derives a bound on the critical exponent of cyclic codes from the burst-covering radius.

Significance. If the LFSR frequency bound and its application hold, the work provides concrete radius estimates for important families (BCH, Melas) and a practical algorithm, while the frequency result may have standalone value in sequence analysis. The general bounds and critical-exponent connection broaden the contribution within coding theory.

major comments (1)
  1. [BCH codes and LFSR frequency bound] The section deriving the new bound on pattern frequencies in LFSR sequences for BCH codes: the combinatorial argument for parameter-independent frequency control must be stated explicitly with the counting steps, as this step is load-bearing for the subsequent radius bounds on BCH and Melas codes.
minor comments (3)
  1. [General bounds] In the general bounds section, clarify whether the burst-covering radius definitions reduce to standard covering radius when the burst length is 1.
  2. [Burst-covering algorithm] The algorithm section should include a brief complexity analysis or pseudocode to make the efficiency claim verifiable.
  3. [Results for BCH/Melas codes] Add a short numerical example (e.g., small BCH code) illustrating the radius bound to aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the work, and the recommendation for minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: [BCH codes and LFSR frequency bound] The section deriving the new bound on pattern frequencies in LFSR sequences for BCH codes: the combinatorial argument for parameter-independent frequency control must be stated explicitly with the counting steps, as this step is load-bearing for the subsequent radius bounds on BCH and Melas codes.

    Authors: We agree that the combinatorial argument requires explicit expansion for clarity. In the revised manuscript we will rewrite the relevant subsection to present a complete step-by-step counting argument, enumerating each combinatorial step that establishes the parameter-independent frequency control in the LFSR sequences of primitive BCH codes. This will make the derivation self-contained and directly support the subsequent radius bounds for BCH and Melas codes. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation begins with the definition of burst-covering radius and general bounds relating code parameters to this radius. Stronger bounds for cyclic codes are obtained via combinatorial properties of LFSR sequences generated by the code's feedback polynomial. For BCH codes a new bound on pattern frequencies in these sequences is proved from first principles and stated to be of independent interest; this bound is then applied to control the radius for primitive BCH and Melas codes. The efficient algorithm and critical-exponent bound are direct consequences of the radius result. No equation reduces to a fitted parameter renamed as a prediction, no load-bearing premise rests on a self-citation chain, and no ansatz is smuggled via prior work by the same authors. The logical flow is self-contained against external combinatorial and LFSR facts.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard properties of cyclic codes and LFSR sequences over finite fields; no free parameters or invented entities are apparent from the abstract.

axioms (1)
  • domain assumption LFSR sequences generated by primitive polynomials have controllable pattern frequencies that can be bounded to determine covering radii.
    Invoked to prove the new bound for BCH codes and apply it to burst-covering radius.

pith-pipeline@v0.9.0 · 5403 in / 1182 out tokens · 23278 ms · 2026-05-16T17:48:27.035953+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    On the existence of optimum cyclic burst correcting codes overGF(q),

    K. A. S. Abdel-Ghaffar, “On the existence of optimum cyclic burst correcting codes overGF(q),”IEEE Trans. Inform. Theory, vol. 34, no. 2, pp. 329–332, Mar. 1988

    work page 1988

  2. [2]

    On the existence of optimum cyclic burst-correcting codes,

    K. A. S. Abdel-Ghaffar, R. J. McEliece, A. M. Odlyzko, and H. C. A. van Tilborg, “On the existence of optimum cyclic burst-correcting codes,”IEEE Trans. Inform. Theory, vol. 32, no. 6, pp. 768–775, Nov. 1986

    work page 1986

  3. [3]

    A class of systematic codes for non-independent errors,

    N. M. Abramson, “A class of systematic codes for non-independent errors,”IRE Trans. on Inform. Theory, vol. 5, pp. 150–157, Dec. 1959

    work page 1959

  4. [4]

    Bounds for exponential sums,

    L. Carlitz and S. Uchiyama, “Bounds for exponential sums,”Duke Mathematical Journal, vol. 24, pp. 37–41, 1957. [Online]. Available: https://api.semanticscholar.org/CorpusID:119515935

    work page 1957

  5. [5]

    Computing partial sums in multidimensional arrays,

    B. Chazelle and B. Rosenberg, “Computing partial sums in multidimensional arrays,” inSCG ’89, 1989. [Online]. Available: https: //api.semanticscholar.org/CorpusID:5096537

    work page 1989

  6. [6]

    Repairing with zero skip cost,

    Y . M. Chee, S. H. Dau, T. Etzion, H. M. Kiah, Y . Luo, and W. Zhang, “Repairing with zero skip cost,” in2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2134–2139

    work page 2024

  7. [7]

    Private information retrieval,

    B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,”J. of the ACM, vol. 45, no. 6, pp. 965–981, 1998

    work page 1998

  8. [8]

    Using Stepanov’s method for exponential sums involving rational functions,

    T. Cochrane and C. Pinner, “Using Stepanov’s method for exponential sums involving rational functions,”J. of Number Theory, vol. 116, no. 2, pp. 270–292, Feb. 2006

    work page 2006

  9. [9]

    Cohen, I

    G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein,Covering Codes. North-Holland, 1997

    work page 1997

  10. [10]

    The generalized covering radii of linear codes,

    D. Elimelech, M. Firer, and M. Schwartz, “The generalized covering radii of linear codes,”IEEE Trans. Inform. Theory, vol. 67, no. 12, pp. 8070–8085, Dec. 2021

    work page 2021

  11. [11]

    On the generalized covering radii of Reed-Muller codes,

    D. Elimelech, H. Wei, and M. Schwartz, “On the generalized covering radii of Reed-Muller codes,”IEEE Trans. Inform. Theory, vol. 68, no. 7, pp. 4378–4391, Jul. 2022

    work page 2022

  12. [12]

    A note on optimum burst-error-correcting codes,

    B. Elspas and R. A. Short, “A note on optimum burst-error-correcting codes,”IRE Trans. on Inform. Theory, pp. 39–42, Jan. 1962

    work page 1962

  13. [13]

    Constructions for perfect 2-burst-correcting codes,

    T. Etzion, “Constructions for perfect 2-burst-correcting codes,”IEEE Trans. Inform. Theory, vol. 47, no. 6, pp. 2553–2555, Sep. 2001

    work page 2001

  14. [14]

    A class of multiple-error-correcting binary codes for non-independent errors,

    P. Fire, “A class of multiple-error-correcting binary codes for non-independent errors,” Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, USA, Tech. Rep. Sylvania Report RSL-E-2, 1959

    work page 1959

  15. [15]

    S. W. Golomb,Shift Register Sequences. Holden-Day, San Francisco, 1967

    work page 1967

  16. [16]

    Goresky and A

    M. Goresky and A. Klapper,Algebraic Shift Register Sequences. Cambridge University Press, 2012

    work page 2012

  17. [17]

    Lidl and H

    R. Lidl and H. Niederreiter,Finite Fields. Cambridge University Press, 1997

    work page 1997

  18. [18]

    F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes. North-Holland, 1978

    work page 1978

  19. [19]

    Distribution properties of feedback shift register sequences,

    H. Niederreiter, “Distribution properties of feedback shift register sequences,”Problems of control and information theory- Problemy upravleniya i toerii informatsii, vol. 15, no. 1, pp. 19–34, 1986

    work page 1986

  20. [20]

    Estimation of a sum along an algebraic curve,

    G. I. Perel’muter, “Estimation of a sum along an algebraic curve,”Mathematical Notes of the Academy of Sciences of the USSR, vol. 5, no. 3, pp. 223–227, 1969

    work page 1969

  21. [21]

    Access-redundancy tradeoffs in quantized linear computations,

    V . Ramkumar, N. Raviv, and I. Tamo, “Access-redundancy tradeoffs in quantized linear computations,”IEEE Trans. Inform. Theory, vol. 70, no. 11, pp. 7723–7739, Nov. 2024

    work page 2024

  22. [22]

    Two-dimensional cluster-correcting codes,

    M. Schwartz and T. Etzion, “Two-dimensional cluster-correcting codes,”IEEE Trans. Inform. Theory, vol. 51, no. 6, pp. 2121–2132, Jun. 2005

    work page 2005

  23. [23]

    Achievable lower bound on the optimal access bandwidth of(K+ 2, K,2)-MDS array code with degraded read friendly,

    T.-Y . Wu, Y . S. Han, Z. Li, B. Bai, G. Zhang, X. Zhang, and X. Wu, “Achievable lower bound on the optimal access bandwidth of(K+ 2, K,2)-MDS array code with degraded read friendly,” in2021 IEEE Information Theory Workshop (ITW), 2021, pp. 1–5

    work page 2021

  24. [24]

    On zero skip-cost generalized fractional repetition codes from covering designs,

    W. Yu, B.-J. Yuan, and M. Schwartz, “On zero skip-cost generalized fractional repetition codes from covering designs,”arXiv preprint arXiv:2502.12897, 2025. 15 APPENDIX Lemma 39.For all integersa, b⩾1, 1 + (2a −1)(2 b −1) (2gcd(a,b) −1)2 (a+b)/2 >2 (a+b)/2−gcd(a,b). Proof:Letc= gcd(a, b). The inequality holds if and only if (2c −1)2 (a+b)/2 + (2a −1)(2 b ...

    work page arXiv 2025