2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.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
