Improved Upper Bounds on Stopping Redundancy

Details Improved Upper Bounds on Stopping Redundancy Improved Upper Bounds on Stopping Redundancy

2005-11-15

arxiv.org/abs/cs/0511056v1

Computer Science

Information Theory

13 pages, 3 figures. Submitted to the IEEE Transactions on Information Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Improved Upper Bounds on Stopping Redundancy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Upper Bounds on Stopping Redundancy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Upper Bounds on Stopping Redundancy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7475