Decoding interleaved Reed-Solomon codes over noisy channels (Q2373723)

The authors provide an algorithm for the solution of the simultaneous polynomial reconstruction (SPR) problem: For parameters \(n, k, t, r \in \mathbb N\) and pairwise distinct elements \(z_1, \dots, z_n\) of a finite field \(\mathbb F\), an instance of SPR is a set of tuples \(\langle y_{i,1},\dots , y_{i,r}\rangle_{i=1}^n\) with entries in \(\mathbb F\) that satisfies the following: There exists an \(I\in \{1, \ldots, n\}\) of cardinality \(t\) and polynomials \(p_1, \dots, p_r \in \mathbb F[x]\) of degree less than \(k\) such that \(p_j(z_i)= y_{i, j}\) for all \(i\in I\) and \(j \in \{1, \dots, n\}\). A coding theoretic application of their algorithm in the setting of interleaved Reed-Solomon decoding in the non-binary symmetric channel (NBSC) model is then discussed. The probabilistic algorithm presented allows for efficient transmission arbitrarily close to the channel capacity in the NBSC model.