WorksComputer Science
Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound
Abstract
We study the minimum extension degree required for a Reed–Solomon code to admit exact -linear repair at the cut-set bound from every prescribed set of helpers. Let , and let be the minimum product of pairwise coprime integers, each at least . For every prime power and all , we prove that the minimum degree over is exactly . When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with , we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an -linear repair scheme on the same code, where is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.