Construction of Optimal (r, δ)-Locally Recoverable Codes and Connection With Graph Theory
Chaoping Xing, Chen Yuan · IEEE Transactions on Information Theory · 2022
A block code is called a locally recoverable code (LRC for short) with$(r,\delta)$-locality, if subject to any$\delta -1$erasure failures, every symbol in the encoding can still be recovered by accessing at most$r$other symbols. Recently, it was discovered by several authors that a$q$-ary optimal$(r,\delta)$-LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than$q+1$. This is quite different from the classical$q$-ary MDS codes where it is conjectured that the code length is upper bounded by$q+1$(or$q+2$for some special cases). In this paper, we further investigate constructions of optimal$(r,\delta)$-LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of$\mathbb {F}_{q}$. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal$(r,\delta)$-LRC with code length$\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$, where$d$is the minimum distance. In particular, to our surprise, for$\delta =2$this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswamiet al.(2018) for$d\geq 7$. In addition, for$d=6$, we are able to remove the constraint required in Jin (2019) that$q$is even.