# Good Locally Repairable Codes via Propagation Rules

Shu Liu  Natl Key Lab Sci and Technol Commun, University of Electronic Science
and Technology of China, Chengdu, China<EMAIL_ADDRESS>,  Liming Ma
School of Mathematical Sciences, University of Science and Technology of
China, Hefei 230026, China<EMAIL_ADDRESS>,  Tingyi Wu  Theory Lab,
Central Research Institute, 2012 Labs, Huawei Technology Co. Ltd.
<EMAIL_ADDRESS>and  Chaoping Xing  School of Electronics, Information
and Electric Engineering, Shanghai Jiao Tong University, China 200240
<EMAIL_ADDRESS>
###### Abstract.

In classical coding theory, it is common to construct new codes via
propagation rules. There are various propagation rules to construct classical
block codes. However, propagation rules have not been extensively explored for
constructions of locally repairable codes. In this paper, we introduce a few
propagation rules to construct good locally repairable codes. To our surprise,
these simple propagation rules produce a few interesting results. Firstly, by
concatenating a locally repairable code as an inner code with a classical
block code as an outer code, we obtain quite a few dimension-optimal binary
locally repairable codes. Secondly, from this concatenation, we explicitly
build a family of locally repairable codes that exceeds the Zyablov-type
bound. Thirdly, by a lengthening propagation rule that adds some rows and
columns from a parity-check matrix of a given linear code, we are able to
produce a family of dimension-optimal binary locally repairable codes from the
extended Hamming codes, and to convert a classical maximum distance separable
(MDS) code into a Singleton-optimal locally repairable code. Furthermore, via
the lengthening propagation rule, we greatly simplify the construction of a
family of locally repairable codes in [25, Theorem 5] that breaks the
asymptotic Gilbert-Varshamov bound. In addition, we make use of three other
propagation rules to produce more dimension-optimal binary locally repairable
codes. Finally, one of phenomena that we observe in this paper is that some
trivial propagation rules in classical block codes do not hold anymore for
locally repairable codes.

##  1\. Introduction

Since the first work on locally repairable codes in [13, 15], construction of
good locally repairable codes has been a central problem in the study of
locally repairable codes [1, 2, 5, 9, 11, 12, 14, 17, 20, 24, 28, 31, 32, 34,
35, 36]. A locally repairable code is just a block code with an additional
parameter called locality. It was shown in [11] that the minimum distance
$d(C)$ of an $[n,k,d]$-linear code $C$ with locality $r$ is upper bounded by

(1) $d(C)\leq n-k-\left\lceil\frac{k}{r}\right\rceil+2.$

The bound (1) is called the Singleton-type bound for locally repairable codes,
and hence any code achieving this bound is called an optimal locally
repairable code or a Singleton-optimal locally repairable code.

###  1.1. Known Results

The construction of optimal locally repairable codes is of both theoretical
interest and practical importance. A class of codes constructed earlier and
known as pyramid codes [15] are shown to be optimal locally repairable codes.
In [32], Silberstein et al. proposed a two-level construction based on the
Gabidulin codes combined with a single parity-check $(r+1,r)$ code. Another
construction [36] used two layers of MDS codes, a Reed-Solomon code and a
special $(r+1,r)$ MDS code. A common shortcoming of these constructions is
that the size of the code alphabet is an exponential function of the code
length, and complicating the implementation. There was an earlier construction
of optimal locally repairable codes given in [29] with alphabet size
comparable to code length. However, the rate of the code is very close to $1$.

A remarkable construction of optimal locally repairable codes via subcodes of
Reed-Solomon codes was given by Tamo and Barg in [34]. There are some
constraints on choice of locality due to the existence of good polynomials,
and the length is upper bounded by the code alphabet size $q$. This
construction was generalized via the automorphism group of a rational function
field in [19] and it turns out that there are more flexibility on locality and
the code length can be $q+1$. Based on the classical MDS conjecture, one
should wonder if $q$-ary optimal locally repairable codes can have length
bigger than $q+1$. Surprisingly, several optimal locally repairable codes with
length around $q^{2}$ are constructed from algebraic surfaces in [2]. By
making use of automorphism groups of elliptic curves, optimal locally
repairable codes with length up to $q+2\sqrt{q}$ can be constructed [20, 25].
Algebraic surfaces are employed to construct two families of optimal locally
repairable codes [30]. In these constructions, there are no restriction on the
minimum distance of optimal locally repairable codes.

As for optimal locally repairable codes with small distances, the length of
optimal locally repairable codes could be much larger than the alphabet size
$q$. Arbitrary long optimal locally repairable codes can be constructed by
cyclic codes for distance $d=3,4$ [24], and the length of an optimal $q$-ary
locally repairable code is at most roughly $O(dq^{3})$ for distance $d\geq 5$
[12]. Jin provided an explicit construction of $q$-ary optimal locally
repairable codes with length $O(q^{2})$ via binary constant-weight codes for
distance $5$ and $6$ [17]. From extreme graph theory, there exists explicit
construction of optimal locally repairable codes with super-linear length for
distance $d\geq 7$ [38]. Over the past few years, locally repairable codes
have been generalized to correct multiple erasure errors [5, 6, 7, 8] and
correct erasures from multiple recovery sets [4, 18, 31].

The Singleton-type bound of locally repairable codes is not always tight. In
[3], Cadambe and Mazumdar derived a field-dependent bound, known as the C-M
bound,

$k\leq\min_{t\in\mathbb{Z}_{+}}\\{tr+k_{opt}^{(q)}(n-(r+1)t,d)\\},$

where $k_{opt}^{(q)}(n,d)$ is the largest possible dimension of an $[n,k,d]$
linear code over $\mathbb{F}_{q}$. Unfortunately, the value
$k_{opt}^{(q)}(n,d)$ is not completely determined. For binary locally
repairable codes, several explicit upper bounds on the dimension of linear
locally repairable codes were given via a sphere-packing approach in [37]. Any
locally repairable code achieving one of these bounds is called dimension-
optimal, and many dimensional-optimal locally repairable codes have been
constructed in [16, 23]. In particular, some propagation rules has been
employed in [3, 37]. The construction of locally repairable codes via
concatenation was introduced by using a simple parity-check code as inner code
[3], and a shortening technique to construct locally repairable codes was
given in [37, Lemma 10].

###  1.2. Our Contributions and Techniques

Among these constructions, propagation rules have not been extensively
explored although various propagation rules have been discovered in classical
coding theory. The current paper makes a step towards constructing locally
repairable codes by exploring various propagation rules. This paper makes the
following six-fold contributions:

  * (i)

give two main propagation rules together with three other propagation rules
for constructions of locally repairable codes. In addition, we show that some
trivial propagation rules in classical block codes do not hold anymore for
locally repairable codes;

  * (ii)

construct many dimension-optimal binary locally repairable codes based on the
first main propagation rule, i.e., concatenating a locally repairable code as
an inner code with a classical block code as an outer code. More dimension-
optimal binary locally repairable codes are produced via minor propagation
rules based on the aforementioned dimension-optimal locally repairable codes;

  * (iii)

by concatenating locally repairable codes with algebraic geometry codes via
the first main propagation rule, we are able to break the Zyablov-type bound
for locally repairable codes;

  * (iv)

produce a family of dimension-optimal binary locally repairable codes from
extended Hamming codes based on the second main propagation rule, i.e., add
certain rows and columns to a parity-check matrix of a given linear code.

  * (v)

convert Reed-Solomon codes into Singleton-optimal locally repairable codes via
the second main propagation rule;

  * (vi)

greatly simplify the construction of a family of locally repairable codes
given in [25, Theorem 5] that breaks the asymptotic Gilbert-Varshamov bound.

###  1.3. Organization

This paper is organized as follows. In Section 2, we present some
preliminaries including linear codes, algebraic geometry codes and locally
repairable codes. In Section 3, we introduce the first main propagation rule
together with three other propagation rules, and then present many dimension-
optimal locally repairable codes. In addition, we show that some trivial
propagation rules for classical block codes do not hold anymore for locally
repairable codes. Furthermore, we explicitly construct a family of locally
repairable codes that exceed the Zyablov-type bound. In Section 4, we produce
a family of dimension-optimal binary locally repairable codes from extended
Hamming codes via the second main propagation rule, and convert a classical
MDS code into a Singleton-optimal locally repairable code. Finally, we
simplify a construction of a family of locally repairable codes which can
break the asymptotic Gilbert-Varshamov bound.

##  2\. Preliminaries

In this section, we present some preliminaries on the theory of linear codes,
algebraic geometry codes and locally repairable codes.

###  2.1. Linear codes

In this subsection, we briefly discuss linear codes. The reader may refer to
[22, 27] for more details. Let $q$ be a prime power and $\mathbb{F}_{q}$ be
the finite field with $q$ elements. Let $\mathbb{F}_{q}^{n}$ be the vector
space of dimension $n$ over $\mathbb{F}_{q}$. A linear code $\mathcal{C}$ of
length $n$ over $\mathbb{F}_{q}$ is an $\mathbb{F}_{q}$-subspace of
$\mathbb{F}_{q}^{n}$. The dimension of $\mathcal{C}$ is defined to be the
dimension of $\mathcal{C}$ as a vector space over $\mathbb{F}_{q}$. Any
element in $\mathcal{C}$ is called a codeword. The support of a codeword ${\bf
u}=(u_{1},\cdots,u_{n})\in C$ is defined by $\text{supp}({\bf
u})=\\{i\in[n]:u_{i}\neq 0\\},$ where $[n]=\\{1,2,\cdots,n\\}.$ The Hamming
weight $\text{wt}(\bf u)$ of ${\bf u}$ is defined to be the size of
$\text{supp}({\bf u}).$ If $\mathcal{C}\neq\\{0\\}$, then the minimum distance
of $\mathcal{C}$ is defined to be the smallest Hamming weight of nonzero
codewords in $\mathcal{C}$.

A $q$-ary linear code with length $n$, dimension $k$ and minimum distance $d$
is denoted as an $[n,k,d]_{q}$-linear code. From the Singleton bound [22,
Theorem 5.4.1], we have the following inequality

(2) $d\leq n-k+1.$

A linear code with minimum distance achieving this Singleton bound (2) is
called an maximum distance separable code (MDS code for short). The dual
$\mathcal{C}^{\perp}$ of any code $\mathcal{C}$ is the orthogonal complement
of $\mathcal{C}$ in $\mathbb{F}_{q}^{n}$, i.e., $\mathcal{C}^{\perp}:=\\{{\bf
x}\in\mathbb{F}_{q}^{n}:\langle{\bf x},{\bf c}\rangle=0\text{ for any }{\bf
c}\in\mathcal{C}\\},$ where $\langle\cdot,\cdot\rangle$ is the canonical
Euclidean inner product in $\mathbb{F}_{q}^{n}$.

###  2.2. Algebraic geometry codes

Let $F/\mathbb{F}_{q}$ be a function field with genus $g$ over the full
constant field $\mathbb{F}_{q}$. Let $\mathbb{P}_{F}$ denote the set of places
of $F$. Any place of $F$ with degree one is called rational. For a divisor $G$
of function field $F/\mathbb{F}_{q}$, we define the Riemann-Roch space by
$\mathcal{L}(G):=\\{u\in F^{*}:\;(u)+G\geqslant 0\\}\cup\\{0\\}.$ From
Riemann’s theorem, $\mathcal{L}(G)$ is a finite-dimensional vector space over
$\mathbb{F}_{q}$ and its dimension $\ell(G)$ is lower bounded by
$\ell(G)\geqslant\deg(G)-g+1$. Moreover, the equality holds true if
$\deg(G)\geqslant 2g-1$ from [33, Theorem 1.5.17].

Let $\mathcal{P}=\\{P_{1},\dots,P_{n}\\}$ be a set of distinct rational places
of $F$. For a special divisor $G$ of $F$ with $0<\deg(G)<n$ and ${\rm
supp}(G)\cap\mathcal{P}=\emptyset$, the algebraic geometry code associated
with $\mathcal{P}$ and $G$ is defined to be
$\mathcal{C}(\mathcal{P},G):=\\{(f(P_{1}),f(P_{2}),\dots,f(P_{n})):\;f\in\mathcal{L}(G)\\}.$
Then $\mathcal{C}(\mathcal{P},G)$ is an $[n,k,d]_{q}$-linear code with
dimension $k=\ell(G)$ and minimum distance $d\geqslant n-\deg(G)$ from [33,
Theorem 2.2.2].

Let $N_{q}(g)$ be the maximum number of rational places of function fields
over $\mathbb{F}_{q}$ with genus $g$. The real number $A(q)$ defined by
$A(q):=\limsup_{g\rightarrow\infty}\frac{N_{q}(g)}{g}$ is called the Ihara’s
constant. If $q$ is a square, then $A(q)=\sqrt{q}-1$ [10]. The famous Tsfaman-
Vlăduţ-Zink bound (TVZ bound for short) can be found from [33, Theorem 8.4.7].

######  Proposition 2.1.

Let $q=\ell^{2}$ be a square of a prime power. Then for all $\delta$ with
$0\leqslant\delta\leqslant 1-(\ell-1)^{-1}$, there exists a family of
algebraic geometry codes such that its information rate $R$ and relative
minimum distance $\delta$ satisfy $R\geqslant 1-\frac{1}{\sqrt{q}-1}-\delta.$

###  2.3. Locally repairable codes

Roughly speaking, a block code is said with locality $r$ if every coordinate
of any given codeword can be recovered by accessing at most $r$ other
coordinates of this codeword. A formal definition of a locally repairable code
with locality $r$ can be given as follows.

######  Definition 1.

A $q$-ary code of length $n$ is called a locally repairable code (LRC for
short) with locality $r$ if for any $i\in[n],$ there exists a subset
$R\subseteq[n]\setminus\\{i\\}$ of size $r$ such that for any ${\bf
c}=(c_{1},\cdots,c_{n})\in\mathcal{C},$ $c_{i}$ can be recovered by
$\\{c_{j}\\}_{j\in R},$ i.e., for any $i\in[n],$ there exists a subset
$R\subseteq[n]\setminus\\{i\\}$ of size $r$ such that for any ${\bf
u,v}\in\mathcal{C},{\bf u}_{R\cup\\{i\\}}={\bf v}_{R\cup\\{i\\}}$ if and only
if ${\bf u}_{R}={\bf v}_{R}.$ The set $R\cup\\{i\\}$ is called a recovery set
of $i.$ Note that we include $i$ in the recovery set for convenience.

In this paper, we always consider linear locally repairable codes. Thus, a
linear locally repairable code over $\mathbb{F}_{q}$ of length $n$, dimension
$k$, minimum distance $d$ and locality $r$ is denoted to be an
$[n,k,d;r]_{q}$-locally repairable code. For such a $q$-ary
$[n,k,d;r]$-locally repairable code, the minimum distance of $\mathcal{C}$ is
upper bounded by

(3) $d\leqslant n-k-\left\lceil\frac{k}{r}\right\rceil+2.$

A code achieving this bound (3) is usually called an optimal locally
repairable code. However, we refer it as a Singleton-optimal locally
repairable code in this paper.

Recovery sets of a linear locally repairable code can be characterized by its
dual code from [12, Lemma 5]. The precise result is given as below.

######  Lemma 2.2.

A subset $R\subseteq[n]$ containing $i$ is a recovery set at $i$ for a $q$-ary
linear code of length $n$ if and only if there exists a codeword ${\bf
c}\in\mathcal{C}^{\bot}$ such that $i\in{\rm supp}({\bf c})\subseteq R.$

For a linear code ${\mathcal{C}}$ and $r\geqslant 1$, we define the set
$\mathfrak{R}_{\mathcal{C}}(r):=\\{{\rm supp}({\bf c}):\;{\bf
c}\in{\mathcal{C}}^{\perp},\;|{\rm supp}({\bf c})|\leqslant r+1\\}.$ The
following result is a straightforward corollary of Lemma 2.2.

######  Corollary 2.3.

A linear code ${\mathcal{C}}$ has locality $r$ if and only if
$[n]=\cup_{I\in\mathfrak{R}_{\mathcal{C}}(r)}I$.

In this paper, we will also study the asymptotic behavior of locally
repairable codes. Let the locality $r$ and alphabet size $q$ be fixed, and let
the dimension and minimum distance be proportional to the length $n$. Let
$R_{q}(r,\delta)$ denote the asymptotic bound on the rate of $q$-ary locally
repairable codes with locality $r$ and relative minimum distance $\delta$,
i.e.,

$R_{q}(r,\delta)=\limsup_{n\rightarrow\infty}\frac{\log_{q}M_{q}(n,\lfloor\delta
n\rfloor,r)}{n},$

where $M_{q}(n,d,r)$ is the maximum size of locally repairable codes of length
$n$, minimum distance $d$ and locality $r$.

For $0\leqslant\delta\leqslant 1-q^{-1}$, the asymptotic Gilbert-Varshamov
bound of locally repairable codes is given in [35] by

$R_{q}(r,\delta)\geqslant 1-\min_{0<s\leqslant
1}\Big{\\{}\frac{1}{r+1}\log_{q}\Big{(}[1+(q-1)s]^{r+1}+(q-1)(1-s)^{r+1}\Big{)}-\delta\log_{q}s\Big{\\}}.$

Barg et al. [1] gave a construction of asymptotically good $q$-ary locally
repairable codes with locality $r$ whose rate $R$ and relative distance
$\delta$ satisfy

(4) $R\geqslant\frac{r}{r+1}\Big{(}1-\delta-\frac{3}{\sqrt{q}+1}\Big{)},\quad
r=\sqrt{q}-1,$

and

(5)
$R\geqslant\frac{r}{r+1}\Big{(}1-\delta-\frac{\sqrt{q}+r}{q-1}\Big{)},\quad(r+1)|(\sqrt{q}+1).$

