A Link between Guruswami–Sudan’s List–Decoding and Decoding of Interleaved Reed–Solomon Codes

Abstract—The Welch–Berlekamp approach for Reed–Solomon (RS) codes forms a bridge between classical syndrome–based decoding algorithms and interpolation–based list–decoding pro-cedures 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. Index Terms—Guruswami–Sudan (GS) interpolation, Reed– Solomon (RS) codes, Interleaved Reed–Solomon (IRS) code