@inproceedings{ee00570b88a2462a9a0035129a50f84c,
title = "On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm",
abstract = "In 2000 Roth and Ruckenstein proposed an Extended Key Equation for solving the interpolation step in the Sudan decoding algorithm. Generalizing their idea, a sequence of key equations for the Guruswami-Sudan (GS) algorithm, which is able to list decode a Reed-Solomon code with arbitrary rate, is derived. This extension allows a reduction of the number of equations and therefore a reduction of the algorithm's complexity. Furthermore, we indicate how to adapt the Fundamental Iterative Algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.",
keywords = "(Extended) Key Equation, Guruswami-Sudan algorithm, List decoding, Polynomial interpolation, Reed-Solomon codes",
author = "Daniel Augot and Alexander Zeh",
year = "2008",
month = jan,
day = "1",
doi = "10.1109/ISIT.2008.4595466",
language = "English",
isbn = "9781424422579",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2620--2624",
booktitle = "Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008",
note = "2008 IEEE International Symposium on Information Theory, ISIT 2008 ; Conference date: 06-07-2008 Through 11-07-2008",
}