Improved Upper Bounds on Stopping Redundancy
From MaRDI portal
Publication:3548239
Abstract: Let C be a linear code with length n and minimum distance d. The stopping redundancy of C is defined as the minimum number of rows in a parity-check matrix for C such that the smallest stopping sets in the corresponding Tanner graph have size d. We derive new upper bounds on the stopping redundancy of linear codes in general, and of maximum distance separable (MDS) codes specifically, and show how they improve upon previously known results. For MDS codes, the new bounds are found by upper bounding the stopping redundancy by a combinatorial quantity closely related to Turan numbers. (The Turan number, T(v,k,t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) We further show that the stopping redundancy of MDS codes is T(n,d-1,d-2)(1+O(n^{-1})) for fixed d, and is at most T(n,d-1,d-2)(3+O(n^{-1})) for fixed code dimension k=n-d+1. For d=3,4, we prove that the stopping redundancy of MDS codes is equal to T(n,d-1,d-2), for which exact formulas are known. For d=5, we show that the stopping redundancy of MDS codes is either T(n,4,3) or T(n,4,3)+1.
Recommendations
- Improved Probabilistic Bounds on Stopping Redundancy
- On the stopping distance and the stopping redundancy of codes
- On the Stopping Redundancy of Reed–Muller Codes
- Two classes of optimal stopping redundancy codes.
- Stopping sets of binary parity-check matrices with constant weight columns and stopping redundancy of the associated codes
Cited in
(4)
This page was built for publication: Improved Upper Bounds on Stopping Redundancy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548239)
