Complete Characterizations of Optimal Locally Repairable Codes With Locality 1 and $K-1$

IEEE Access

Bin Chen¹  Yichong Xia² 

[1] Graduate School at Shenzhen, Tsinghua University, Shenzhen, China;School of Mathematics, Sun Yat-sen University, Guangzhou, China;

关键词: Distributed storage systems;    erasure codes;    maximum distance separable (MDS) codes;    near MDS codes;    locally repairable codes;   

DOI  :  10.1109/ACCESS.2019.2934769

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown