Locally recoverable code: Difference between revisions

Revision as of 20:19, 15 November 2024

Revision as of 21:25, 16 November 2024

Line 3:

{{Orphan|date=November 2024}}

'''Locally recoverable codes''' are a family of [[error correction code]]s 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" |chaptercontribution=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publishertitle=2012 IEEE International Symposium on Information Theory Proceedings |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 |arxiv=1206.3804 }}</ref> and have been widely studied in [[information theory]] due to their applications related to distributive and [[cloud storage]] systems.<ref>{{Citation

|first1=A.

|last1=Barg

Line 10:

|first3=S.

|last3=Vlăduţ

|titlecontribution="Locally recoverable codes on algebraic curves"

|chapter=Locally recoverable codes on algebraic curves

|pages=1252–1256

|___location=Hong Kong, China

|publishertitle=2015 IEEE International Symposium on Information Theory

|date=2015

|doi=10.1109/ISIT.2015.7282656

Line 24 ⟶ 23:

|first2=A.

|last2=Mazumdar

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

|pages=5787–5794

|journal=IEEE Transactions on Information Theory

Line 38 ⟶ 37:

|first3=G.

|last3=Micheli

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

|journal=Designs, Codes and Cryptography

|pages=1427–1436

Line 52 ⟶ 51:

|first3=G.

|last3=Matthews

|title="Locally Recoverable Codes with Availability t≥2''t''≥2 from Fiber Products of Curves"

|date=2022

|doi=10.3934/amc.2018020

Line 72 ⟶ 71:

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

|first1=V. |last1=Cadambe |first2=A. |last2=Mazumdar |title="An upper bound on the size of locally recoverable codes" |chaptercontribution=An upper bound on the size of locally recoverable codes |pages=1–5 |___location=Calgary, AB, Canada |publishertitle=2013 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 [[Disjoint sets|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 [[Hamming distance|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 78 ⟶ 77:

== Tamo–Barg codes ==

Let <math>f</math> ∈\in <math>\mathbb F_{q} [x]</math> be a [[polynomial]] and let <math>\ell</math> be a positive [[integer]]. Then <math>f</math> is said to be (<math>r</math>, <math>\ell</math>)-good if

:• <math>f</math> has [[Degree of a polynomial|degree]] <math>r+1</math>,

:• there exist distinct [[subset]]s <math>A_{1}</math> , . . .\ldots, <math>A_{\ell}</math> distinct [[Subset|subsets]] of <math>\mathbb F_{q}</math> such that

::– for any <math>i \in \{1, \ldots, \ell\}</math>, <math>f</math> (<math>A_{i}</math> ) = \{<math>t_{i}\}</math>} for some <math>t_{i}</math> ∈\in <math>\mathbb F_{q}</math> , i.e., <math>f</math> is [[Constant (mathematics)|constant]] on <math>A_{i}</math>,

::– #<math>\# A_{i}</math> = <math>r + 1</math>,

::– <math>A_{i}</math> ∩\cap <math>A_{j} = \varnothing</math> = ∅ for any <math>i</math> ≠\neq <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.

Line 97 ⟶ 96:

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" |chaptercontribution=A family of optimal locally recoverable codes |pages=686–690 |___location=Honolulu, HI, USA |publishertitle=2014 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> ≤\leq <math>\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>

<div style="text-align: center;"><math>V = \{\sum_{i=0}^s g_{i}(x)f(x)^i:{\text{deg}}(g_{i}(x)) \leq {\text{deg}}(f(x))-2\}</math></div>

:• Let <math>T</math> = <math display="inline">\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>.

=== Parameters of Tamo–Barg codes ===