Repairing Reed-Solomon Codes Evaluated on Subspaces
share
We consider the repair problem for Reed–Solomon (RS) codes, evaluated on an 𝔽_q-linear subspace U⊆𝔽_q^m of dimension d, where q is a prime power, m is a positive integer, and 𝔽_q is the Galois field of size q. For the case of q≥ 3, 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 𝔽_q, provided that ms≥ d(m-r). For the case of 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–Milenkovich to the range r<m-s, for a wide range of parameters.
READ FULL TEXT