betaFeedback

Reading v1View latest version

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 Fq\mathbb{F}_q-linear repair at the cut-set bound from every prescribed set of dd helpers. Let s=d−k+1s=d-k+1, and let Qs(n)Q_s(n) be the minimum product of nn pairwise coprime integers, each at least ss. For every prime power qq and all 3≤k<d<n≤2d−23\le k<d<n\le2d-2, we prove that the minimum degree over Fq\mathbb{F}_q is exactly sQs(n)sQ_s(n). 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 n>2d−2n>2d-2, 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 Fp\mathbb{F}_p-linear repair scheme on the same code, where pp is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.

Paper details

vlnc:W_vp643rt6
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…