Complete Characterizations of Optimal Locally Repairable Codes With Locality 1 and <inline-formula> <tex-math notation="LaTeX">$K-1$ </tex-math></inline-formula>

Abstract

A locally repairable code (LRC) is a [n, k, d] linear code with length n, dimension k, minimum distance d and locality r, which means that every code symbol can be repaired by at most r other symbols. LRCs have become an important candidate in distributed storage systems due to their relatively low I/O cost. An LRC is said to be optimal if its minimum distance meets one of the Singleton-like bounds. This paper considers the optimal constructions of LRCs with locality r = 1 and r = k - 1, which involves three types: r-local LRCs, (r, δ)-LRCs and LRCs with t-availability. Specifically, we first prove that the existence of an optimal LRC with locality r = 1 is equivalent to that of an MDS code with certain parameters. Thus we can completely characterize the three types of optimal LRCs with r = 1 based on some known constructions of MDS codes. Near MDS codes is a special class of sub-optimal linear code whose minimum distance d = n - k and the i-th generalized Hamming weight achieves the generalized Singleton bound for 2 ≤ i ≤ k. For r = k - 1, we have established the connections between optimal r-local LRCs/ LRCs with t-availability and near MDS codes. Such connections can help to construct optimal LRCs with r = k - 1 from some known classes of near MDS codes.

Keywords

• Distributed storage systems
• erasure codes
• maximum distance separable (MDS) codes
• near MDS codes
• locally repairable codes