Repairing Reed–Solomon Codes Evaluated on Subspaces

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.