Furthermore, it was shown in [1] that for some values $r$ and $q$, the bound
(5) exceeds the asymptotic Gilbert-Varshamov bound for locally repairable
codes. Li et al. [21] generalized the idea given in [1] by considering more
subgroups of automorphism groups of function fields in the Garcia-Stichtenoth
tower [10]. This construction allows more flexibility of locality. In
particular, if $r+1=up^{v}$ with $u|\gcd(p^{v}-1,\sqrt{q}-1)$, then there
exists a family of explicit $q$-ary linear locally repairable codes with
locality $r$ whose rate $R$ and relative distance $\delta$ satisfy

(6)
$R\geqslant\frac{r}{1+r}\Big{(}1-\delta-\frac{\sqrt{q}+r-1}{q-\sqrt{q}}\Big{)}.$

In order to overcome the restrictions on alphabet size $q$ and locality $r$,
the authors [25] provided an explicit construction via parity-check matrices
whose columns are formed by coefficients of local expansions of function
fields in the Garcia-Stichtenoth tower. In particular, for any fixed $q$ and
$r$, it has been proved in [25] that

(7) $R\geqslant\frac{r}{r+1}-\frac{1}{A(q)}\times\frac{r}{r+1}-\delta.$

##  3\. Locally Repairable Codes via Concatenations

In this section, we present the first main propagation rule together with
three other propagation rules and construct many dimension-optimal locally
repairable codes. In addition, we show that some trivial propagation rules for
classical block codes do not hold anymore for locally repairable codes.

###  3.1. Concatenations and dimension-optimal locally repairable codes

Let us start with the first main propagation rule by concatenating a locally
repairable code as an inner code with a classical block code as an outer code.

######  Theorem 3.1.

Let the inner code $\mathcal{C}_{in}$ be a $q$-ary
$[n_{1},k_{1},d_{1};r]$-locally repairable code and let the outer code
$\mathcal{C}_{out}$ be a $q^{k_{1}}$-ary $[n_{2},k_{2},d_{2}]$-linear code,
then one can concatenate $\mathcal{C}_{in}$ with $\mathcal{C}_{out}$ to obtain
an $[n_{1}n_{2},k_{1}k_{2},\geqslant d_{1}d_{2};r]_{q}$-locally repairable
code $\mathcal{C}_{conc}$.

###### Proof.

Fix an $\mathbb{F}_{q}$-vector space isomorphism $\varphi$ between
$\mathbb{F}_{q^{k_{1}}}$ and $\mathcal{C}_{in}.$ Define $\mathcal{C}_{conc}$
by

$\mathcal{C}_{conc}=\\{(\varphi(c_{1}),\varphi(c_{2}),\dots,\varphi(c_{n_{2}})):\;(c_{1},c_{2},\dots,c_{n_{2}})\in\mathcal{C}_{out}\\}.$

Then $\mathcal{C}_{conc}$ is an $[n_{1}n_{2},k_{1}k_{2},\geqslant
d_{1}d_{2}]_{q}$-linear code from [22, Theorem 6.3.1]. Every position of a
codeword of $\mathcal{C}_{conc}$ can be determined by $r$ other positions due
to the fact that the inner code $\mathcal{C}_{in}$ has locality $r$. Hence,
$\mathcal{C}_{conc}$ has locality $r$. ∎

Although the concatenation technique is simple, it is quite powerful. By
concatenating locally repairable codes with classical block codes, we can
construct many good binary linear locally repairable codes that achieve the
upper bound given in [37, Theorem 6].

######  Lemma 3.2.

For any binary $[n,k,d;r]$-locally repairable code with locality $r$ such that
$d\geqslant 5$ and $2\leqslant r\leqslant\frac{n}{2}-2,$ it follows that

(8)
$k\leqslant\left\lfloor\frac{rn}{r+1}-\min\left\\{\log_{2}\left(1+\frac{rn}{2}\right),\frac{rn}{(r+1)(r+2)}\right\\}\right\rfloor.$

A binary linear locally repairable code is called dimension-optimal if its
dimension achieves the bound (8) in Lemma 3.2. Based on our concatenation
given in Theorem 3.1, we can provide many dimension-optimal binary locally
repairable codes.

######  Example 3.3.

Let $\mathcal{C}_{in}$ be a single parity-check $[5,4,2]_{2}$ code. Let
$\mathcal{C}_{out}$ be a $[17,15,3]_{2^{4}}$ MDS code obtained from rational
algebraic geometry codes. By Theorem 3.1, we obtain an
$[85,60,6;4]_{2}$-locally repairable code. On the other hand, the bound (8) in
Lemma 3.2 shows that every $[85,k,6;4]_{2}$-locally repairable code must obey
$k\leqslant 60.582$, i.e., $k\leqslant 60$. This implies that an
$[85,60,6;4]_{2}$-locally repairable code is dimension-optimal. Similarly,
more dimension-optimal binary locally repairable codes via concatenations can
be listed in the following table.

Table I

Dimension-optimal Locally Repairable Codes via Concatenations

Inner code | Outer code | Dimension-optimal binary LRCs
---|---|---
$[5,4,2;4]_{2}$ | $[17,15,3]_{16}$ | $[85,60,6;4]_{2}$
$[5,4,2;4]_{2}$ | $[16,14,3]_{16}$ | $[80,56,6;4]_{2}$
$[5,4,2;4]_{2}$ | $[15,13,3]_{16}$ | $[75,52,6;4]_{2}$
$[5,4,2;4]_{2}$ | $[14,12,3]_{16}$ | $[70,48,6;4]_{2}$
$[5,4,2;4]_{2}$ | $[13,11,3]_{16}$ | $[65,44,6;4]_{2}$
$[4,3,2;3]_{2}$ | $[9,7,3]_{8}$ | $[36,21,6;3]_{2}$

Some classical propagation rules given in [22, Theorem 6.1.1] can be
generalized to construct new locally repairable codes from old ones.

######  Lemma 3.4.

If $\mathcal{C}$ is an $[n,k,d;r]_{q}$-locally repairable code, then

  * (i)

there exists an $[n+1,k,d;r]_{q}$-locally repairable code;

  * (ii)

there exists an $[n-1,\geqslant k-1,d;r]_{q}$-locally repairable code;

  * (iii)

there exists an $[n-t,\geqslant k-t+s,\geqslant d-s;r]_{q}$-locally repairable
code for any $0\leqslant s\leqslant t$, provided that $\mathcal{C}$ has
disjoint recovery sets and one of the recovery sets has size $t$.

###### Proof.

(i) By adding $0$ to the $(n+1)$-th position of every codeword of
$\mathcal{C}$, one gets an $[n+1,k,d]_{q}$-linear code. For the $(n+1)$-th
position, we have a recovery set $\\{n+1\\}$. Thus, the new code has locality
$r$ as well.

(ii) Let $H$ be a parity-check matrix of $\mathcal{C}$. From [22, Theorem
4.5.6], there are $d$ columns of $H$ which are linearly dependent. Without
loss of generality, assume that the last column of $H$ is not in these $d$
columns. We delete the last column of $H$ to form a $(n-k)\times(n-1)$ matrix
$H_{1}$. Let $\mathcal{C}_{1}$ be the code with $H_{1}$ as its parity-check
matrix. It is clear that $\mathcal{C}_{1}$ is an $[n-1,\geqslant
k-1,d]_{q}$-linear code. To obtain the locality, for each $i\in[n-1]$, there
exists a codeword ${\bf u}\in\mathcal{C}^{\perp}$ such that $i\in{\rm
supp}({\bf u})$ and $|{\rm supp}({\bf u})|\leqslant r+1$. Let ${\bf u}_{1}$ be
the vector obtained from ${\bf u}$ by deleting the last position. Then ${\bf
u}_{1}\in\mathcal{C}_{1}^{\perp}$, $i\in{\rm supp}({\bf u}_{1})$ and $|{\rm
supp}({\bf u}_{1})|\leqslant r+1$. This implies that the position $i$ has a
recovery set of size at most $r+1$. Hence, $\mathcal{C}_{1}$ is an
$[n-1,\geqslant k-1,d;r]_{q}$-locally repairable code.

(iii) Without loss of generality, we may assume that
$\\{n-t+1,n-t+2,\dots,n\\}$ is a recovery set of size $t$. Let $H$ be a
parity-check matrix of $\mathcal{C}$. We delete the last $t-s$ columns of $H$
to form an $(n-k)\times(n-t+s)$ matrix $H_{2}$. Let $\mathcal{C}_{2}$ be the
code with $H_{2}$ as its parity-check matrix. It is clear that
$\mathcal{C}_{2}$ is an $[n-t+s,\geqslant k-t+s,\geqslant d]_{q}$-linear code.
As in (ii), we can show that $\mathcal{C}_{2}$ has locality $r$ as well.
Furthermore, $\\{n-t+1,n-t+2,\cdots,n-t+s\\}$ is a recovery set that is
disjoint with other recovery sets. Now we delete the last $s$ positions of
$\mathcal{C}_{2}$ to obtain $\mathcal{C}_{3}$. It is easy to see that
$\mathcal{C}_{3}$ is an $[n-t,\geqslant k-t+s,\geqslant d-s]_{q}$-linear code.
As a whole recovery set of $\mathcal{C}_{2}$ is deleted, $\mathcal{C}_{3}$ has
disjoint recovery sets with each size being at most $r+1$, i.e.,
$\mathcal{C}_{3}$ has locality $r$. ∎

