Skip to Main content Skip to Navigation
Conference papers

A link between Guruswami-Sudan's list-decoding and decoding of interleaved Reed-Solomon codes

Alexander Zeh 1, 2 Christian Senger 2 
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : The Welch-Berlekamp approach for Reed-Solomon (RS) codes forms a bridge between classical syndrome-based decoding algorithms and interpolation-based list-decoding procedures for list size ℓ = 1. It returns the univariate error-locator polynomial and the evaluation polynomial of the RS code as a y-root. In this paper, we show the connection between the Welch-Berlekamp approach for a specific Interleaved Reed-Solomon code scheme and the Guruswami-Sudan principle. It turns out that the decoding of Interleaved RS codes can be formulated as a modified Guruswami-Sudan problem with a specific multiplicity assignment. We show that our new approach results in the same solution space as the Welch-Berlekamp scheme. Furthermore, we prove some important properties.
Keywords : decoding irs list
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00647609
Contributor : Alexander Zeh Connect in order to contact the contributor
Submitted on : Friday, December 2, 2011 - 2:16:57 PM
Last modification on : Friday, February 4, 2022 - 3:17:41 AM
Long-term archiving on: : Saturday, March 3, 2012 - 2:31:25 AM

File

ISIT2010.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Alexander Zeh, Christian Senger. A link between Guruswami-Sudan's list-decoding and decoding of interleaved Reed-Solomon codes. IEEE International Symposium on Information Theory (ISIT), Jun 2010, Austin, United States. pp.1198-1202, ⟨10.1109/ISIT.2010.5513427⟩. ⟨hal-00647609⟩

Share

Metrics

Record views

197

Files downloads

146