New Constructions of Optimal Locally Repairable Codes With Super-Linear Length

作者：Xiangliang Kong, Xin Wang, Gennian Ge · 发表于：IEEE Transactions on Information Theory · 年份：2021 · DOI：10.1109/tit.2021.3103330 · 被引用次数：26 · 研究领域：Advanced Data Storage Technologies、Caching and Content Delivery、Error Correcting Code Techniques

As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRCs, bounds and constructions of the corresponding optimal codes are of particular concerns. In this work, codes with (r,δ)-locality which have optimal minimal distance w.r.t. the bound given by Prakash et al. are considered. Through parity-check matrix approach, constructions of both optimal (r,δ)-LRCs with all symbol locality ( (r,δ)a-LRCs) and optimal (r,δ)-LRCs with information locality ( (r,δ)i-LRCs) are provided. As a generalization of a work of Xing and Yuan, these constructions are built on a connection between sparse hypergraphs and optimal (r,δ)-LRCs. With the help of constructions of large sparse hypergraphs, the lengths of codes obtained from our construction can be super-linear in the alphabet size. This improves upon previous constructions when the minimal distance of the code is at least 3δ+1. As two applications, optimal H-LRCs with super-linear lengths and GSD codes with unbounded lengths are also constructed.