Name
Abstract | ||
|---|---|---|
A Reed-Solomon code of length n can be list decoded using the well-known Guruswami-Sudan algorithm. By a result of Alekhnovich (2005) the interpolation part in this algorithm can be done in complexity O(s^4l^4nlog^2nloglogn), where l denotes the designed list size and s the multiplicity parameter. The parameters l and s are sometimes considered to be constants in the complexity analysis, but for high rate Reed-Solomon codes, their values can be very large. In this paper we will combine ideas from Alekhnovich (2005) and the concept of key equations to get an algorithm that has complexity O(sl^4nlog^2nloglogn). This compares favorably to the complexities of other known interpolation algorithms. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.jsc.2010.03.010 | J. Symb. Comput. |
Keywords | Field | DocType |
Reed–Solomon codes,list size,high rate Reed-Solomon code,List decoding,complexity O,Reed-Solomon code,interpolation part,Interpolation,parameters l,key equation,complexity analysis,interpolation algorithm,well-known Guruswami-Sudan algorithm,Guruswami–Sudan algorithm | Discrete mathematics,Interpolation,Arithmetic,Reed–Solomon error correction,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
45 | 7 | Journal of Symbolic Computation |
Citations | PageRank | References |
20 | 0.78 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Beelen | 1 | 116 | 15.95 |
| Kristian Brander | 2 | 30 | 1.41 |