BOUNDS ON THE LIST-DECODING RADIUS OF REED --SOLOMON CODES.
Saved in:
| Title: | BOUNDS ON THE LIST-DECODING RADIUS OF REED --SOLOMON CODES. |
|---|---|
| Authors: | Ruckestein, Gitit1 gitit@cs.technion.ac.il, Roth, Ron M.1 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 12362629 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: BOUNDS ON THE LIST-DECODING RADIUS OF REED --SOLOMON CODES. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ruckestein%2C+Gitit%22">Ruckestein, Gitit</searchLink><relatesTo>1</relatesTo><i> gitit@cs.technion.ac.il</i><br /><searchLink fieldCode="AR" term="%22Roth%2C+Ron+M%2E%22">Roth, Ron M.</searchLink><relatesTo>1</relatesTo><i> ronny@cs.technion.ac.il</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Discrete+Mathematics%22">SIAM Journal on Discrete Mathematics</searchLink>. 2003, Vol. 17 Issue 2, p171-195. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Reed-Solomon+codes%22">Reed-Solomon codes</searchLink><br /><searchLink fieldCode="DE" term="%22Digital+signal+processing+mathematics%22">Digital signal processing mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Error-correcting+codes%22">Error-correcting codes</searchLink><br /><searchLink fieldCode="DE" term="%22Block+designs%22">Block designs</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Sidon+sets%22">Sidon sets</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=12362629 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/S0895480101395506 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 171 Subjects: – SubjectFull: Reed-Solomon codes Type: general – SubjectFull: Digital signal processing mathematics Type: general – SubjectFull: Error-correcting codes Type: general – SubjectFull: Block designs Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Sidon sets Type: general Titles: – TitleFull: BOUNDS ON THE LIST-DECODING RADIUS OF REED --SOLOMON CODES. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ruckestein, Gitit – PersonEntity: Name: NameFull: Roth, Ron M. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: 2003 Type: published Y: 2003 Identifiers: – Type: issn-print Value: 08954801 Numbering: – Type: volume Value: 17 – Type: issue Value: 2 Titles: – TitleFull: SIAM Journal on Discrete Mathematics Type: main |
| ResultId | 1 |
