On the List-Decodability of Random Linear Codes
2011 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 57, no 2, 718-725 p.Article in journal (Refereed) Published
The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field, Gamma(q), p is an element of (0, 1 - 1/q) and epsilon > 0, it is proved that with high probability a random linear code C in F-q(n) of rate (1 - H-q(p) - epsilon) can be list decoded from a fraction p of errors with lists of size at most O(1/epsilon). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/epsilon) suffices to have rate within epsilon of the information-theoretically optimal rate of 1 - H-q(p). The best previously known list-size bound was q(O(1/epsilon)) (except in the q = 2 case where a list-size bound of O(1/epsilon) was known). The main technical ingredient in the proof is a strong upper bound on the probability that l random vectors chosen from a Hamming ball centered at the origin have too many (more than Omega(l)) vectors from their linear span also belong to the ball.
Place, publisher, year, edition, pages
2011. Vol. 57, no 2, 718-725 p.
Hamming bound, linear codes, list decoding, probabilistic method, random coding
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-31347DOI: 10.1109/TIT.2010.2095170ISI: 000286514200010ScopusID: 2-s2.0-79251490359OAI: oai:DiVA.org:kth-31347DiVA: diva2:404462
QC 201103172011-03-172011-03-142013-04-05Bibliographically approved