betaFeedback

WorksComputer Science

Minimum Extension Degrees for Reed-Solomon Codes:Exact Values and a Quadratic Transition

Abstract

We study the minimum extension degree of Reed-Solomon codes admitting exact linear repair of every failed coordinate from any dd surviving coordinates at the cut-set bound. Write 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. We locate the transition for the formula sQs(n)sQ_s(n) near n=d2n=d^2: for every fixed 0<ε<10<\varepsilon<1 and sufficiently large dd, the formula is exact up to (1−ε)d2(1-\varepsilon)d^2, whereas strict improvement is possible at every length at least (1+ε)d2(1+\varepsilon)d^2, uniformly over the base field and code dimension. The lower bound follows from an inequality for the cost of residual prime powers; the upper bound follows from an existing affine-plane construction. We also show that the full-helper coordinate-count bound is attained over sufficiently large base fields. Finally, nonlinear repair at cut-set equality induces linear repair over the prime field. Thus the degree bounds over that field remain valid, and the same transition holds when the repair base field is prime.

Paper details

vlnc:W_vp643rt6
Version
v2 · latest
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…