101. Repairing Reed–Solomon Codes Evaluated on Subspaces.
- Author
-
Berman, Amit, Buzaglo, Sarit, Dor, Avner, Shany, Yaron, and Tamo, Itzhak
- Subjects
FINITE fields ,REED-Solomon codes ,FAULT tolerance (Engineering) - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF