Locally recoverable code

Introduction

Locally Recoverable Codes are a family of error correction codes that were introduced first by D. S. Papailiopoulos and A. G. Dimakis and have been widely studied in Information theory due to their applications related to Distributive and Cloud Storage Systems.

A locally recoverable code is a linear code such that there is a function that takes set of coordinates of a codeword and some specific coordinate and outputs an appropriate coordinate.

Definition

Let ${\displaystyle C}$  be a ${\displaystyle [n,k,d]_{q}}$  linear code. For ${\displaystyle i\in \{1,\ldots ,n\}}$ , let us denote by ${\displaystyle r_{i}}$  the minimum number of other coordinates we have to look at to recover an erasure in coordinate ${\displaystyle i}$ . The number ${\displaystyle r_{i}}$  is said to be the locality of the ${\displaystyle i}$ -th coordinate of the code. The locality of the code is defined as

${\displaystyle r={\textrm {max}}\{r_{i}|i\in \{1,\ldots ,n\}\}}$ 

An ${\displaystyle [n,k,d,r]_{q}}$  locally recoverable code (LRC) is an ${\displaystyle [n,k,d]_{q}}$  linear code ${\displaystyle C\in F_{q}^{n}}$  with locality ${\displaystyle r}$ .

Let ${\displaystyle C}$  be an ${\displaystyle [n,k,d]_{q}}$ -locally recoverable code. Then a deleted component can be recovered linearly, i.e. for every ${\displaystyle i\in \{1,\ldots ,n\}}$ , the space of linear equations of the code contains elements of the form ${\displaystyle x_{i}=f(x_{i},\ldots ,x_{i_{r}})}$ , where ${\displaystyle i_{j}\neq i}$ .

Optimal Locally Recoverable Codes

Theorem 1.3 Let ${\displaystyle n=(r+1)s}$  and let ${\displaystyle C}$  be an ${\displaystyle [n,k,d]_{q}}$ -locally recoverable code having ${\displaystyle s}$  disjoint locality sets of size ${\displaystyle r+1}$ . Then,

${\displaystyle d\leq n-k-\lceil {\frac {k}{r}}\rceil +2}$ 

An ${\displaystyle [n,k,d,r]_{q}}$ -LRC ${\displaystyle C}$  is sai to be optimal if the minimum distance of ${\displaystyle C}$  satisfies

${\displaystyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2}$ 

Tamo-Barg Codes

Let f ∈ ${\displaystyle F_{q}}$ [X] be a polynomial and let l be a positive integer. Then f is said to be (r, l)-good if

• f has degree r + 1,

• there exist ${\displaystyle A_{1}}$  , . . . ,${\displaystyle A_{l}}$  distinct subsets of ${\displaystyle F_{q}}$  such that

– for any i ∈ {1, . . ., l}, f (${\displaystyle A_{i}}$  ) = {${\displaystyle t_{i}}$ } for some ti ∈ ${\displaystyle F_{q}}$  , i.e. f is constant on Ai ,

– #${\displaystyle A_{i}}$  = r + 1,

– ${\displaystyle A_{i}}$  ∩ ${\displaystyle A_{j}}$  = ∅ for any i ≠ j.

We say that {${\displaystyle A_{1}}$  , . . . , ${\displaystyle A_{l}}$ } is a splitting covering for f .

Tamo Barg Construction

References