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.

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=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-\lceil {\frac {k}{r}}\rceil +2}$ 

By rewriting this new bound as

${\displaystyle d\leq n-k+1-(\lceil {\frac {k}{r}}\rceil -1)}$ 

we can see that some of the maximum possible minimum distance is sacrificed to obtain the locality ${\displaystyle r}$  in our code.

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 coordinte and outputs an appropriate coordinate.

References