######  Remark 3.5.

For classical block codes, we have the following propagation rules: (i) an
$[n,k,d]_{q}$-linear code gives an $[n-1,k,d-1]_{q}$-linear code; (ii) an
$[n,k,d]_{q}$-linear code gives an $[n,k,d-1]_{q}$-linear code. However, these
two propagation rules does not hold anymore. Namely, (i) an
$[n,k,d;r]_{q}$-locally repairable code does not always produce an
$[n-1,k,d-1;r]_{q}$-locally repairable code; (ii) an $[n,k,d;r]_{q}$-locally
repairable code does not always produce an $[n,k,d-1;r]_{q}$-locally
repairable code. To see this, let us give two counter-examples.

Counter-example 1: By Table I, we have a binary $[85,60,6;4]$-locally
repairable code. Suppose we had a binary $[85-1,60,6-1;4]$-locally repairable
code. Then by Lemma 3.2, any $[84,k,5;4]_{2}$-locally repairable code must
satisfy $k\leqslant 59.8$. This is a contradiction.

Counter-example 2: Consider the binary $[5,4,2;4]$-locally repairable code. As
we do not have a locally repairable code with minimum distance $1$, we have no
way to get a $[5,4,1;4]$-locally repairable code.

######  Example 3.6.

We can make use of the propagation rules given in Lemma 3.4 to construct more
dimension-optimal locally repairable codes from Table I.

Table II

Dimension-optimal Locally Repairable Codes via Propagation Rules in Lemma 3.4
Codes from Table I Dimension-optimal LRCs Propagation rules $[85,60,6;4]_{2}$
$[84,59,6;4]_{2}$ Lemma 3.4(ii) $[80,56,6;4]_{2}$ $[79,55,6;4]_{2}$ Lemma
3.4(ii) $[75,52,6;4]_{2}$ $[74,51,6;4]_{2}$ Lemma 3.4(ii) $[85,60,6;4]_{2}$
$[80,56,\geqslant 5;4]_{2}$ Lemma 3.4(iii) $[80,56,6;4]_{2}$ $[75,52,\geqslant
5;4]_{2}$ Lemma 3.4(iii) $[75,52,6;4]_{2}$ $[70,48,\geqslant 5;4]_{2}$ Lemma
3.4(iii) $[70,48,6;4]_{2}$ $[65,44,\geqslant 5;4]_{2}$ Lemma 3.4(iii)

###  3.2. Zyablov-type bound

In classical coding theory, in order to obtain an explicit asymptotic bound,
one can concatenate a family of linear codes achieving the Gilbert-Varshamov
bound as an inner code and a Reed-Solomon code as an outer code. The explicit
asymptotic bound obtained in this way is called the Zyablov bound. In this
subsection, we will explore the same technique to obtain the Zyablov-type
bound for locally repairable codes.

Consider the inner code $\mathcal{C}_{\rm in}$ to be an
$[n_{1},k_{1},d_{1};r]_{2}$-locally repairable code that achieves the Gilbert-
Varshamov bound, and the outer code $\mathcal{C}_{\rm out}$ to be an
$[n_{2},k_{2},d_{2}=n_{2}-k_{2}+1]_{q}$ Reed-Solomon code with $q=2^{k_{1}}$.
The concatenated code $\mathcal{C}_{\rm conc}$ is a binary
$[n_{1}n_{2},k_{1}k_{2},\geqslant d_{1}d_{2};r]$-locally repairable code from
Theorem 3.1. In particular, its rate satisfies

(9)
$R=\frac{k_{1}}{n_{1}}\times\frac{k_{2}}{n_{2}}=\left(1-h\left(r,\frac{d_{1}}{n_{1}}\right)+o(1)\right)\left(1-\frac{d_{2}}{n_{2}}\right),$

where

(10) $h(r,x):=\min_{0<s\leqslant
1}\Big{\\{}\frac{1}{r+1}\log_{q}\Big{(}[1+(q-1)s]^{r+1}+(q-1)(1-s)^{r+1}\Big{)}-x\log_{q}s\Big{\\}}.$

Put $\tau=\frac{d_{1}}{n_{1}}$ and $\delta=\frac{d_{1}d_{2}}{n_{1}n_{2}}$.
Then we have $\frac{d_{2}}{n_{2}}=\frac{\delta}{\tau}$. Substituting
$\frac{d_{1}}{n_{1}}=\tau$ and $\frac{d_{2}}{n_{2}}=\frac{\delta}{\tau}$ into
Equation (9), we obtain the following Zyablov-type bound for locally
repairable codes.

######  Theorem 3.7.

(Zyablov-type bound) For given integer $r\geqslant 1$ and real
$\delta\in(0,1)$, there exists a family of binary locally repairable codes of
rate $R$, relative minimum distance $\delta$ and locality $r$ satisfying
$\displaystyle R=\max_{\delta\leq\tau\leq 1}(1-\delta/\tau)(1-h(r,\tau)).$
Furthermore, this family of locally repairable codes can be constructed in
polynomial time.

######  Remark 1.

The Zyablov-type bound is worse than the Gilbert-Varshamov bound, since
$h(r,\tau)$ is a decreasing function in the variable $\tau$ and

$\max_{\delta\leq\tau\leq
1}(1-\delta/\tau)(1-h(r,\tau))\leqslant\max_{\delta\leq\tau\leq
1}(1-h(r,\tau))\leqslant 1-h(r,\delta).$

###  3.3. Breaking the Zyablov-type bound

In this subsection, we provide an explicit construction of asymptotically good
locally repairable codes exceeding the Zyablov-type bound via concatenated
codes.

######  Proposition 3.8.

Let $\mathcal{C}_{in}$ be the extended Hamming code $[8,4,4]_{2}$ with
locality $3$. Let $\\{\mathcal{C}_{out}^{(i)}\\}_{i=1}^{\infty}$ be a family
of algebraic geometry codes $[n_{i},k_{i},d_{i}]_{2^{4}}$ attaining the TVZ
bound given in Proposition 2.1. Then the concatenated codes are a family of
$[8n_{i},4k_{i},4d_{i};3]_{2}$-locally repairable codes with locality $3$ such
that its information rate $R$ and relative minimum distance $\delta$ satisfy
$R+\delta\geqslant 1/3.$

###### Proof.

From Theorem 3.1, the concatenated codes are a family of
$[8n_{i},4k_{i},4d_{i};3]_{2}$-locally repairable codes with locality $3$.
Thus, we have

$R+\delta=\lim_{i\rightarrow\infty}\frac{4k_{i}+4d_{i}}{8n_{i}}\geqslant\frac{1}{2}-\frac{1}{2\cdot
A(2^{4})}=\frac{1}{2}-\frac{1}{2\times 3}=\frac{1}{3}.$

∎

######  Remark 2.

Proposition 3.8 gives an explicit family of locally repairable codes with
locality $3$ that are beyond the Zyablov-type bound in some interval (see
Figure 1).

Figure 1. Beyond the Zyablov-type bound for locality $3$

######  Proposition 3.9.

Let $\mathcal{C}_{in}$ be the extended Golay code $[24,12,8]_{2}$ with
locality $7$. Let $\\{\mathcal{C}_{out}^{(i)}\\}_{i=1}^{\infty}$ be a family
of algebraic geometry codes $[n_{i},k_{i},d_{i}]$ over $\mathbb{F}_{2^{12}}$
attaining the TVZ bound given in Proposition 2.1. Then the concatenated codes
are a family of $[24n_{i},12k_{i},8d_{i}]_{2}$-linear locally repairable codes
with locality $7$ such that its information rate $R$ and relative minimum
distance $\delta$ satisfy $R\geqslant{31}/{63}-3\delta/2.$

######  Remark 3.

Proposition 3.9 gives an explicit family of locally repairable codes with
locality $7$ that are beyond the Zyablov-type bound in some interval (see
Figure 2).

Figure 2. Beyond the Zyablov-type bound for locality $7$

######  Proposition 3.10.

Let $m\leqslant q$ and $1\leqslant t\leqslant m-1$ be positive integers. Let
$\mathcal{C}_{in}$ be an $[m,m-t,t+1]_{q}$ Reed-Solomon code. Let
$\\{\mathcal{C}_{out}^{(i)}\\}$ be a family of algebraic geometry codes
$[n_{i},k_{i},d_{i}]$ over $\mathbb{F}_{q^{m-t}}$ attaining the TVZ bound
given in Proposition 2.1. Then the concatenated codes are locally repairable
codes with locality $m-t$ such that its information rate $R$ and relative
minimum distance $\delta$ satisfy

