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 metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00509209
Contributor : Daniel Augot <>
Submitted on : Tuesday, August 10, 2010 - 5:12:58 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: Thursday, June 30, 2011 - 1:21:13 PM

Files

ExtendedEKE.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

231

Files downloads

350