Skip to main content
eScholarship
Open Access Publications from the University of California

Improved upper bounds on stopping redundancy

  • Author(s): Han, Junsheng S
  • Siegel, P H
  • et al.
Abstract

For a linear block code with minimum distance d, its stopping redundancy is the minimum number of check nodes in a Tanner graph representation of the code, such that all nonempty stopping sets have size d or larger. We derive new upper bounds on stopping redundancy for all linear codes in general, and for maximum distance separable (MDS) codes specifically, and show how they improve upon previous 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.) Asymptotically, we show that the stopping redundancy of MDS codes with length n and minimum distance d > 1 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 + 0(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.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View