Improved Upper Bounds on Stopping Redundancy

DOI10.1109/TIT.2006.887513zbMATH Open1310.94232arXivcs/0511056MaRDI QIDQ3548239FDOQ3548239

Authors: Junsheng Han, Paul Siegel 

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0511056

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

zbMATH Keywords

maximum distance separable (MDS) codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65)

Cited In (4)

• Stopping sets of binary parity-check matrices with constant weight columns and stopping redundancy of the associated codes
• Two classes of optimal stopping redundancy codes.
• On the stopping distance and the stopping redundancy of codes
• Improved Probabilistic Bounds on Stopping Redundancy

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)