Improved Singleton-type Bounds for Locally Repairable Codes
Antti Pöllänen, Thomas Westerbäck, Ragnar Freij-Hollanti, Camilla Hollanti · arXiv (Cornell University) · 2016
Locally repairable codes (LRCs) are error correcting codes used in distributed data storage. Besides a global level, they enable errors to be corrected locally, reducing the need for communication between storage nodes. There is a close connection between almost affine LRCs and matroid theory which can be utilized to construct good LRCs and derive bounds on their performance. This article presents two improvements to such results in [T. Westerb\ack et al., On the Combinatorics of Locally Repairable Codes, Arxiv: 1501.00153]: The class of parameters $(n,k,d,r,\delta)$ for which there exists a matroid achieving the generalized Singleton bound for LRCs, is expanded. Also, an improved lower bound is given for $d_{\rm{max}}(n,k,r,\delta)$, the maximal achievable minimum distance $d$ that a matroid with parameters $(n,k,r,\delta)$ can have. This bound is proved to be optimal for the main class of matroids used to derive the existence bounds in [T. Westerb\ack et al., On the Combinatorics of Locally Repairable Codes, Arxiv: 1501.00153] and in this article. The results obtained directly translate to similar results on LRCs using the connection between them and matroids.