Locally recoverable code: Difference between revisions

Revision as of 21:25, 16 November 2024

Revision as of 21:28, 16 November 2024

Line 66:

Let <math>C</math> be an <math>[n, k, d]_{q}</math>-locally recoverable code. Then an erased component can be recovered linearly,<ref>{{Citation

|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |title="Locally Repairable Codes" |chaptercontribution=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publisher=2012 IEEE International Symposium on Information Theory |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 |arxiv=1206.3804 }}</ref> i.e. for every <math>i \in \{1, \ldots, n\}</math>, the space of [[Linearlinear equation|linear equations ]]s of the code contains [[Element (mathematics)|elements]] of the form <math> x_{i} = f(x_{i_{1}}, \ldots, x_{i_{r}})</math>, where <math>i_{j} \neq i</math>.

==Optimal locally recoverable codes==

Line 90:

We say that {<math>A_{1},\ldots,A_{\ell}</math>} is a splitting covering for <math>f</math>.<ref>{{Citation |first1=G.

|last1=Micheli |title="Constructions of Locally Recoverable Codes Which are Optimal" |pages=167–175 |journal=IEEE Transactions on Information Theory |date=2020 |volume=66 |doi=10.1109/TIT.2019.2939464

|arxiv=1806.11492 }}</ref>

Line 100:

:• Let <math>s \leq \ell-1</math> be a positive [[integer]].

:• Consider the following <math>\mathbb F_{q}</math>-[[vector space]] of [[polynomial]]s <math display="block">V = \{\sum_{i=0}^s g_{i}(x)f(x)^i: \deg(g_{i}(x)) \leq \deg(f(x))-2\}.</math>

:• Let <math>T</math> = <math display="inline">T = \bigcup_{i=1}^\ell A_i</math>.

:• The code <math> \{ ev_{T}(g):g \in V \}</math> is an <math>((r+1)\ell,(s+1)r,d,r)</math>-optimal locally coverable code, where <math>ev_{T}</math> denotes evaluation of <math>g</math> at all points in the [[Set (mathematics)|set]] <math>T</math>.

Line 107:

:• '''Length.''' The length is the number of evaluation points. Because the [[Set (mathematics)|sets]] <math>A_i</math> are [[Disjoint sets|disjoint]] for <math>i \in \{1, \ldots, \ell\}</math>, the length of the code is <math>|T| = (r+1)\ell</math>.

:• '''Dimension.''' The [[dimension]] of the code is <math>(s+1)r</math>, for <math>s</math> ≤ <math>\ell-1</math>, as each <math>g_i</math> has [[Degree of a polynomial|degree]] at most <math>{\text{deg}}(f(x))-2</math>, covering a [[vector space]] of [[dimension]] <math>{\text{deg}}(f(x))-1=r</math>, and by the construction of <math>V</math>, there are <math>s+1</math> distinct <math>g_i</math>.

:• '''Distance.''' The [[Hamming distance|distance]] is given by the fact that <math>V \subseteq \mathbb F_q [x]_{\leq k}</math>, where <math>k = r + 1 - 2 + s(r+1)</math>, and the obtained code is the [[Reed–Solomon error correction|Reed-Solomon code]] of [[Degree of a polynomial|degree]] at most <math>k</math>, so the minimum [[Hamming distance|distance]] equals <math>(r+1)\ell-((r+1)-2+s(r+1))</math>.

Line 113:

:• '''Locality.''' After the erasure of the single component, the evaluation at <math>a_i \in A_i</math>, where <math>|A_i|=r+1</math>, is unknown, but the evaluations for all other <math>a \in A_i</math> are known, so at most <math>r</math> evaluations are needed to uniquely determine the erased component, which gives us the locality of <math>r</math>.

: To see this, <math>g</math> restricted to <math>A_j</math> can be described by a [[polynomial]] <math>h</math> of [[Degree of a polynomial|degree]] at most <math>{\text{deg}}(f(x))-2 = r + 1 - 2 = r - 1</math> thanks to the form of the [[Element (mathematics)|elements]] in <math>V</math> (i.e., thanks to the fact that <math>f</math> is [[Constant (mathematics)function|constant]] on <math>A_j</math>, and the <math>g_i</math>'s have [[Degree of a polynomial|degree]] at most <math>{\text{deg}}(f(x))-2</math>). On the other hand <math>|A_j \backslash \{a_j\}| = r</math>, and <math>r</math> evaluations uniquely determine a [[polynomial]] of [[Degree of a polynomial|degree]] <math>r-1</math>. Therefore <math>h</math> can be constructed and evaluated at <math>a_j</math> to recover <math>g(a_j)</math>.

=== Example of Tamo–Barg construction ===