IEEE Transactions on Information Theory · 2007 · 61 citations · 20 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsCoding TheoryEnumerative CombinatoricsError Control CodingError-correcting CodesBounds On CodesLinear Block CodesLinear CodesMaximum Distance Separable CodesMds CodesMinimum DistanceMinimum Distance BoundsUpper Bounds
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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> )) for fixed d, and is at most T (n,d-1,d-2)(3+O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> )) 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
20
Low-density parity-check codes
Robert G. Gallager · IEEE Transactions on Information Theory · 1962 · 10.6K citations · Full text
On a Packing and Covering Problem
Vojtěch Rödl · European Journal of Combinatorics · 1985 · 414 citations
Esther Seiden, Rita Zemach · The Annals of Mathematical Statistics · 1966 · 287 citations · Full text