Advances in Mathematics of Communications · 2010 · 23 citations · 18 references
Natural SciencesComputer ScienceMathematicsAlgebraAlgorithmsTheory Of ComputationAlgebraic GeometryCoding TheoryError Control CodingError-correcting CodesAlgebraic Geometry CodesAlgebraic-geometric CodesDecoding AlgorithmsInterpolation ConstraintsLinear CodesList DecodingReed-solomon CodesReed-solomon Coding
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.
18
The Magma Algebra System I: The User Language
Wieb Bosma, John Cannon, Catherine Playoust · Journal of Symbolic Computation · 1997 · 7.4K citations
Introduction to Commutative Algebra.
D. J. Lewis, B. R. McDonald, M. F. Atiyah et al. · American Mathematical Monthly · 1970 · 1.8K citations