TY - GEN
T1 - On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm
AU - Augot, Daniel
AU - Zeh, Alexander
PY - 2008/9/29
Y1 - 2008/9/29
N2 - 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.
AB - 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.
KW - (Extended) Key Equation
KW - Guruswami-Sudan algorithm
KW - List decoding
KW - Polynomial interpolation
KW - Reed-Solomon codes
U2 - 10.1109/ISIT.2008.4595466
DO - 10.1109/ISIT.2008.4595466
M3 - Conference contribution
AN - SCOPUS:52349089005
SN - 9781424422579
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2620
EP - 2624
BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Y2 - 6 July 2008 through 11 July 2008
ER -