Repairing Reed–Solomon Codes Evaluated on Subspaces
A. L. Berman, Sarit Buzaglo, Avner Dor, Yaron Shany, Itzhak Tamo · IEEE Transactions on Information Theory · 2022
We consider the repair problem for Reed–Solomon (RS) codes, evaluated on an$\mathbb {F}_{q}$-linear subspace$U\subseteq \mathbb {F}_{q^{m}} $of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb {F}_{q}$is the Galois field of size$q$. For$q>2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}$,$s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb {F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least$1/3$) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme. Our result extend the construction of Dau–Milenkovic to the range$r < m-s$, for a wide range of parameters.