- Title
- A parametric approach to list decoding of Reed-Solomon codes using interpolation
- Creator
- Ali, Mortuza; Kiujper, Margreta
- Date
- 2011
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/74219
- Identifier
- vital:7221
- Identifier
- ISSN:0018-9448
- Abstract
- Abstract—In this paper, we present a minimal list decoding algorithm for Reed-Solomon (RS) codes. Minimal list decoding for a code refers to list decoding with radius , where is the minimum of the distances between the received word and any codeword in . We consider the problem of determining the value of as well as determining all the codewords at distance . Our approach involves a parametrization of interpolating polynomials of a minimal Gröbner basis . We present two efficient ways to compute . We also show that so-called re-encoding can be used to further reduce the complexity. We then demonstrate how our parametric approach can be solved by a computationally feasible rational curve fitting solution from a recent paper by Wu. Besides, we present an algorithm to compute the minimum multiplicity as well as the optimal values of the parameters associated with this multiplicity, which results in overall savings in both memory and computation
- Relation
- IEEE Transaction on Information Theory Vol. 57, no. 10 (2011), p. 6718-6728
- Rights
- Copyright IEEE
- Rights
- This metadata is freely available under a CCO license
- Subject
- Gröbner basis; List decoding; Predictable leading; Monomial; Rational interpolation; Reed-Solomon code; 0801 Artificial Intelligence and Image Processing
- Reviewed
- Hits: 601
- Visitors: 593
- Downloads: 2
| Thumbnail | File | Description | Size | Format |
|---|