On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm

Daniel Augot (1) , Alexander Zeh (1)

1 SECRET - Security, Cryptology and Transmissions

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.

Domaines: Théorie de l'information [cs.IT]; Théorie de l'information et codage [math.IT]

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⟩