$R\geqslant\left(1-\frac{t}{m}\right)\left(1-\frac{1}{A(q^{m-t})}\right)-\frac{m-t}{t+1}\delta.$

Furthermore, such codes can be explicitly constructed.

###### Proof.

Let us consider the $[m,m-t,t+1]_{q}$ Reed-Solomon code given by

$\mathcal{A}:=\\{(f(\alpha_{1}),\dots,f(\alpha_{m})):\;f(x)\in\mathbb{F}_{q}[x]_{<m-t}\\},$

where $\alpha_{1},\dots,\alpha_{m}$ are pairwise distinct elements of
$\mathbb{F}_{q}$. From Lagrange interpolation formula, it is clear that the
$[m,m-t,t+1]_{q}$ Reed-Solomon code has locality $m-t$. From Theorem 3.1, the
concatenated codes have parameters $[mn_{i},(m-t)k_{i},(t+1)d_{i};m-t]_{q}$.
Hence, we have
$(t+1)(m-t)k_{i}+(m-t)(t+1)d_{i}\geqslant(m-t)(t+1)(k_{i}+d_{i}).$ This gives

$(t+1)R+(m-t)\delta\geqslant\left(1-\frac{t}{m}\right)(t+1)\left(1-\frac{1}{A(q^{m-t})}\right).$

The desired result follows.

∎

By taking $m=r+1$ and $t=1$ in Proposition 3.10, we obtain the following
result.

######  Corollary 3.11.

For any given real number $\delta\in(0,1)$, there exists an explicit family of
locally repairable codes with rate $R$, locality $r$ and relative minimum
distance $\delta$ satisfying

$R\geqslant\frac{r}{r+1}\left(1-\frac{1}{A(q^{r})}\right)-\frac{r}{2}\delta.$

In particular, if $q$ is a prime, then we can obtain the same asymptotic bound
of locally repairable codes over a prime finite field as given in [25, Theorem
10].

##  4\. Locally repairable codes via lengthening parity-check matrices

In this section, we try to construct good locally repairable codes based on
linear codes from a lengthening propagation rule. In particular, the technique
is to endow the locality by adding rows and columns in the parity-check matrix
of linear codes.

Let $\mathcal{C}_{0}$ be an $[n,k,d]$-linear code over $\mathbb{F}_{q}$ and
let $H_{0}\in\mathbb{F}_{q}^{(n-k)\times n}$ be its parity-check matrix. Let
$r$ be a positive integer. There exist integers $m$ and $s$ such that $n=mr+s$
with $1\leqslant s\leqslant r$. We divide the columns of $H_{0}$ into
$\lceil\frac{n}{r}\rceil$ blocks. Let ${\bf h}_{ij}$ be the columns of $H_{0}$
for $1\leqslant i\leqslant m,1\leqslant j\leqslant r$ and $i=m+1,1\leqslant
j\leqslant s$, i.e.,

$H_{0}=({\bf h}_{11},\cdots,{\bf h}_{1r},{\bf h}_{21},\cdots,{\bf
h}_{2r},\cdots,{\bf h}_{m1},\cdots,{\bf h}_{mr},{\bf h}_{m+1,1},\cdots,{\bf
h}_{m+1,s}).$

Now let us consider the matrix $H$ defined by

(11)
$H:=\left(\begin{array}[]{cccc|c|cccc|cccc}1&\cdots&1&1&\cdots&0&\cdots&0&0&0&\cdots&0&0\\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&\cdots&0&0&\cdots&1&\cdots&1&1&0&\cdots&0&0\\\
0&\cdots&0&0&\cdots&0&\cdots&0&0&1&\cdots&1&1\\\ {\bf h}_{11}&\cdots&{\bf
h}_{1r}&{\bf 0}&\cdots&{\bf h}_{m1}&\cdots&{\bf h}_{mr}&{\bf 0}&{\bf
h}_{m+1,1}&\cdots&{\bf h}_{m+1,s}&{\bf 0}\end{array}\right),$

where ${\bf 0}$ stands for the zero vector of dimension $n-k$.

######  Lemma 4.1.

Let $H$ be the matrix defined in Equation (11). Then any $d-1$ columns of $H$
are linearly independent.

###### Proof.

Let ${\bf c}_{i,j}$ denote the $j$-th column in the $i$-th block of the
parity-check matrix $H$. Choose arbitrary $d-1$ columns $\\{{\bf c}_{i,j}:i\in
I,j\in S_{i}\\}$ from $H$, where $S_{i}$ is a nonempty subset of
$\\{1,2,\cdots,r+1\\}$ with $\sum_{i\in I}|S_{i}|=d-1$.

Case 1: the last column in each block does not belong to $\\{{\bf
c}_{i,j}:i\in I,j\in S_{i}\\}$, i.e., $r+1\notin S_{i}$ for $1\leqslant
i\leqslant m$ and $s+1\notin S_{m+1}$. Since $H_{0}$ is a parity-check matrix
of an $[n,k,d]$-linear code, any $d-1$ columns of $H_{0}$ are linearly
independent. Hence, any $d-1$ columns $\\{{\bf c}_{i,j}:i\in I,j\in S_{i}\\}$
are linearly independent from linear algebra.

Case 2: the last column of some blocks are chosen. Without loss of generality,
assume that $r+1\in S_{i_{0}}$ for some $1\leqslant i_{0}\leqslant m$. In this
case, we can prove a stronger result. That is, arbitrary $d$ columns $\\{{\bf
c}_{i,j}:i\in I,j\in S_{i}\\}$ are linearly independent. Assume that there
exist $\lambda_{i,j}\in\mathbb{F}_{q}$ such that

$\sum_{i_{0}\neq i\in I}\sum_{j\in S_{i}}\lambda_{ij}{\bf c}_{ij}+\sum_{j\in
S_{i_{0}}}\lambda_{i_{0},j}{\bf c}_{i_{0},j}={\bf 0}.$

From the first $\lceil\frac{n}{r}\rceil$ rows of $H$, we have $\sum_{j\in
S_{i}}\lambda_{i,j}=0$ for $i\in I$. It follows that

(12) $\lambda_{i_{0},r+1}=-\sum_{j\in
S_{i_{0}}\setminus\\{r+1\\}}\lambda_{i_{0},j}.$

Then we have

$\sum_{i_{0}\neq i\in I}\sum_{j\in S_{i}}\lambda_{ij}{\bf c}_{ij}+\sum_{j\in
S_{i_{0}}\setminus\\{r+1\\}}\lambda_{i_{0},j}({\bf c}_{i_{0},j}-{\bf
c}_{i_{0},r+1})={\bf 0}.$

By focusing on the last $n-k$ rows of $H$, we have

$\sum_{i_{0}\neq i\in I}\sum_{j\in S_{i}}\lambda_{ij}{\bf h}_{ij}+\sum_{j\in
S_{i_{0}}\setminus\\{r+1\\}}\lambda_{i_{0},j}{\bf h}_{i_{0},j}={\bf 0}.$

Since any $d-1$ columns of $H_{0}$ are linearly independent, we have
$\lambda_{i,j}=0$ for $i_{0}\neq i\in I,j\in S_{i}$ and $i=i_{0},j\in
S_{i_{0}}\setminus\\{r+1\\}$. From Equation (12), we have
$\lambda_{i_{0},r+1}=0$. Hence, any $d$ columns are linearly independent in
this case. ∎

######  Proposition 4.2.

Let $\mathcal{C}$ be the code with $H$ given in Equation (11) as its parity-
check matrix. Then $\mathcal{C}$ is an $[n+\lceil\frac{n}{r}\rceil,k,\geqslant
d;r]$-locally repairable code.

###### Proof.

Since $H$ is an
$(n-k+\lceil\frac{n}{r}\rceil)\times(n+\lceil\frac{n}{r}\rceil)$ matrix and
the rows of $H$ are linearly independent from linear algebra, the dimension of
$\mathcal{C}$ is
$(n+\lceil\frac{n}{r}\rceil)-(n-k+\lceil\frac{n}{r}\rceil)=k$. From Lemma 4.1,
any $d-1$ columns of $H$ are linearly independent. Hence, the minimum distance
of $\mathcal{C}$ is at least $d$ from [22, Theorem 4.5.6]. Moreover, the
locality of $\mathcal{C}$ is $r$ from the parity-check matrix $H$ and
Corollary 2.3.

∎

###  4.1. Dimension-optimal locally repairable codes

In order to increase minimum distance of locally repairable codes constructed
in Proposition 4.2, we can employ the additional property of parity-check
matrices of extended Hamming codes. In this subsection, we propose a
construction of dimension-optimal locally repairable codes via lengthening
extended Hamming codes.

######  Theorem 4.3.

