Locally recoverable code: Difference between revisions

Revision as of 12:36, 25 September 2024

Revision as of 18:26, 4 November 2024

Line 3:

{{AfC topic|stem}}

{{AfC submission|||ts=20240924004443|u=Yaroslav-Marta|ns=118}}

{{AfC submission|t||ts=20231130204613|u=Yaroslav-Marta|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

'''Locally Recoverable Codes''' are a family of error correction codes that were introduced first by D. S. Papailiopoulos and A. G. Dimakis<ref>{{Citation

|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |title="Locally Repairable Codes" |chapter=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publisher=IEEE International Symposium on Information Theory |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 }}</ref> and have been widely studied in Information theory due to their applications related to Distributive and Cloud Storage Systems.

<ref>{{Citation

Line 23:

|arxiv=1603.08876

|isbn=978-1-4673-7704-1

}}</ref> <ref>{{Citation

<ref>{{Citation

|first1=V. R.

|last1=Cadambe

Line 36 ⟶ 35:

|issue=11

|doi=10.1109/TIT.2015.2477406

}}</ref><ref>{{Citation

<ref>{{Citation

|first1=A.

|last1=Dukes

Line 51 ⟶ 49:

|issue=6

|doi= 10.1007/s10623-022-01046-y

}}</ref><ref>{{Citation

<ref>{{Citation

|first1=K.

|last1=Haymaker

Line 72 ⟶ 69:

An <math>[n, k, d, r]_{q}</math> ''locally recoverable code'' (LRC) is an <math>[n, k, d]_{q}</math> linear code <math>C \in \mathbb F_q^n</math> with locality <math>r</math>.

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" |chapter=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publisher=IEEE International Symposium on Information Theory |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 }}</ref>, i.e. for every <math>i \in \{1, \ldots, n\}</math>, the space of linear equations of the code contains 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 96 ⟶ 93:

::– <math>A_{i}</math> ∩ <math>A_{j}</math> = ∅ for any <math>i</math> ≠ <math>j</math>.

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>.

=== Tamo--Barg Construction ===

Line 151 ⟶ 148:

'''Definition'''<ref>{{Citation

|first1=P. |last1=Huang |first2=E. |last2=Yaakobi |first3=H.|last3=Uchikawa |first4=P.H.|last4=Siegel |title="Linear locally repairable codes with availability" |chapter=Linear locally repairable codes with availability |pages=1871–1875 |___location=Hong Kong, China |publisher=IEEE International Symposium on Information Theory |date=2015 |doi=10.1109/ISIT.2015.7282780|isbn=978-1-4673-7704-1 }}</ref> A code <math>C</math> has all-symbol locality <math>r</math> and availability <math>t</math> if every code symbol can be recovered from <math>t</math> disjoint repair sets of other symbols, each set of size at most <math>r</math> symbols. Such codes are called <math>(r,t)_a</math>-LRC.

'''Theorem'''<ref>{{Citation |first1=I. |last1=Tamo |first2=A. |last2=Barg |title="Bounds on locally recoverable codes with multiple recovering sets" |chapter=Bounds on locally recoverable codes with multiple recovering sets |pages=691–695 |___location=Honolulu, HI, USA |publisher=2014 IEEE International Symposium on Information Theory |date=2014 |doi=10.1109/ISIT.2014.6874921|arxiv=1402.0916 |isbn=978-1-4799-5186-4 }}</ref> The minimum distance of <math>[n,k,d]_q</math>-LRC having locality <math>r</math> and availability <math>t</math> satisfies the upper bound

<div style="text-align: center;"><math>d \leq n - \sum_{i=0}^{t} \left\lfloor\frac{k-1}{r^i}\right\rfloor</math></div>.

If the code is systematic and locality and availability apply only to its information symbols, then the code has information locality <math>r</math> and availability <math>t</math>, and is called <math>(r,t)_i</math>-LRC.

'''Theorem'''<ref>{{Citation