Papers for

network coding specialists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Reed Solomon codes exact repair extension degrees identified

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

Sun 25 OctInformation Theory
The gist
Reed Solomon codes are a way to protect data by spreading it over many parts. Fixing or repairing these codes efficiently needs extra data parts, called extension degrees. The authors figured out the exact smallest number of these parts needed to perfectly fix the data under certain conditions. They also showed that even if the repair method isn’t simple (nonlinear), the smallest number of parts needed doesn’t get any smaller than in linear methods. This helps understand the limits of how efficiently data can be repaired.
Open → 2610.34377v1