Optimal locally repairable linear codes

Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n,k,d] linear code having all-symbol (r,δ)-locality, denoted as (r,δ)a, is considered optimal if it has the actual highest minimum distance of any code of the given parameters n,k,r and δ. A minimum distance bound is given in. The existing results on the existence and the construction of optimal (r, δ) a linear codes are limited to only two small regions within this special case, namely, i) m=0 and ii) m≥ (v+δ-1)>(δ-1) and δ=2, where m=n mod(r+δ-1) and v=k mod r. This paper investigates the properties and existence conditions for optimal (r,δ)a linear codes with general r and δ. First, a structure theorem is derived for general optimal (r,δ)a codes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and δ is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no (r,δ)a linear code can achieve the minimum distance bound in. For four other cases the optimal (r,δ)a codes are shown to exist over a field of size q≥(n/k-1), deterministic constructions are proposed. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on optimal (r,δ) a linear codes, leaving only two cases in which the construction of optimal codes are not yet known. © 1983-2012 IEEE