Storage codes from binary BCH codes approach perfect efficiency
Asymptotically unit-rate storage codes from binary BCH codes
Information Theory
Summary
The paper studies special codes that let you store data on a network, where each stored piece can be recovered from its neighbors’ data. It proves that certain binary BCH codes used in these networks get very close to perfect efficiency, meaning almost all the space is used for useful data as the network grows. The authors use mathematical tools involving polynomials to show how this works and even give precise formulas for some cases. This means better designs for storage that can recover errors while using very little extra space.
What this means in practice
- •For distributed storage engineers: Use BCH-based storage codes to design systems that recover lost data from neighbors with minimal storage overhead as the system scales.
- •For network code designers: Incorporate high-rate full-parity codes on triangle-free graphs to improve error correction with near-optimal storage efficiency under fixed error budgets.
A theory result. No direct application yet.
Authors
Aryeh Lev Zabokritskiy
Abstract
A storage code on a graph assigns a symbol to each vertex so that the symbol can be recovered from its neighbors. We prove that the binary full-parity storage codes on triangle-free coset graphs of primitive BCH codes have rate tending to one for every fixed error-correction capability of at least two. The conclusion also holds for an increasing error budget under an explicit growth condition. The proof bounds the binary rank of convolution matrices associated with polynomial maps. Low coordinate degree forces cancellation in the polynomial representing the image, and a polynomial rank bound converts this cancellation into a quantitative estimate for the storage rate. For the double-error-correcting family over $\mathbb{F}_{2^m}$, we prove that the storage deficiency is $Θ(((1+\sqrt{5})/4)^m)$. This refinement follows from an exact Fibonacci formula for a polynomial coefficient rank and a matching exponential lower bound after finite-field evaluation.