All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD2-S6-T2.1
Paper Title Repairing Reed--Solomon Codes Evaluated on Subspaces
Authors Amit Berman, Sarit Buzaglo, Avner Dor, Yaron Shany, Samsung Israel R&D Center (SIRC), Israel; Itzhak Tamo, Tel Aviv University, Israel
Session D2-S6-T2: Reed-Solomon & MDS Codes
Chaired Session: Tuesday, 13 July, 23:40 - 00:00
Engagement Session: Wednesday, 14 July, 00:00 - 00:20
Abstract We consider the repair problem for Reed--Solomon (RS) codes, evaluated on an $\efq$-linear subspace $U\subseteq\efqm$ of dimension $d$, where $q$ is a prime power, $m$ is a positive integer, and $\efq$ 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 $\efq$, 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.