Optimal Locally Repairable Linear Codes
Wentu Song, Son Hoang Dau, Chau Yuen, Tiffany Jing Li · IEEE Journal on Selected Areas in Communications · 2014
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 [10]. The existing results on the existence and the construction of optimal (r, δ)alinear 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, δ)alinear codes with general r and δ. First, a structure theorem is derived for general optimal (r, δ)acodes 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, δ)alinear code can achieve the minimum distance bound in [10]. For four other cases the optimal (r, δ)acodes are shown to exist over a field of size q ≥ (k-1n), 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, δ)alinear codes, leaving only two cases in which the construction of optimal codes are not yet known.