Let $\mathcal{C}_{0}$ be a binary $[2^{t},2^{t}-1-t,4]$-extended Hamming code
for $t\geqslant 3$. Let $H_{0}$ be a parity-check matrix of $\mathcal{C}_{0}$
and let $H$ be the matrix given in Equation (11). Then, for $r=2$ or $3$, the
code $\mathcal{C}$ with $H$ as a parity-check matrix is a binary
$[2^{t}+\lceil\frac{2^{t}}{r}\rceil,2^{t}-1-t,5;r]$-locally repairable code.
Furthermore, $\mathcal{C}$ achieves the upper bound (8) if $(r=2,t\geqslant
5)$ or $(r=3,t\geqslant 5)$, i.e., $\mathcal{C}$ is dimension-optimal in these
cases.

###### Proof.

Let us first show that $\mathcal{C}$ is a
$[2^{t}+\lceil\frac{2^{t}}{r}\rceil,2^{t}-1-t,5;r]$-locally repairable code.
By Proposition 4.2, it is sufficient to show that any four columns of $H$ are
linearly independent. Let us prove this only for the case where $r=3$.

Case 1: all four columns belong to the same block, say the first block. In
this case, we have to show that $(1,{\bf 0},{\bf 0})^{T}$, $(1,{\bf 0},{\bf
h}_{11})^{T}$, $(1,{\bf 0},{\bf h}_{12})^{T}$ and $(1,{\bf 0},{\bf
h}_{13})^{T}$ are linearly independent. Suppose that

(13) $\lambda_{0}(1,{\bf 0},{\bf 0})^{T}+\sum_{i=1}^{3}\lambda_{i}(1,{\bf
0},{\bf h}_{1i})^{T}={\bf 0}^{T}$

for some $\lambda_{i}\in\mathbb{F}_{2}$ with $0\leqslant i\leqslant 3$. Then
we have $\sum_{i=1}^{3}\lambda_{i}{\bf h}_{1i}={\bf 0}$. This forces that
$\lambda_{1}=\lambda_{2}=\lambda_{3}=0$ from [22, Theorem 4.5.6], since
$\mathcal{C}_{0}$ has minimum distance $4$. Thus, it follows from (13) that
$\lambda_{0}=0$.

Case 2: Other possibilities: (a) three columns belong to one block and one
column belongs to another block; (b) two columns belong to one block and other
two belong to another block; (c) two columns belong to one block and other two
columns belong to other two blocks, respectively; (d) four columns belong to
four distinct blocks. For these four possibilities, one can use a similar
argument to show that they are linearly independent. This proves the first
part.

Now if $r=2$ and $t\geqslant 5$, we want to show that

(14)
$k=2^{t}-1-t\geqslant\left\lfloor\frac{rn}{r+1}-\min\left\\{\log_{2}\left(1+\frac{rn}{2}\right),\frac{rn}{(r+1)(r+2)}\right\\}\right\rfloor$

with $r=2$ and $n=2^{t}+2^{t-1}$. To show (14), it will be sufficient to show
the following two inequalities

(15) $2^{t}-t>\frac{rn}{r+1}-\log_{2}\left(1+\frac{rn}{2}\right)$

and

(16) $2^{t}-t>\frac{rn}{r+1}-\frac{rn}{(r+1)(r+2)}.$

Substituting $r=2$ and $n=2^{t}+2^{t-1}$ into (15) and rewrite it into the
following form

(17) $\log_{2}\left(1+2^{t}+2^{t-1}\right)>t.$

It is clear that (17) holds and hence (15) holds.

Substituting $r=2$ and $n=2^{t}+2^{t-1}$ into (16) and rewrite it into the
following form

(18) $2^{t}-t>\frac{r}{r+2}\times n=2^{t-1}+2^{t-2}.$

The inequality (18) holds when $t\geqslant 5$ and hence (16) holds. This
completes the proof for the case where $r=2$ and $t\geqslant 5$.

Next assume that $r=3$ and $t\geqslant 5$. In this case we want to show that
the two inequalities (15) and (16) hold for $r=3$ and
$n=2^{t}+\lceil\frac{2^{t}}{3}\rceil$.

Substituting $r=3$ and $n=2^{t}+\left\lceil\frac{2^{t}}{3}\right\rceil$ into
(15) and rewrite it into the following form

(19)
$\log_{2}\left(1+\frac{3}{2}\left(2^{t}+\left\lceil\frac{2^{t}}{3}\right\rceil\right)\right)>t+\frac{3}{4}\times\left\lceil\frac{2^{t}}{3}\right\rceil-\frac{2^{t}}{4}.$

Note that we have
$1+\frac{3}{2}\left(2^{t}+\left\lceil\frac{2^{t}}{3}\right\rceil\right)>\frac{3}{2}\times
2^{t}>\sqrt{2}\times 2^{t}$. This gives

$\log_{2}\left(1+\frac{3}{2}\left(2^{t}+\left\lceil\frac{2^{t}}{3}\right\rceil\right)\right)>t+\frac{1}{2}=t+\frac{3}{4}\times\frac{2^{t}+2}{3}-\frac{2^{t}}{4}\geqslant
t+\frac{3}{4}\times\left\lceil\frac{2^{t}}{3}\right\rceil-\frac{2^{t}}{4},$

i.e., the inequality (19) holds and hence (15) holds.

Substituting $r=3$ and $n=2^{t}+\left\lceil\frac{2^{t}}{3}\right\rceil$ into
(16) and rewrite it into the following form

(20) $2^{t}-t>\frac{r}{r+2}\times
n=\frac{3}{5}\left(2^{t}+\left\lceil\frac{2^{t}}{3}\right\rceil\right)$

The inequality (20) holds when $t\geqslant 5$ and hence (16) holds. This
completes the proof for the case where $r=3$ and $t\geqslant 5$. ∎

Theorem 4.3 produces two families of dimension-optimal locally repairable
codes based on our second propagation rule and extended Hamming codes.
Combining with the propagation rules given in Lemma 3.4, we can obtain more
dimension-optimal locally repairable codes which are listed in the following
table.

Table III

Dimension-optimal LRCs via Lengthening and Propagation Rules in Lemma 3.4

$(r,t)$ | Known optimal LRCs | New optimal LRCs | Propagation rules
---|---|---|---
| given in Theorem 4.3 |  |
$(2,5)$ | $[48,26,5;2]_{2}$ | $[47,25,5;2]_{2}$ | Lemma 3.4(ii)
$(2,6)$ | $[96,57,5;2]_{2}$ | $[95,56,5;2]_{2}$ | Lemma 3.4(ii)
$(2,7)$ | $[192,120,5;2]_{2}$ | $[191,119,5;2]_{2}$ | Lemma 3.4(ii)
$(2,8)$ | $[384,247,5;2]_{2}$ | $[383,246,5;2]_{2}$ | Lemma 3.4(ii)
$(2,9)$ | $[768,502,5;2]_{2}$ | $[767,501,5;2]_{2}$ | Lemma 3.4(ii)
$(3,5)$ | $[43,26,5;3]_{2}$ | $[42,25,5;3]_{2}$ | Lemma 3.4(ii)
$(3,6)$ | $[86,57,5;3]_{2}$ | $[85,56,5;3]_{2}$ | Lemma 3.4(ii)
$(3,7)$ | $[171,120,5;3]_{2}$ | $[170,119,5;3]_{2}$ | Lemma 3.4(ii)
$(3,8)$ | $[342,247,5;3]_{2}$ | $[341,246,5;3]_{2}$ | Lemma 3.4(ii)
$(3,9)$ | $[683,502,5;3]_{2}$ | $[682,501,5;3]_{2}$ | Lemma 3.4(ii)
$(3,5)$ | $[43,26,5;3]_{2}$ | $[44,26,5;3]_{2}$ | Lemma 3.4(i)
$(3,7)$ | $[171,120,5;3]_{2}$ | $[172,120,5;3]_{2}$ | Lemma 3.4(i)
$(3,9)$ | $[683,502,5;3]_{2}$ | $[684,502,5;3]_{2}$ | Lemma 3.4(i)

###  4.2. Singleton-optimal locally repairable codes via lengthening RS codes

Again, in order to increase the minimum distance of locally repairable codes
given in Proposition 4.2, we can employ the additional property of parity-
check matrices with the Vandermonde structure as given in [17, 38]. In this
subsection, let us consider lengthening Reed-Solomon codes.

Let $r$ be a positive integer and let $n\leqslant q-1$ be a positive integer.
There exist integers $m$ and $s$ such that $n=mr+s$ with $1\leqslant
s\leqslant r$. Let $d\geqslant 2$ be a positive integer. Let $H_{0}$ be a
$(d-1)\times n$ matrix consisting of columns ${\bf
h}_{ij}=(\alpha_{ij},\alpha_{ij}^{2},\cdots,\alpha_{ij}^{d-1})^{T}$ with
pairwise distinct $\alpha_{ij}\in\mathbb{F}_{q}^{*}$ for $1\leqslant
i\leqslant m$, $1\leqslant j\leqslant r$ and $i=m+1,1\leqslant j\leqslant s$.
Any $d-1$ columns of $H_{0}$ are linearly independent, since the determinant
of Vandermonde matrix is nonzero. Let $H_{1}$ be a $d\times n$ matrix given as
follows:

