Skip to Main content Skip to Navigation
New interface
Conference papers

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 algorithmpsilas complexity. Furthermore, we indicate how to adapt the fundamental iterative algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Daniel Augot Connect in order to contact the contributor
Submitted on : Tuesday, August 10, 2010 - 5:12:58 PM
Last modification on : Friday, January 21, 2022 - 3:14:51 AM
Long-term archiving on: : Thursday, June 30, 2011 - 1:21:13 PM


Files produced by the author(s)




Daniel Augot, Alexander Zeh. On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm. Information Theory, 2008. ISIT 2008. IEEE International Symposium on, Jul 2008, Toronto, Canada. pp.2620-2624, ⟨10.1109/ISIT.2008.4595466⟩. ⟨inria-00509209⟩



Record views


Files downloads