Technical Program

Paper Detail

Paper IDM.2.5
Paper Title Complete Characterization of Optimal LRCs with Minimum Distance 6 and Locality 2: Improved Bounds and Constructions
Authors Weijun Fang, Bin Chen, Shu-Tao Xia, Tsinghua University, China; Fang-Wei Fu, Nankai University, China
Session M.2: Codes for Distributed Storage II
Presentation Lecture
Track Coding for Storage and Memories
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Locally repairable codes (LRCs) with locality $r$ were introduced to recover an erased code symbol by accessing at most $r$ other code symbols. An LRC achieving the well-known Singleton-type bound is called an optimal LRC. Constructing optimal LRCs has been a hot topic of coding theory in recent years. Similar to the famous MDS conjecture, the maximum code length of an optimal LRC has been investigated by Guruswami \emph{et al.} (TIT2019) and some constructions of optimal LRCs with large code length are also presented by Jin (TIT2019) and Xing and Yuan (arXiv2018). In this paper, we consider the maximum code length of optimal LRCs with minimum distance 6 and locality 2. Firstly, we give a complete characterization for optimal LRCs with $d=6$ and $r=2$, which shows that the existence of such an LRC is equivalent to the existence of a special subset of lines of finite projective plane $PG(2, q)$. Based on this characterization, we generalize the results of Chen \emph{et al.} (ISIT2018) and present two new constructions of optimal $(n, d=6; r=2)$-LRCs with $n=3(q+\sqrt{q}+1)$ and $n=3(2q-4)$, respectively. By using the techniques of line-point incidence matrix and Johnson bound, we show that the code length of any $q$-ary optimal LRCs with $d=6$ and $r=2$ must be bounded by $O(q^{1.5})$. To the best of our knowledge, both of the code length of our new constructions and upper bounds are better than the previously known ones. Moreover, we also determine the exact value of the maximum code length of $q$-ary optimal LRCs with $d=6$ and $r=2$ for $q=4,5$.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!