Change search
ReferencesLink to record
Permanent link

Direct link
Combinatorial bounds for list decoding
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2002 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 48, no 5, 1021-1034 p.Article in journal (Refereed) Published
Abstract [en]

Informally, an error-correcting code has nice list-decodability properties if every Hamming ball of large radius has a small number of codewords in it. Here, we report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H-1 (1-R-1/c) (.) n. This answers the main open question from the work of Elias. This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan in this vein. Specifically, for every epsilon > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Omega(epsilon(4)) that can be list-decoded in polynomial time from up to a fraction (1/2 - epsilon) of errors, using lists of size O(epsilon(-2)). On the negative side, we show that for every delta and c, there exists tau < delta, c(1) > 0, and an infinite family of linear codes {C-i}(i) such that if n(i) denotes the block length of C-i, then C-i has minimum distance at least delta (.) n(i) and contains more than c(1) (.) n(i)(c) codewords in some Hamming ball of radius tau (.) n(i). While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the radius for list-decodability by a polynomial-sized list away from the minimum distance of the code.

Place, publisher, year, edition, pages
2002. Vol. 48, no 5, 1021-1034 p.
Keyword [en]
concatenated codes, error-correcting codes, list decoding, Reed-Solomon (RS) code, reed-solomon, codes
URN: urn:nbn:se:kth:diva-21462ISI: 000174970900002OAI: diva2:340160
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
IEEE Transactions on Information Theory

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 42 hits
ReferencesLink to record
Permanent link

Direct link