Title | ||
---|---|---|
Construction of Optimal (<italic>r</italic>, δ)-Locally Recoverable Codes and Connection With Graph Theory |
Abstract | ||
---|---|---|
A block code is called a locally recoverable code (LRC for short) with
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(r,\delta)$ </tex-math></inline-formula>
-locality, if subject to any
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta -1$ </tex-math></inline-formula>
erasure failures, every symbol in the encoding can still be recovered by accessing at most
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>
other symbols. Recently, it was discovered by several authors that a
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>
-ary optimal
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(r,\delta)$ </tex-math></inline-formula>
-LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q+1$ </tex-math></inline-formula>
. This is quite different from the classical
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>
-ary MDS codes where it is conjectured that the code length is upper bounded by
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q+1$ </tex-math></inline-formula>
(or
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q+2$ </tex-math></inline-formula>
for some special cases). In this paper, we further investigate constructions of optimal
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(r,\delta)$ </tex-math></inline-formula>
-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
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>
. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(r,\delta)$ </tex-math></inline-formula>
-LRC with code length
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$ </tex-math></inline-formula>
, where
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>
is the minimum distance. In particular, to our surprise, for
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\delta =2$ </tex-math></inline-formula>
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 Guruswami
<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al.</i>
(2018) for
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d\geq 7$ </tex-math></inline-formula>
. In addition, for
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d=6$ </tex-math></inline-formula>
, we are able to remove the constraint required in Jin (2019) that
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>
is even. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1109/TIT.2022.3157612 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
Distributed storage,locally repairable codes,Singleton-like bounds,maximum distance separable (MDS) codes,hypergraph | Journal | 68 |
Issue | ISSN | Citations |
7 | 0018-9448 | 0 |
PageRank | References | Authors |
0.34 | 24 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chaoping Xing | 1 | 916 | 110.47 |
Chen Yuan | 2 | 0 | 0.34 |