$H_{1}=\left(\begin{array}[]{cccccccccc}1&\cdots&1&\cdots&1&\cdots&1&1&\cdots&1\\\
{\bf h}_{11}&\cdots&{\bf h}_{1r}&\cdots&{\bf h}_{m1}&\cdots&{\bf h}_{mr}&{\bf
h}_{m+1,1}&\cdots&{\bf h}_{m+1,s}\end{array}\right).$

It is easy to see that $H_{1}$ is a Vandermonde matrix which is a generator
matrix of some Reed-Solomon code. Let $\mathcal{C}_{1}$ be the code with
$H_{1}$ as its parity-check matrix. Then $\mathcal{C}_{1}$ is an $[n,n-d,d+1]$
MDS code. We split the first row of $H_{1}$ into $\lceil\frac{n}{r}\rceil$
rows and add a new column in each block of $H_{1}$ as follows:

(21)
$H=\left(\begin{array}[]{cccc|c|cccc|cccc}1&\cdots&1&1&\cdots&0&\cdots&0&0&0&\cdots&0&0\\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&\cdots&0&0&\cdots&1&\cdots&1&1&0&\cdots&0&0\\\
0&\cdots&0&0&\cdots&0&\cdots&0&0&1&\cdots&1&1\\\ {\bf h}_{11}&\cdots&{\bf
h}_{1r}&{\bf 0}&\cdots&{\bf h}_{m1}&\cdots&{\bf h}_{mr}&{\bf 0}&{\bf
h}_{m+1,1}&\cdots&{\bf h}_{m+1,s}&{\bf 0}\end{array}\right),$

where ${\bf 0}$ stands for the zero vector of dimension $d-1$.

######  Lemma 4.4.

Any $d$ columns of $H$ given in Equation (21) are linearly independent.

###### Proof.

Let ${\bf c}_{i,j}$ be the $j$-th column in the $i$-th block of the parity-
check matrix $H$. Choose any $d$ columns $\\{{\bf c}_{i,j}:i\in I,j\in
S_{i}\\}$ from $H$, where $S_{i}$ is a nonempty subset of
$\\{1,2,\cdots,r+1\\}$ with $\sum_{i\in I}|S_{i}|=d$.

Case 1: the last column in each block does not belong to $\\{{\bf
c}_{i,j}:i\in I,j\in S_{i}\\}$, i.e., $r+1\notin S_{i}$ for $1\leqslant
i\leqslant m$ and $s+1\notin S_{m+1}$. Assume that there exist
$\lambda_{i,j}\in\mathbb{F}_{q}$ such that $\sum_{i\in I}\sum_{j\in
S_{i}}\lambda_{ij}{\bf c}_{i,j}={\bf 0}.$ It follows that $\sum_{j\in
S_{i}}\lambda_{i,j}=0$ for all $i\in I$ from the parity-check matrix $H$,
which imply that $\sum_{i\in I}\sum_{j\in S_{i}}\lambda_{i,j}=0$. Thus, we
have the following system of linear equations

$\sum_{i\in I,j\in S_{i}}\alpha_{ij}^{t}\lambda_{i,j}=0\text{ for }0\leqslant
t\leqslant d-1.$

The coefficient matrix of the above system of linear equations is a
Vandermonde matrix in the variables $\\{\alpha_{i,j}:i\in I,j\in S_{i}\\}$.
Since $\alpha_{i,j}$ are pairwise distinct, the determinant of the coefficient
matrix is nonzero. Hence, such an system of linear equations has a unique
solution $\lambda_{i,j}=0$ for $i\in I$ and $j\in S_{i}$.

Case 2: the last column of some blocks are contained in $\\{{\bf
c}_{i,j}:1\leqslant i\leqslant m+1,j\in S_{i}\\}$. We have already proved that
any $d$ columns of $H$ are linearly independent for this case in Lemma 4.1. So
we omit the details here. ∎

######  Proposition 4.5.

Let $\mathcal{C}$ be the code with $H$ given in Equation (21) as its parity-
check matrix. Then $\mathcal{C}$ is an
$[n+\lceil\frac{n}{r}\rceil,n-d+1,\geqslant d+1;r]$-locally repairable code.

###### Proof.

The parity-check matrix $H$ is a
$(\lceil\frac{n}{r}\rceil+d-1)\times(n+\lceil\frac{n}{r}\rceil)$ matrix and
the rows of $H$ are linearly independent from linear algebra. Hence, the
dimension of $\mathcal{C}$ is $n-d+1$. From Lemma 4.4 and [22, Theorem 4.5.6],
the minimum distance of $\mathcal{C}$ is at least $d+1$. Finally, the locality
of $\mathcal{C}$ is $r$ from the parity-check matrix $H$ and Corollary 2.3. ∎

######  Theorem 4.6.

Let $r$ be a positive integer. Let $n\leqslant q-1$ be a positive integer such
that $n=mr+s$ with $1\leqslant s\leqslant r$ and let $d\leqslant s$ be a
positive integer. Then there exists a Singleton-optimal
$[n+\lceil\frac{n}{r}\rceil,n-d+1,d+1;r]_{q}$-locally repairable code.

###### Proof.

From Proposition 4.5, we have

$\displaystyle
n+\left\lceil\frac{n}{r}\right\rceil-(n-d+1)-\left\lceil\frac{n-d+1}{r}\right\rceil+2$
$\displaystyle=d+1+\left\lceil\frac{n}{r}\right\rceil-\left\lceil\frac{n-d+1}{r}\right\rceil$
$\displaystyle=d+1+\left\lceil\frac{mr+s}{r}\right\rceil-\left\lceil\frac{mr+s-d+1}{r}\right\rceil$
$\displaystyle=d+1\leqslant d(\mathcal{C}).$

Hence, $\mathcal{C}$ is a Singleton-optimal
$[n+\lceil\frac{n}{r}\rceil,n-d+1,d+1;r]_{q}$-locally repairable code. ∎

######  Example 4.7.

Let $q=2^{6}=64$, $n=63$ and $r=11$. It is clear that $63=11\times 5+8$, i.e.,
$s=8$. Choose $d=8$. From Theorem 4.6, there exists a Singleton-optimal
$[69,56,9;11]_{64}$-locally repairable codes with locality $r=11$.

######  Remark 4.

From Theorem 4.6, we can explicitly construct a new family of Singleton-
optimal locally repairable codes with length up to
$q-1+\lceil\frac{q-1}{r}\rceil$, which is larger than $q$ compared with [7,
19, 34]. If the minimum distance $d$ is large and linearly proportional to
$q$, then $r$ is linear proportional to $q-1$ as well, i.e.,
$\lceil\frac{q-1}{r}\rceil$ is a constant with respect to large $q$. In this
case, the length of such Singleton-optimal locally repairable codes is less
than the $q+2\sqrt{q}$ which can be obtained from elliptic curves [20, 26].

###  4.3. Asymptotic bounds of locally repairable codes

In [25], the authors gave a very technical and complicated method to obtain an
asymptotic bound exceeding the Gilbert-Varshamov bound for locally repairable
codes via local expansions of carefully chosen functions in the Garcia-
Stichtenoth tower. In this subsection, we provide a much simpler proof for
such an asymptotic bound given in [25, Theorem 5] via lengthening algebraic
geometry codes.

Let $r$ be a fixed positive integer. Let $\\{C_{i}\\}_{i=1}^{\infty}$ be a
family of $q$-ary $[n_{i},k_{i},d_{i}]$-linear codes with information rate and
relative minimum distance $R_{1}=\lim_{i\rightarrow\infty}\frac{k_{i}}{n_{i}}$
and $\delta_{1}=\lim_{i\rightarrow\infty}\frac{d_{i}}{n_{i}}.$ From
Proposition 4.2, there exists a family of
$[n_{i}+\lceil\frac{n_{i}}{r}\rceil,k_{i},\geqslant d_{i};r]$-locally
repairable codes. Then the information rate of this family of locally
repairable codes is

$R=\lim_{i\rightarrow\infty}\frac{k_{i}}{n_{i}+\lceil\frac{n_{i}}{r}\rceil}=\lim_{i\rightarrow\infty}\frac{k_{i}}{n_{i}}\times\frac{n_{i}}{n_{i}+\lceil\frac{n_{i}}{r}\rceil}=\frac{r}{r+1}R_{1}$

and its relative minimum distance is

$\delta=\lim_{i\rightarrow\infty}\frac{d_{i}}{n_{i}+\lceil\frac{n_{i}}{r}\rceil}=\lim_{i\rightarrow\infty}\frac{d_{i}}{n_{i}}\times\frac{n_{i}}{n_{i}+\lceil\frac{n_{i}}{r}\rceil}=\frac{r}{r+1}\delta_{1}.$

Combining with the classical Gilbert-Varshamov bound [33, Proposition 8.4.4],
we have the following result.

######  Proposition 4.8.

