Skip to Main content Skip to Navigation
Conference papers

Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm

Alexander Zeh 1, 2 Wenhui Li 1 
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : We modify the Euclidean algorithm of Feng and Tzeng to decode Reed-Solomon (RS) codes up to the Sudan radius. The basic steps are the virtual extension to an Interleaved RS code and the reformulation of the multi-sequence shift-register problem of varying length to a multi-sequence problem of equal length. We prove the reformulation and analyze the complexity of our new decoding approach. Furthermore, the extended key equation, that describes the multi-sequence problem, is derived in an alternative polynomial way.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Alexander Zeh Connect in order to contact the contributor
Submitted on : Friday, December 2, 2011 - 1:13:57 PM
Last modification on : Friday, February 4, 2022 - 3:18:18 AM
Long-term archiving on: : Saturday, March 3, 2012 - 2:31:06 AM


Publisher files allowed on an open archive




Alexander Zeh, Wenhui Li. Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm. IEEE International Symposium on Information Theory and its Applications (ISITA), Oct 2010, Taichung, Taiwan. pp.986-990, ⟨10.1109/ISITA.2010.5649520⟩. ⟨hal-00647597⟩



Record views


Files downloads