Improvements on the Johnson bound for Reed-Solomon codes

Muralidhara, V. N. ; Sen, Sandeep (2009) Improvements on the Johnson bound for Reed-Solomon codes Discrete Applied Mathematics, 157 (4). pp. 812-818. ISSN 0166-218X

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/j.dam.2008.06.014

Abstract

For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than n−√nk, there can be at most O(n2) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k<αn for any constant 0<α<1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius n−√nk+c (for any c>0) there can be at most O(nc2√α/(1−√α)2+c+2) number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the bound n−√nk is not sacrosanct for such a high rate. We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds [n/k]. We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Reed Solomom Codes; List Decodability
ID Code:53443
Deposited On:08 Aug 2011 12:14
Last Modified:08 Aug 2011 12:14

Repository Staff Only: item control page