DocumentCode :
1302468
Title :
Single-Exclusion Number and the Stopping Redundancy of MDS Codes
Author :
Han, Junsheng ; Siegel, Paul H. ; Roth, Ron M.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of California, La Jolla, CA, USA
Volume :
55
Issue :
9
fYear :
2009
Firstpage :
4155
Lastpage :
4166
Abstract :
For a linear block code C, its stopping redundancy is defined as the smallest number of check nodes in a Tanner graph for C, such that there exist no stopping sets of size smaller than the minimum distance of C. Schwartz and Vardy conjectured that the stopping redundancy of a maximum-distance separable (MDS) code should only depend on its length and minimum distance. We define the (n, t)-single-exclusion number, S(n, t) as the smallest number of i-subsets of an n-set, such that for each i-subset of the n-set, i =1,... ,t + 1, there exists a i-subset that contains all but one element of the i-subset. New upper bounds on the single-exclusion number are obtained via probabilistic methods, recurrent inequalities, as well as explicit constructions. The new bounds are used to better understand the stopping redundancy of MDS codes. In particular, it is shown that for [n, k = n - d + 1, d] MDS codes, as n rarr infin , the stopping redundancy is asymptotic to S(n, d - 2), if d = o(radic(n)), or if k = o(radic(n)), k rarr infin, thus giving partial confirmation of the Schwartz-Vardy conjecture in the asymptotic sense.
Keywords :
block codes; maximum likelihood decoding; set theory; Schwartz-Vardy conjecture; Tanner graph; erasure channel; iterative decoding; linear block code; maximum-distance separable code; probabilistic methods; recurrent inequalities; single-exclusion number; AWGN; Additive white noise; Block codes; Helium; Iterative decoding; Linear code; Magnetic recording; Maximum likelihood decoding; Parity check codes; Upper bound; Erasure channel; TurÁn number; iterative decoding; maximum-distance separable (MDS) code; single-exclusion number; stopping redundancy; stopping set;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2009.2025578
Filename :
5208498
Link To Document :
بازگشت