BOUNDS ON THE LIST-DECODING RADIUS OF REED --SOLOMON CODES.

Saved in:

Bibliographic Details
Title:	BOUNDS ON THE LIST-DECODING RADIUS OF REED --SOLOMON CODES.
Authors:	Ruckestein, Gitit¹ gitit@cs.technion.ac.il, Roth, Ron M.¹ ronny@cs.technion.ac.il
Source:	SIAM Journal on Discrete Mathematics. 2003, Vol. 17 Issue 2, p171-195. 25p.
Subjects:	Reed-Solomon codes, Digital signal processing mathematics, Error-correcting codes, Block designs, Algorithms, Sidon sets
Abstract:	Techniques are presented for computing upper and lower bounds on the number of errors that can be corrected by list decoders for general block codes and, specifically, for Reed-Solomon (RS) codes. The list decoder of Guruswami and Sudan implies such a lower bound (referred to here as the GS bound) for RS codes. It is shown that this lower bound, given by means of the code's length, the minimum Hamming distance, and the maximal allowed list size, in fact applies to all block codes. Ranges of code parameters are identified where the GS bound is tight for worst-case RS codes, in which case the list decoder of Guruswami and Sudan provably corrects the largest possible number of errors. On the other hand, ranges of parameters are provided for which the GS lower bound can be strictly improved. In some cases the improvement applies to all block codes with a given minimum Hamming distance, while in others it applies only to RS codes. [ABSTRACT FROM AUTHOR]
	Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Techniques are presented for computing upper and lower bounds on the number of errors that can be corrected by list decoders for general block codes and, specifically, for Reed-Solomon (RS) codes. The list decoder of Guruswami and Sudan implies such a lower bound (referred to here as the GS bound) for RS codes. It is shown that this lower bound, given by means of the code's length, the minimum Hamming distance, and the maximal allowed list size, in fact applies to all block codes. Ranges of code parameters are identified where the GS bound is tight for worst-case RS codes, in which case the list decoder of Guruswami and Sudan provably corrects the largest possible number of errors. On the other hand, ranges of parameters are provided for which the GS lower bound can be strictly improved. In some cases the improvement applies to all block codes with a given minimum Hamming distance, while in others it applies only to RS codes. [ABSTRACT FROM AUTHOR]
ISSN:	08954801
DOI:	10.1137/S0895480101395506