DocumentCode :
1355691
Title :
A Lower Bound on List Size for List Decoding
Author :
Guruswami, Venkatesan ; Vadhan, Salil
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of Washington, Seattle, WA, USA
Volume :
56
Issue :
11
fYear :
2010
Firstpage :
5681
Lastpage :
5688
Abstract :
A q-ary error-correcting code C ⊆ {1,2,...,q}n is said to be list decodable to radius ρ with list size L if every Hamming ball of radius ρ contains at most L codewords of C. We prove that in order for a q -ary code to be list-decodable up to radius (1-1/q)(1- ε)n, we must have L = Ω(1/ ε2) . Specifically, we prove that there exists a constant cq > 0 and a function fq such that for small enough ε > 0, if C is list-decodable to radius (1-1/q)(1- ε)n with list size cq/ ε2, then C has at most fq( ε) codewords, independent of n . This result is asymptotically tight (treating q as a constant), since such codes with an exponential (in n ) number of codewords are known for list size L = O(1/ ε2). A result similar to ours is implicit in Blinovsky ( Problems of Information Transmission, 1986) for the binary (q=2) case. Our proof is simpler and works for all alphabet sizes, and provides more intuition for why the lower bound arises.
Keywords :
binary codes; error correction codes; binary case; list decoding; lower bound; q-ary error correcting code; Binary codes; Context; Correlation; Decoding; Entropy; Error correction codes; Probabilistic logic; Bounds on codes; list decoding; probabilistic method; random codes; randomness extractors;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2010.2070170
Filename :
5605366
Link To Document :
بازگشت