1. Repairing Reed–Solomon Codes Evaluated on Subspaces
- Author
-
Yaron Shany, Sarit Buzaglo, Amit Berman, Itzhak Tamo, and Avner Dor
- Subjects
Combinatorics ,Integer ,Reed–Solomon error correction ,Scheme (mathematics) ,Galois theory ,Dimension (graph theory) ,Codimension ,Library and Information Sciences ,Linear subspace ,Prime power ,Mathematics ,Computer Science Applications ,Information Systems - 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 , 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.
- Published
- 2022
- Full Text
- View/download PDF