Locally recoverable code: Difference between revisions

Revision as of 00:44, 24 September 2024

Revision as of 12:36, 25 September 2024

Line 6:

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-27752771–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

|first1=A.

Line 15:

|last3=Vlăduţ

|title="Locally recoverable codes on algebraic curves"

|chapter=Locally recoverable codes on algebraic curves

|pages=1252-1256

|pages=1252–1256

|___location=Hong Kong, China

|publisher=IEEE International Symposium on Information Theory

|date=2015

|doi=10.1109/ISIT.2015.7282656

|arxiv=1603.08876

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

}}</ref>

<ref>{{Citation

Line 27 ⟶ 30:

|last2=Mazumdar

|title="Bounds on the Size of Locally Recoverable Codes"

|pages=5787-57945787–5794

|publisherjournal=IEEE Transactions on Information Theory

|date=2015

|volume=61

|issue=11

|doi=10.1109/TIT.2015.2477406

}}</ref>

Line 40 ⟶ 45:

|last3=Micheli

|title="Optimal selection for good polynomials of degree up to five"

|journal=Designs, Codes and Cryptography

|pages=1427-1436

|pages=1427–1436

|date=2022

|volume=90

|issue=6

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

}}</ref>

Line 65 ⟶ 73:

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-27752771–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==

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

|first1=V. |last1=Cadambe |first2=A. |last2=Mazumdar |title="An upper bound on the size of locally recoverable codes" |chapter=An upper bound on the size of locally recoverable codes |pages=1-51–5 |___location=Calgary, AB, Canada |publisher=International Symposium on Network Coding |date=2013 |doi=10.1109/NetCod.2013.6570829|arxiv=1308.3200 |isbn=978-1-4799-0823-3 }}</ref> Let <math>n = (r+1)s</math> and let <math>C</math> be an <math>[n, k, d]_{q}</math>-locally recoverable code having <math>s</math> disjoint locality sets of size <math>r+1</math>. Then <div style="text-align: center;"><math>d \leq n - k - \left\lceil\frac{k}{r}\right\rceil + 2</math></div>

An <math>[n, k, d, r]_{q}</math>-LRC <math>C</math> is said to be optimal if the minimum distance of <math>C</math> satisfies <div style="text-align: center;"><math>d = n - k - \left\lceil\frac{k}{r}\right\rceil + 2</math></div>

Line 89 ⟶ 97:

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-175167–175 |publisherjournal=IEEE Transactions on Information Theory |date=2020 |volume=66 |doi=10.1109/TIT.2019.2939464

|arxiv=1806.11492 }}</ref>.

=== Tamo--Barg Construction ===

The Tamo--Barg construction utilizes good polynomials.<ref>{{Citation

|first1=I.|last1=Tamo |first2=A. |last2=Barg |title="A family of optimal locally recoverable code" |chapter=A family of optimal locally recoverable codes |pages=686-690686–690 |___location=Honolulu, HI, USA |publisher=IEEE International Symposium on Information Theory |date=2014 |doi=10.1109/ISIT.2014.6874920|isbn=978-1-4799-5186-4 }}</ref>

:• Suppose that a <math>(r, \ell)</math>-good polynomial <math>f(x)</math> over <math>\mathbb F_{q}</math> is given with splitting covering <math>i \in \{1, \ldots, \ell\}</math>.

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

Line 143 ⟶ 151:

'''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-18751871–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-695691–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>.

Line 152 ⟶ 160:

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

|first1=A. |last1=Wang |first2=Z. |last2=Zhang |title="Repair locality with multiple erasure tolerance" |pages=6979-69876979–6987 |publisherjournal=IEEE Transactions on Information Theory |date=2014 |volume=60 |issue=11 |doi=10.1109/TIT.2014.2351404|arxiv=1306.4774 }}</ref> The minimum distance d of an <math>[n,k,d]_q</math> linear <math>(r,t)_i</math>-LRC satisfies the upper bound

<div style="text-align: center;"><math>d \leq n-k-\left\lceil\frac{t(k-1)+1}{t(r-1)+1}\right\rceil+2</math></div>.