Bounds on the maximal minimum distance of linear locally repairable codes

Abstract

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. A generalized Singleton bound for linear LRCs with parameters (n; k; d; r; δ) was given in [N. Prakash et al., 'Optimal Linear Codes with a Local-Error-Correction Property', IEEE Int. Symp. Inf. Theory]. In this paper, a LRC achieving this bound is called perfect. Results on the existence and nonexistence of linear perfect (n; k; d; r; δ)-LRCs were given in [W. Song et al., 'Optimal locally repairable codes', IEEE J. Sel. Areas Comm.]. Using matroid theory, these existence and nonexistence results were later strengthened in [T. Westerbäck et al., 'On the Combinatorics of Locally Repairable Codes', Arxiv: 1501.00153], which also provided a general lower bound on the maximal achievable minimum distance dmax(n; k; r; δ) that a linear LRC with parameters (n; k; r; δ) can have. This article expands the class of parameters (n; k; d; r; δ) for which there exist perfect linear LRCs and improves the lower bound for dmax(n; k; r; δ). Further, this bound is proved to be optimal for the class of matroids that is used to derive the existence bounds of linear LRCs.