Locally Recoverable Codes

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

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

Definition

Let

C

be a

[n, k, d]_{q}

linear code. For

i \in {1, \dots, n}

, let us denote by

r_{i}

the minimum number of other coordinates we have to look at to recover an erasure in coordinate

i

. The number

r_{i}

is said to be the locality of the

$i$

-th coordinate of the code. The locality of the code is defined as

r = max {r_{i} | i \in {1, \dots, n}}

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

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

Optimal Locally Recoverable Codes

Theorem^[7] Let

n = (r + 1) s

and let

C

be an

[n, k, d]_{q}

-locally recoverable code having

s

disjoint locality sets of size

r + 1

. Then

d \leq n - k - ⌈ \frac{k}{r} ⌉ + 2

An

[n, k, d, r]_{q}

-LRC

C

is said to be optimal if the minimum distance of

C

satisfies

d = n - k - ⌈ \frac{k}{r} ⌉ + 2

Tamo--Barg Codes

Let $f$ ∈ $𝔽_{q} [x]$ be a polynomial and let $ℓ$ be a positive integer. Then $f$ is said to be ( $r$ , $ℓ$ )-good if

•

f

has degree

r + 1

,

• there exist

A_{1}

, . . .,

A_{ℓ}

distinct subsets of

𝔽_{q}

such that

– for any

i \in {1, \dots, ℓ}

,

f

(

A_{i}

) = {

t_{i}

} for some

t_{i}

∈

𝔽_{q}

, i.e. f is constant on

A_{i}

,

– #

A_{i}

=

r + 1

,

–

A_{i}

∩

A_{j}

= ∅ for any

i

≠

j

.

We say that { $A_{1}, \dots, A_{ℓ}$ } is a splitting covering for $f$ ^[8].

Tamo--Barg Construction

The Tamo--Barg construction utilizes good polynomials.^[9]

• Suppose that a

(r, ℓ)

-good polynomial

f (x)

over

𝔽_{q}

is given with splitting covering

i \in {1, \dots, ℓ}

.

• Let

s

≤

ℓ - 1

be a positive integer.

• Consider the following

𝔽_{q}

-vector space of polynomials

V = {\sum_{i = 0}^{s} g_{i} (x) f (x)^{i} : deg (g_{i} (x)) \leq deg (f (x)) - 2}

• Let

T

=

⋃_{i = 1}^{ℓ} A_{i}

• The code

{e v_{T} (g) : g \in V}

is an

((r + 1) ℓ, (s + 1) r, d, r)

optimal locally recoverable code, where

e v_{T}

denotes evaluation of g at all points in the set

T

.

Parameters of Tamo--Barg Codes

• 'Length. The length is the number of evaluation points. Because the sets

A_{i}

are disjoint for

i \in {1, \dots, ℓ}

, the length of the code is

| T | = (r + 1) ℓ

.

• 'Dimension. The dimension of the code is

(s + 1) r

, for

s

≤

ℓ - 1

, as each

g_{i}

has degree at most

deg (f (x)) - 2

, covering a vector space of dimension

deg (f (x)) - 1 = r

, and by the construction of

V

, there are

s + 1

distinct

g_{i}

, each of which covering distinct vector spaces of dimension

r

.

• 'Distance. The distance is given by the fact that

V \subseteq 𝔽_{q} [x]_{\leq k}

, where

k = r + 1 - 2 + s (r + 1)

, and the obtained code is the Reed-Solomon code of degree at most

k

, so the distance equals

(r + 1) ℓ - ((r + 1) - 2 + s (r + 1))

.

• 'Locality. After the erasure of the single component, the evaluation at

a_{i} \in A_{i}

, where

| A_{i} | = r + 1

, is unknown, but the evaluations for all other

a \in A_{i}

are known, so at most

r

evaluations are needed to uniquely determine the erased component, which gives us the locality of

r

.

Now,

g

restricted to

A_{1}

can be described by a polynomial

h

of degree at most

deg (f (x)) - 2 = r + 1 - 2 = r - 1

thanks to the form of the elements in

V

(i.e. thanks to the fact that

f

is constant on

A_{1}

, and the

g_{i}

's have degree at most

deg (f (x)) - 2

). On the other hand

| A_{1} ∖ {a_{1}} | = r

, and

r

evaluations uniquely determine a polynomial of degree

r - 1

. Therefore

h

can be constructed and evaluated at

a_{1}

to recover

g (a_{1})

.