Abstract | ||
---|---|---|
We consider the problem of list decoding algebraic-geometry codes. We define a general class of one-point algebraic-geometry codes encompassing, among others, Reed-Solomon codes, Hermitian codes and norm-trace codes. We show how for such codes the interpolation constraints in the Guruswami-Sudan list-decoder, can be rephrased using a module formulation. We then generalize an algorithm by Alekhnovich [2], and show how this can be used to efficiently solve the interpolation problem in this module reformulation. The family of codes we consider has a number of well-known members, for which the interpolation part of the Guruswami-Sudan list decoder has been studied previously. For such codes the complexity of the interpolation algorithm we propose, compares favorably to the complexity of known algorithms. |
Year | DOI | Venue |
---|---|---|
2010 | 10.3934/amc.2010.4.485 | ADVANCES IN MATHEMATICS OF COMMUNICATIONS |
Keywords | Field | DocType |
List-decoding,algebraic geometry codes,Alekhnovich's algorithm | Discrete mathematics,Concatenated error correction code,Sequential decoding,Algebra,Block code,Serial concatenated convolutional codes,Raptor code,Linear code,Tornado code,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
4 | 4 | 1930-5346 |
Citations | PageRank | References |
10 | 0.63 | 14 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Beelen | 1 | 116 | 15.95 |
Kristian Brander | 2 | 30 | 1.41 |