Repairing Reed–Solomon Codes Evaluated on Subspaces

Abstract

We consider the repair problem for Reed-Solomon (RS) codes, evaluated on an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{q}$</tex> -linear subspace <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$U \subseteq \mathbb{F}_{q^{m}}$</tex> of dimension <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> is a prime power, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> is a positive integer, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{q}$</tex> is the Galois field of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> . For <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q &gt; 2$</tex> , we show the existence of a linear repair scheme for the RS code of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n=q^{d}$</tex> and codimension <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q^{s}, s &lt; d$</tex> , evaluated on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$U$</tex> , in which each of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n-1$</tex> surviving nodes transmits only <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex> symbols of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{q}$</tex> , provided that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$ms\geq d(m-r)$</tex> . For the case <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q=2$</tex> , we prove a similar result, with some restrictions on the evaluation linear subspace <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$U$</tex> . 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.

Topics & Concepts