Locally recoverable code: Difference between revisions

Revision as of 23:45, 4 November 2024

Revision as of 00:56, 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 Systems.<ref>{{Citation

<ref>{{Citation

|first1=A.

|last1=Barg

Line 76 ⟶ 75:

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>

== Tamo--BargTamo—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

Line 94 ⟶ 93:

|arxiv=1806.11492 }}</ref>

=== Tamo--BargTamo—Barg Construction ===

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

Line 105 ⟶ 104:

:• 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 g at all points in the set <math>T</math>.

=== Parameters of Tamo--BargTamo—Barg Codes ===

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

Line 117 ⟶ 116:

: To see this, <math>g</math> restricted to <math>A_j</math> can be described by a polynomial <math>h</math> of degree at most <math>{\text{deg}}(f(x))-2 = r + 1 - 2 = r - 1</math> thanks to the form of the elements in <math>V</math> (i.e. thanks to the fact that <math>f</math> is constant on <math>A_j</math>, and the <math>g_i</math>'s have 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 <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-BargTamo—Barg Construction ===

We will use <math>x^5 \in \mathbb F_{41} [x]</math> to construct <math>[15, 8, 6, 4]</math>-LRC. Notice that the degree of this polynomial is 5, and it is constant on <math>A_i</math> for <math>i \in \{1, \ldots, 8\}</math>, where <math>A_1 = \{1, 10, 16, 18, 37\}</math>, <math>A_2 = 2A_1</math>, <math>A_3 = 3A_1</math>, <math>A_4 = 4A_1</math>, <math>A_5 = 5A_1</math>, <math>A_6 = 6A_1</math>, <math>A_7 = 11A_1</math>, and <math>A_8 = 15A_1</math>: <math>A_1^5 = \{1\}</math>, <math>A_2^5 = \{32\}</math>, <math>A_3^5 = \{38\}</math>, <math>A_4^5 = \{40\}</math>, <math>A_5^5 = \{9\}</math>, <math>A_6^5 = \{27\}</math>, <math>A_7^5 = \{3\}</math>, <math>A_8^5 = \{14\}</math>. Hence, <math>x^5</math> is a <math>(4,8)</math>-good polynomial over <math>\mathbb F_{41}</math> by the definition. Now, we will use this polynomial to construct a code of dimension <math>k = 8</math> and length <math>n = 15</math> over <math>\mathbb F_{41}</math>. The locality of this code is 4, which will allow us to recover a single server failure by looking at the infromationinformation contained in at most 4 other servers.

Next, let's us define the encoding polynomial: <math>f_a(x) = \sum_{i=0}^{r - 1} f_i(x)x^i</math>, where <math>f_i(x) = \sum_{i=0}^{\frac{k}{r} - 1} a_{i,j}g(x)^j</math>. So, <math>f_a(x) =</math> <math>a_{0,0} +</math> <math>a_{0,1}x^5 +</math> <math>a_{1,0}x +</math> <math>a_{1,1}x^6 +</math> <math>a_{2,0}x^2 +</math> <math>a_{2,1}x^7 +</math> <math>a_{3,0}x^3 +</math> <math>a_{3,1}x^8</math>.

Thus, we can use the obtained encoding polynomial if we take our data to encode as the row vector <math>a = </math> <math>(a_{0,0}, a_{0,1}, a_{1,0}, a_{1,1}, a_{2,0}, a_{2,1}, a_{3,0}, a_{3,1})</math>. Encoding the vector <math>m</math> to a length 15 message vector <math>c</math> by multiplying <math>m</math> by the generator matrix