Let $H_{q}(x)$ be the $q$-ary entropy function
$H_{q}(x):=x\log_{q}(q-1)-x\log_{q}(x)-(1-x)\log_{q}(1-x).$ Then there exists
a family of $q$-ary locally repairable codes with locality $r$ whose
information rate $R$ and relative minimum distance $\delta$ satisfy

$R\geqslant\frac{r}{r+1}\left(1-H_{q}\Big{(}\frac{r+1}{r}\delta\Big{)}\right).$

Combining with the TVZ bound of algebraic geometry codes [33, Proposition
8.4.7], we have

$\frac{r+1}{r}R\geqslant 1-\frac{1}{A(q)}-\frac{r+1}{r}\delta.$

Hence, we have shown the following result which is the same as [25, Theorem
5].

######  Theorem 4.9.

Let $q$ be a prime power and let $A(q)$ be the Ihara’s constant. Then there
exists a family of $q$-ary locally repairable codes with locality $r$ whose
information rate $R$ and relative minimum distance $\delta$ satisfy

(22) $R\geqslant\frac{r}{r+1}-\frac{1}{A(q)}\times\frac{r}{r+1}-\delta.$

Figure 3. $q=2^{12},r=61$

The Figure 3 shows that the bound given in Theorem 4.9 can exceed the
asymptotic Gilbert-Varshamov bound of locally repairable codes for
$q=2^{12},r=61$. Hence, we greatly simplify the bound given in [25, Theorem 5]
that breaks the asymptotic Gilbert-Varshamov bound for locally repairable
codes.

## References

  * [1] A. Barg, I. Tamo, and S. Vlăduţ, Locally recoverable codes on algebraic curves, IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4928–4939, Aug. 2017.
  * [2] A. Barg, K. Haymaker, E. Howe, G. Matthews, and A. Varilly-Alvarado, Locally recoverable codes from algebraic curves and surfaces, in Algebraic Geometry for Coding Theory and Cryptography, E.W. Howe, K.E. Lauter, and J.L. Walker, Editors, Springer, 2017, pp. 95–126.
  * [3] V. Cadambe and A. Mazumdar, Bounds on the size of locally recoverable codes, IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 5787–5794, Nov. 2015.
  * [4] H. Cai, Y. Miao, M. Schwartz and X. Tang, On optimal locally repairable codes with multiple disjoint repair sets, IEEE Trans. Inf. Theory, vol. 66, no. 4, pp. 2402–2416, Apr. 2020.
  * [5] H. Cai, Y. Miao, M. Schwartz and X. Tang, On optimal locally repairable codes with super-linear length, IEEE Trans. Inf. Theory, vol. 66, no.8, pp. 4853–4868, Aug. 2020.
  * [6] B. Chen, W. Fang, S. Xia and F. Fu, Constructions of optimal $(r,\delta)$ locally repairable codes via constacyclic codes, IEEE Trans. on Communication, vol. 67, no. 8, pp. 5253–5263, Aug. 2019.
  * [7] B. Chen, S. Xia, J. Hao and F. Fu, Constructions of optimal cyclic $(r,\delta)$ locally repairable codes, IEEE Trans. Inf. Theory, vol. 64, no. 4, pp. 2499–2511, Apr. 2018.
  * [8] W. Fang and F. Fu, Optimal cyclic $(r,\delta)$ locally repairable codes with unbounded length, Finite Fields Appli. 63(2020), 101650.
  * [9] M. Forbes and S. Yekhanin, On the locality of codeword symbols in non-linear codes, Discrete Math. vol. 324, no. 6, pp. 78–84, 2014.
  * [10] A. Garcia and H. Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vlăduţ bound, Invent. Math., vol. 121, pp. 211–222, 1995.
  * [11] P. Gopalan, C. Huang, H. Simitci and S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inf. Theory , vol. 58, no. 11, pp. 6925–6934, Nov. 2012.
  * [12] V. Guruswami, C. Xing and C. Yuan, How long can optimal locally repairable codes be? IEEE Trans. Inf. Theory, vol. 65, no. 6, pp. 3362–3370, Jun. 2019.
  * [13] J. Han and L. A. Lastras-Montano, Reliable memories with subline accesses, Proc. IEEE Internat. Sympos. Inform. Theory, 2007, pp. 2531–2535.
  * [14] J. Hao, S. Xia, K. W. Shum, B. Chen, F. Fu and Y. Yang, Bounds and Constructions of Locally Repairable Codes: Parity-Check Matrix Approach, IEEE Trans. Inf. Theory, vol. 66, no. 12, pp. 7465–7474, Dec. 2020.
  * [15] C. Huang, M. Chen, and J. Li, Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems, Sixth IEEE International Symposium on Network Computing and Applications, 2007, pp. 79–86.
  * [16] P. Huang, E. Yaakobi, H. Uchikawa and P. H. Siegel, Binary linear locally repairable codes, IEEE Trans. Inf. Theory, vol. 62, no. 11, pp. 6268–6283, Nov. 2016.
  * [17] L. Jin, Explicit construction of optimal locally recoverable codes of distance $5$ and $6$ via binary constant weight codes, IEEE Trans. Inf. Theory, vol. 65, no. 8, pp. 4658–4663, Aug. 2019.
  * [18] L. Jin, H. Kan and Y. Zhang, Construction of locally repairable codes with multiple recovering sets via rational function fields, IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 202–209, Jan. 2020.
  * [19] L. Jin, L. Ma and C. Xing, Construction of optimal locally repairable codes via automorphism groups of rational function fields, IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 210–221, Jan. 2021.
  * [20] X. Li, L. Ma and C. Xing, Optimal locally repairable codes via elliptic curves, IEEE Trans. Inf. Theory, vol. 65, no. 1, pp. 108–117, Jan. 2019.
  * [21] X. Li, L. Ma and C. Xing, Construction of asymptotically good locally repairable codes via automorphism groups of function fields, IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 7087–7094, Nov. 2019.
  * [22] S. Ling and C. Xing, Coding Theory: A First Course, Cambridge, 2004.
  * [23] G. Luo and X. Cao, Constructions of optimal binary locally recoverable codes via a general construction of linear codes, IEEE Trans. Commun., vol. 69, no. 8, pp. 4987–4997, Aug. 2021.
  * [24] Y. Luo, C. Xing and C. Yuan, Optimal locally repairable codes of distance $3$ and $4$ via cyclic codes, IEEE Trans. Inf. Theory, vol. 65, no. 2, pp. 3662–2670, Feb. 2019.
  * [25] L. Ma and C. Xing, Constructive asymptotic bounds of locally repairable codes via function fields, IEEE Trans. Inf. Theory, vol. 66, no. 9, pp. 5395–5403, Sep. 2020.
  * [26] L. Ma and C. Xing, The group structures of automorphism groups of elliptic function fields over finite fields and optimal locally repairable codes, arXiv:2008.12119.
  * [27] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977.
  * [28] D. S. Papailiopoulos and A.G. Dimakis, Locally repairable codes, IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 5843–5855, Oct. 2014.
  * [29] N. Prakash, G.M. Kamath, V. Lalitha and P.V. Kumar, Optimal linear codes with a local-error-correction property, Proc. 2012 IEEE Int. Symp. Inform. Theory, 2012, pp. 2776–2780.
  * [30] C. Salgado, A. Varilly-Alvarado and J. Voloch, Locally repairable codes on surfaces, IEEE Trans. Inf. Theory, vol. 67, no. 9, pp. 5765–5777, Sep. 2021.
  * [31] N. Silberstein, T. Etzion and M. Schwartz, Locality and availability of array codes constructed from subspaces, IEEE Trans. Inf. Theory, vol. 65, no. 5, pp. 2648–2660, May 2019.
  * [32] N. Silberstein, A.S. Rawat, O.O. Koyluoglu and S. Vichwanath, Optimal locally repairable codes via rank-matric codes, Proc. IEEE Int. Symp. Inf. Theory, 2013, pp. 1819–1823.
  * [33] H. Stichtenoth, Algebraic Function Fields and Codes, Graduate Texts in Mathematics, vol. 254, Berlin, Germany: Springer Verlag, 2009.
  * [34] I. Tamo and A. Barg, A family of optimal locally recoverable codes, IEEE Trans. Inf. Theory, vol. 60, no.8, pp. 4661–4676, Aug. 2014.
  * [35] I. Tamo, A. Barg and A. Frolov, Bounds on the parameters of locally recoverable codes, IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3070–3083, Jun. 2016.
  * [36] I. Tamo, D.S. Papailiopoulos and A.G. Dimakis, Optimal locally repairable codes and connections to matroid theory, IEEE Trans. Inf. Theory, vol. 62, no. 12, pp. 6661–6671, Dec. 2016.
  * [37] A. Wang, Z. Zhang and D. Lin, Bounds for binary linear locally repairable codes via a sphere-packing approach, IEEE Trans. Inf. Theory, vol. 65, no. 7, pp. 4167-4179, Jul. 2019.
  * [38] C. Xing and C. Yuan, Construction of optimal $(r,\delta)$-locally recoverable codes and connection with graph theory, IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4320-4328, Jul. 2022.