Locally recoverable code: Difference between revisions

Revision as of 00:57, 5 November 2024

Revision as of 07:58, 5 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" |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|Cloud Storage]] Systems.<ref>{{Citation

|first1=A.

|last1=Barg

Line 57:

}}</ref>

An <math>[n, k, d, r]_{q}</math> LRC is an <math>[n, k, d]_{q}</math> [[linear code]] such that there is a function <math>f_{i}</math> that takes as input <math>i</math> and a set of <math>r</math> other [[Coordinate system|coordinates]] of a codeword <math>c = (c_{1}, \ldots, c_{n}) \in C</math> different from <math>c_{i}</math>, and outputs <math>c_{i}</math>.

==Definition==

Line 77:

== Tamo—Barg Codes ==

Let <math>f</math> ∈ <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 <math>r+1</math>,

Line 99:

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

:• Consider the following <math>\mathbb F_{q}</math> -[[vector space]] of polynomials

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

Line 108:

:• '''Length.''' The length is the number of evaluation points. Because the sets <math>A_i</math> are 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 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 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 at most <math>k</math>, so the minimum distance equals <math>(r+1)\ell-((r+1)-2+s(r+1))</math>.

:• '''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>.

Line 139:

For example, the encoding of information vector <math>m = (1, 1, 1, 1, 1, 1, 1, 1)</math> gives the codeword <math>c = mG = (8, 8, 5, 9, 21, 3, 36, 31, 32, 12, 2, 20, 37, 33, 21)</math>.

Observe that we constructed an optimal LRC; therefore, using the [[Singleton bound]], we have that the distance of this code is <math>d = n - k - \left\lceil\frac{k}{r}\right\rceil + 2 = 15 - 8 - 2 + 2 = 7</math>. Thus, we can recover any 6 erasures from our codeword by looking at no more than 8 other components.

==Locally Recoverable Codes with Availability==