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.

The concept of Locally Recoverable Codes (LRC) has been studied by various researchers in the field of coding theory. It is challenging to attribute the introduction of LRC to a specific individual, as the development of coding theory and related concepts is often the result of collaborative efforts and contributions from multiple researchers over time.

Definition

Definition 1.1 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\}\}}$ 

Definition 1.2 An ${\displaystyle [n,k,d,r]_{q}}$  locally recovorable 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}$ .

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

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