# A general family of MSRD codes and PMDS codes with smaller field sizes from
extended Moore matrices

Umberto Martínez-Peñas<EMAIL_ADDRESS>Institute of Computer Science
and Mathematics, University of Neuchâtel, Switzerland

###### Abstract

In this work, a general method for constructing linear maximum sum-rank
distance (MSRD) codes is introduced. By a previous result of the author, any
of these MSRD codes provides a linear partial-MDS (PMDS) code, also known as
maximally recoverable (MR) locally repairable code (LRC). For the MSRD code
constructions, extended Moore matrices are introduced. These matrices extend
generator matrices of linearized Reed-Solomon codes, in the sense that
evaluation points inside a conjugacy class need not be linearly independent
over the base field. The key result of this work is a characterization of
evaluation points per conjugacy class that turn extended Moore matrices into
the parity-check (or generator) matrix of a linear MSRD code. The sufficient
and necessary conditions on the evaluation points constitute a natural
generalization of the geometric concept of (partial) spread. Extending Segre’s
original construction of spreads, we provide a method based on tensor products
to produce satisfactory sequences of evaluation points. The method takes as
input a Hamming-metric code and gives as output a linear MSRD code. A list of
linear MSRD codes admitting a wide range of parameters is then obtained,
giving as input trivial codes (yielding linearized Reed-Solomon codes), MDS
codes, Hamming codes, BCH codes and several Algebraic-Geometry codes. Each of
the obtained MSRD codes attains the smallest known field size, or the largest
number of matrix sets, for some parameter regime. In particular, the MSRD
codes based on Hamming codes, valid for minimum sum-rank distance $3$, meet a
recent bound by Byrne et al. These codes are also the first and only known
MSRD codes with field sizes that are linear in the code length if the number
of columns per matrix is constant. Finally, two new families of PMDS codes are
obtained attaining smaller field sizes than those in the literature for many
parameter regimes.

Keywords: Distributed storage, linearized Reed-Solomon codes, locally
repairable codes, Moore matrices, MDS codes, MRD codes, MSRD codes, PMDS
codes, sum-rank metric.

MSC: 15B33; 11T71; 94B27; 94B65

##  1 Introduction

Maximum distance separable (MDS) codes are “optimal” in the sense that their
minimum Hamming distance [20] attains the Singleton bound [45]. Although this
bound is a crude bound on the minimum Hamming distance of codes over small
alphabets, MDS codes are optimal erasure codes from an information-theoretical
perspective: Over large enough alphabets and for a fixed information rate and
block length, any Hamming-metric erasure pattern (any subset of coordinates to
be erased) that can be corrected by some code can be corrected by any MDS
code.

For this reason, in erasure scenarios where alphabets need not be too small
and where information rates and block lengths are fixed, MDS codes offer the
best erasure correction capability. One of such erasure scenarios is that of
node repair in distributed storage, where MDS codes were traditionally a
popular choice. In this scenario, a node may need to be repaired due to its
data being lost, but also due to being unresponsive or unavailable.

However, repairing a single node out of $n$ nodes using an MDS code of rate
$k/n$ requires contacting $k$ other nodes. With the large amounts of data
stored in nowadays’ distributed storage systems, repairing a single node (the
most frequent erasure pattern) results in a high latency due to reading and
decoding large amounts of data. Locally repairable codes (LRCs) [17, 24] may
repair one node (or more generally, $\delta-1$ nodes per local set) by
contacting only a small number $r$ (called locality) of other nodes.
Simultaneously, they are able to correct a large number of global erasures in
catastrophic cases, in contrast with simply using a Cartesian product of MDS
codes of dimension $r$ and block length $r+\delta-1$.

Although extensions of the Singleton bound are known for LRCs (see, e.g., [17,
Eq. (2)] or [24, Th. 2.1]), they do not have the same information-theoretical
meaning as the classical bound [45]. More concretely, an LRC whose (global)
minimum Hamming distance attains such a Singleton bound is not necessarily
capable of correcting all the erasure patterns correctable by some other LRC
of the same parameters. LRCs that may correct all the erasure patterns
correctable by some other LRC with the same locality constraints, over a large
enough alphabet, are called partial MDS (PMDS) codes or maximally recoverable
(MR) LRCs. They were introduced independently in [3, 16] and may correct any
$\delta-1$ erasures per local set, plus any extra $h$ erasures elsewhere.
Here, $\delta$ is the distance of the local codes, and $h$ is the co-dimension
of the global code after puncturing it on any $\delta-1$ coordinates per local
set, hence called the number of global or heavy parities.

Several constructions of PMDS codes exist in the literature [3, 4, 5, 7, 9,
14, 16, 19, 22, 36, 37]. In Construction 1 in [36], it was shown that any
maximum sum-rank distance (MSRD) code [31] may be easily and explicitly turned
into a PMDS code [36, Th. 2]. Moreover, such Construction 1 enjoys further
flexibility and dynamic properties such as being compatible with an arbitrary
choice of local codes, locally replacing such local codes without changing the
overall storage architecture or recoding all the stored data, and enabling any
hierarchical structure of local codes with any number of levels and always
being able to correct any information-theoretically correctable erasure
pattern for the corresponding locality constraints (see [36]). As another
application of the flexibility enabled by MSRD codes, optimal LRCs with
multiple disjoint repair sets were obtained based on MSRD codes in [8].

Apart from being used as PMDS codes for repair in distributed storage [36],
MSRD codes have found applications in universal error correction and security
in multishot network coding [38, 35], rate-diversity optimal space-time codes
with multiple fading blocks and minimum delay [29, 44], and private
information retrieval on PMDS-coded databases or where communication with
servers is through a linearly coded network [32]. They may be applicable in a
multishot or multilayer version of crisscross error and erasure correction,
extending [41].

In this work, MSRD codes are considered as those codes whose minimum sum-rank
distance [38] attains the Singleton bound given in [36, Cor. 2]. By the same
result, such MSRD codes may be defined as MDS codes that remain MDS after
being multiplied by any invertible block-diagonal matrix of the appropriate
sizes (see Definition 6). It is precisely because of this mathematical
property that any MSRD code may be turned into a PMDS code as in Construction
1 in [36], enjoying all the properties described above (see [36, Th. 3]).

In scenarios where large alphabets are allowed, codes over small fields are
preferable, as they enjoy lower computational complexity while being able to
fit the larger alphabets (by encoding data by “chunks”). In contrast with MDS
codes, PMDS codes with linear field sizes in the code length do not exist for
general parameters [18, Th. 3.5 and 3.8]. Hence the same holds for MSRD codes
by Construction 1 in [36]. See Subsection 2.4 for a detailed discussion on
field sizes.

Any maximum rank distance (MRD) code [12, 13, 41] may be used as an MSRD or
PDMS code. However, the field size of any MRD code is exponential in the code
length, rendering them impractical in most cases. PMDS codes with sub-
exponential field sizes were obtained in [3, 4, 5, 7, 14, 16, 19, 22, 36, 37].
The first and only known MSRD codes with sub-exponential field sizes are
linearized Reed-Solomon codes [31] (obtained later independently in [11, 39]),
which recover as particular cases (generalized) Reed-Solomon codes [40] and
Gabidulin codes [12, 13, 41] whenever the sum-rank metric recovers the Hamming
metric and the rank metric, respectively. Recently, a few MSRD codes were
found in [6] for minimum sum-rank distance $2$ or block length minus $1$, or
for parameters with trivial matrix sizes in some components (see Section 5).

In this work, we obtain a general family of MSRD codes (thus PMDS codes) whose
field sizes are smaller than those obtained before for many parameter regimes.
See Section 5 for a detailed summary and comparisons, and the Appendix for
concrete tables. Interestingly, for minimum sum-rank distance $3$ (co-
dimension $h=2$), we obtain MSRD codes whose parameters meet the bound
recently given in [6, Th. 6.12] (see Subsections 2.4 and 4.5). Remarkably,
such codes are the first and only known MSRD codes with minimum sum-rank
distance at least $3$ and linear field sizes in the block length when the
number columns per matrix is arbitrary but constant.

We obtain the general family of MSRD codes as follows. We define extended
Moore matrices (Definition 21), which coincide with the matrices introduced in
[31, p. 604] but where evaluation points per conjugacy class need not be
linearly independent over the base field. We then characterize when extended
Moore matrices are the parity-check matrix (or generator matrix) of an MSRD
code (Theorem 2). The obtained sufficient and necessary conditions on the
evaluation points constitute a generalization of the concept of (partial)
spread in projective geometry. Extending Segre’s construction of spreads [42],
we construct sequences of evaluation points satisfying the required conditions
by using tensor products of a basis of a small finite-field extension with a
sequence of $t$-wise independent [16, Def. 9] elements over a larger finite-
field extension (Theorem 3). As $t$-wise independent sequences coincide with
linear Hamming-metric codes by vectorizing finite-field extensions (Lemma 35),
what is left is to use families of Hamming-metric codes with small redundancy.
Our choices (which seem to be the best) of such Hamming-metric codes are:
Trivial codes, yielding linearized Reed-Solomon codes (Subsection 4.3); MDS
codes (Subsection 4.4); Hamming codes, equivalent to spreads as constructed by
Segre (Subsection 4.5); primitive BCH codes (Subsection 4.6); and Algebraic-
Geometry (AG) codes, including Hermitian AG codes (Subsection 4.8); Suzuki AG
codes (Subsection 4.9); and García-Stichtenoth’s second sequence of AG codes
(Subsection 4.10).

As mentioned above, our general family of MSRD codes recovers linearized Reed-
Solomon codes when using a trivial code to construct the evaluation points.
Even though linearized Reed-Solomon codes recover as particular cases
(generalized) Reed-Solomon codes [40] and Gabidulin codes [12, 13, 41], our
general family of MSRD does not seem to have an analogue in the Hamming metric
or the rank metric (see Remark 33).

The remainder of the manuscript is organized as follows. In Section 2, we
collect some preliminaries on MDS, MSRD and PMDS codes, together with some
considerations and known bounds on field sizes. In Section 3, we characterize
when a sequence of evaluation points turn an extended Moore matrix into the
parity-check matrix of an MSRD code. In Section 4, we construct such sequences
via tensor products and a range of known Hamming-metric codes. Finally, in
Section 5, we provide a summary of the obtained explicit MSRD and PMDS codes
and compare their parameters with codes from the literature. The Appendix
contains several tables with achievable field sizes in the binary case
(characteristic $2$).

## Basic notation

We will denote $\mathbb{N}=\\{0,1,2,\ldots\\}$ and
$\mathbb{Z}_{+}=\\{1,2,3,\ldots\\}$. For positive integers $m\leq n$, we
denote $[n]=\\{1,2,\ldots,n\\}$ and $[m,n]=\\{m,m+1,\ldots,n\\}$. For a field
$\mathbb{F}$, we denote $\mathbb{F}^{*}=\mathbb{F}\setminus\\{0\\}$ and we use
$\langle\cdot\rangle_{\mathbb{F}}$ and $\dim_{\mathbb{F}}(\cdot)$ to denote
$\mathbb{F}$-linear span and dimension over $\mathbb{F}$, respectively. We
denote by $\mathbb{F}^{m\times n}$ the set of $m\times n$ matrices with
entries in $\mathbb{F}$, and we denote $\mathbb{F}^{n}=\mathbb{F}^{1\times
n}$. The group of invertible matrices in $\mathbb{F}^{n\times n}$ is denoted
by ${\rm GL}_{n}(\mathbb{F})$. A code in $\mathbb{F}^{n}$ is any subset
$\mathcal{C}\subseteq\mathbb{F}^{n}$, and we say that $\mathcal{C}$ is a
linear code if it is an $\mathbb{F}$-linear vector subspace of
$\mathbb{F}^{n}$. For matrices $A_{1},A_{2},\ldots,$ $A_{g}$
$\in\mathbb{F}^{r\times s}$, for some positive integers $g$, $r$ and $s$, we
define the block-diagonal matrix

${\rm
diag}(A_{1},A_{2},\ldots,A_{g})=\left(\begin{array}[]{cccc}A_{1}&0&\ldots&0\\\
0&A_{2}&\ldots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\ldots&A_{g}\end{array}\right)\in\mathbb{F}^{gr\times gs}.$

We will also denote by $\mathbf{c}\cdot\mathbf{d}\in\mathbb{F}$ the
conventional inner product of $\mathbf{c},\mathbf{d}\in\mathbb{F}^{n}$ (i.e.,
$\mathbf{c}\cdot\mathbf{d}=\mathbf{c}\mathbf{d}^{T}$), and we denote the dual
of a linear code $\mathcal{C}\subseteq\mathbb{F}^{n}$ by

$\mathcal{C}^{\perp}=\\{\mathbf{d}\in\mathbb{F}^{n}\mid\mathbf{c}\cdot\mathbf{d}=0,\textrm{
for all }\mathbf{c}\in\mathcal{C}\\}\subseteq\mathbb{F}^{n}.$

For a prime power $q$, we denote by $\mathbb{F}_{q}$ the finite field with $q$
elements. Throughout this manuscript, we will fix a prime power $q$ and a
finite-field extension $\mathbb{F}_{q}\subseteq\mathbb{F}_{q^{m}}$, for some
positive integer $m$. The field $\mathbb{F}_{q}$ will be called the base field
throughout the manuscript. Our target codes will be linear codes
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$, hence we will usually call
$\mathbb{F}_{q^{m}}$ the field of linearity of $\mathcal{C}$.

We will use the conventional big O, big Omega and big Theta notations for a
positive real-valued function $f$, written $\mathcal{O}(f)$, $\Omega(f)$ and
$\Theta(f)$, respectively. However, we will try to provide exact bounds as
much as possible, and we will leave the simplified asymptotic notation when
comparisons become complicated.

##  2 Preliminaries: MDS, MSRD and PMDS codes

###  2.1 MDS codes

For a positive integer $n$ and a field $\mathbb{F}$, we define the Hamming
weight [20] of a vector $\mathbf{c}=(c_{1},c_{2},\ldots,$ $c_{n})$
$\in\mathbb{F}^{n}$ by

${\rm wt}_{H}(\mathbf{c})=|\\{i\in[n]\mid c_{i}\neq 0\\}|.$

We define the Hamming metric ${\rm
d}_{H}:\left(\mathbb{F}^{n}\right)^{2}\longrightarrow\mathbb{N}$ by ${\rm
d}_{H}(\mathbf{c},\mathbf{d})={\rm wt}_{H}(\mathbf{c}-\mathbf{d})$, for all
$\mathbf{c},\mathbf{d}\in\mathbb{F}^{n}$. For a (linear or non-linear) code
$\mathcal{C}\subseteq\mathbb{F}^{n}$, we define its minimum Hamming distance
by

${\rm d}_{H}(\mathcal{C})=\min\left\\{{\rm
d}_{H}(\mathbf{c},\mathbf{d})\mid\mathbf{c},\mathbf{d}\in\mathcal{C},\mathbf{c}\neq\mathbf{d}\right\\}.$

We next revisit the Singleton bound [45].

######  Proposition 1 (Singleton bound [45]).

For any (linear or non-linear) code $\mathcal{C}\subseteq\mathbb{F}^{n}$, it
holds that

$|\mathcal{C}|\leq|\mathbb{F}|^{n-{\rm d}_{H}(\mathcal{C})+1}.$ (1)

We define maximum distance separable (MDS) codes as usual.

######  Definition 2 (MDS codes [45]).

We say that a (linear or non-linear) code $\mathcal{C}\subseteq\mathbb{F}^{n}$
is maximum distance separable (MDS) if equality holds in (1).

Recall that, for a linear code $\mathcal{C}\subseteq\mathbb{F}^{n}$ of
dimension $k$, we say that $G\in\mathbb{F}^{k\times n}$ and
$H\in\mathbb{F}^{h\times n}$, $h=n-k$, are a generator matrix and a parity-
check matrix of $\mathcal{C}$, respectively, if

$\mathcal{C}=\left\\{\mathbf{x}G\in\mathbb{F}^{n}\mid\mathbf{x}\in\mathbb{F}^{k}\right\\}=\left\\{\mathbf{y}\in\mathbb{F}^{n}\mid\mathbf{y}H=\mathbf{0}\right\\},$

respectively. As is well known, $H$ and $G$ form a generator matrix and a
parity-check matrix, respectively, of the dual code
$\mathcal{C}^{\perp}\subseteq\mathbb{F}^{n}$. The following result can be
found in [30, Th. 10, p. 33] and [23, Cor. 1.4.14, p. 12]. This lemma will be
crucial for our purposes (see Subsection 4.2).

######  Lemma 3.

Let $t$ be a positive integer, let $\mathcal{C}\subseteq\mathbb{F}^{n}$ be a
linear code of dimension $k$, and let $H\in\mathbb{F}^{h\times n}$ be one of
its parity-check matrices, where $h=n-k$. It holds that ${\rm
d}_{H}(\mathcal{C})\geq t+1$ if, and only if, any $t$ columns of $H$ are
linearly independent. In particular, $\mathcal{C}$ is MDS if, and only if, any
$h$ columns of $H$ are linearly independent.

###  2.2 MSRD codes

Fix positive integers $m$ and $r$, and an ordered basis
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2},\ldots,\alpha_{m})\in\mathbb{F}_{q^{m}}^{m}$
of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$. We define the matrix
representation map
$M_{\boldsymbol{\alpha}}:\mathbb{F}_{q^{m}}^{r}\longrightarrow\mathbb{F}_{q}^{m\times
r}$ by

$M_{\boldsymbol{\alpha}}\left(\sum_{i=1}^{m}\alpha_{i}\mathbf{c}_{i}\right)=\left(\begin{array}[]{cccc}c_{1,1}&c_{1,2}&\ldots&c_{1,r}\\\
c_{2,1}&c_{2,2}&\ldots&c_{2,r}\\\ \vdots&\vdots&\ddots&\vdots\\\
c_{m,1}&c_{m,2}&\ldots&c_{m,r}\\\ \end{array}\right)\in\mathbb{F}_{q}^{m\times
r},$ (2)

where $\mathbf{c}_{i}=(c_{i,1},c_{i,2},\ldots,c_{i,r})\in\mathbb{F}_{q}^{m}$,
for $i=1,2,\ldots,m$. In order to define sum-rank weights on vectors with
components in $\mathbb{F}_{q^{m}}$, we will subdivide them into subvectors as
$\mathbf{c}=(\mathbf{c}^{(1)},$ $\mathbf{c}^{(2)},$ $\ldots,$
$\mathbf{c}^{(g)})\in\mathbb{F}_{q^{m}}^{gr}$, where
$\mathbf{c}^{(i)}\in\mathbb{F}_{q^{m}}^{r}$, for $i=1,2,\ldots,g$, for a
positive integer $g$. Now using (2), we may consider
$\mathbf{c}\in\mathbb{F}_{q^{m}}^{gr}$ as a list of $g$ matrices of size
$m\times r$ over $\mathbb{F}_{q}$:

$\mathbf{c}=\left(\mathbf{c}^{(1)},\mathbf{c}^{(2)},\ldots,\mathbf{c}^{(g)}\right)\equiv\left(M_{\boldsymbol{\alpha}}\left(\mathbf{c}^{(1)}\right),M_{\boldsymbol{\alpha}}\left(\mathbf{c}^{(2)}\right),\ldots,M_{\boldsymbol{\alpha}}\left(\mathbf{c}^{(g)}\right)\right)\in\left(\mathbb{F}_{q}^{m\times
r}\right)^{g}.$ (3)

In this work, the matrix sizes at different positions all have size $m\times
r$. See Remark 8 below regarding different matrix sizes at different
positions.

The sum-rank metric was defined in [38, Sec. III-D], under the name extended
rank distance, as follows.

######  Definition 4 (Sum-rank metric [38]).

Let $g$ be a positive integer, and let $\mathbf{c}=(\mathbf{c}^{(1)},$
$\mathbf{c}^{(2)},$ $\ldots,$ $\mathbf{c}^{(g)})\in\mathbb{F}_{q^{m}}^{gr}$,
where $\mathbf{c}^{(i)}\in\mathbb{F}_{q^{m}}^{r}$, for $i=1,2,\ldots,g$. We
define the sum-rank weight of $\mathbf{c}$, for the length partition $(g,r)$
over the base field $\mathbb{F}_{q}$, by

${\rm wt}_{SR}(\mathbf{c})=\sum_{i=1}^{g}{\rm
Rk}\left(M_{\boldsymbol{\alpha}}(\mathbf{c}^{(i)})\right).$

Finally, we define the sum-rank metric ${\rm
d}_{SR}:\left(\mathbb{F}_{q^{m}}^{gr}\right)^{2}\longrightarrow\mathbb{N}$,
for the length partition $(g,r)$ over the base field $\mathbb{F}_{q}$, by
${\rm d}_{SR}(\mathbf{c},\mathbf{d})={\rm wt}_{SR}(\mathbf{c}-\mathbf{d})$,
for all $\mathbf{c},\mathbf{d}\in\mathbb{F}_{q^{m}}^{gr}$.

For a code $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{gr}$ (linear or non-
linear), we define its minimum sum-rank distance (for the length partition
$(g,r)$ over the base field $\mathbb{F}_{q}$) by

${\rm d}_{SR}(\mathcal{C})=\min\\{{\rm
d}_{SR}(\mathbf{c},\mathbf{d})\mid\mathbf{c},\mathbf{d}\in\mathcal{C},\mathbf{c}\neq\mathbf{d}\\}.$
(4)

The number $g$ will be called the number of matrix sets. In view of Remark 7
below, we will assume from now on that $m\geq r$, hence $r$ is the maximum
possible rank of an $m\times r$ matrix.

For brevity in the notation, we will omit the length partition $(g,r)$ and the
base field $\mathbb{F}_{q}$ when they are understood from the context.
However, it is important to keep in mind that the definition of sum-rank
metric in $\mathbb{F}_{q^{m}}^{gr}$ depends on $(g,r)$ and $\mathbb{F}_{q}$,
since the ($\mathbb{F}_{q}$-linear) vector space isomorphism
$\mathbb{F}_{q^{m}}^{gr}\cong\left(\mathbb{F}_{q}^{m\times r}\right)^{g}$
given by (3) depends on the triplet $(g,r,q)$. Considering codes in
$\mathbb{F}_{q^{m}}^{gr}$ instead of $\left(\mathbb{F}_{q}^{m\times
r}\right)^{g}$ will allow us to consider $\mathbb{F}_{q^{m}}$-linear codes and
to characterize MSRD codes in terms of MDS codes (Proposition 5).

Observe that the Hamming metric [20] and the rank metric [12, 13, 41] are
recovered from the sum-rank metric by setting $r=1$ and $g=1$, respectively.

We have the following extension of the Singleton bound from the Hamming metric
(Proposition 1) to the sum-rank metric, that is, from the case $r=1$ to the
case $r\geq 1$. This result was given in [36, Cor. 2].

######  Proposition 5 (Singleton bound [36]).

Let $g$ be a positive integer, and let
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{gr}$ be a (linear or non-linear)
code. It holds that

$|\mathcal{C}|\leq q^{m(gr-{\rm d}_{SR}(\mathcal{C})+1)}.$ (5)

Furthermore, equality holds in (5) if, and only if, $\mathcal{C}\cdot{\rm
diag}(A_{1},A_{2},\ldots,A_{g})\subseteq\mathbb{F}_{q^{m}}^{gr}$ is MDS, for
all $A_{1},A_{2},\ldots,A_{g}\in{\rm GL}_{r}(\mathbb{F}_{q})$.

The main objects of study in this manuscript are maximum sum-rank distance
(MSRD) codes, introduced in [31, Th. 4], which are a natural extension of MDS
codes (Definition 2).

######  Definition 6 (MSRD codes [31]).

For a positive integer $g$, we say that a (linear or non-linear) code
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{gr}$ is maximum sum-rank distance
(MSRD), for the length partition $(g,r)$ and the base field $\mathbb{F}_{q}$,
if equality holds in (5), or equivalently, if $\mathcal{C}\cdot{\rm
diag}(A_{1},A_{2},\ldots,A_{g})\subseteq\mathbb{F}_{q^{m}}^{gr}$ is MDS, for
all $A_{1},A_{2},\ldots,A_{g}\in{\rm GL}_{r}(\mathbb{F}_{q})$, by Proposition
5.

######  Remark 7.

It was shown in [36, Cor. 3] that, if $m<r$, then there is no MSRD code in
$\mathbb{F}_{q^{m}}^{gr}$ as in Definition 6 with minimum sum-rank distance
larger than $1$. For this reason, we will assume from now on that $m\geq r$.
An alternative Singleton bound exists for the case $m<r$ [36, Cor. 3], but any
MSRD code as in Definition 6 achieves such a bound for the same number of
matrix sets $g$ by transposing the matrices in (3). The resulting codes are
however only $\mathbb{F}_{q}$-linear.

######  Remark 8.

Given a linear MSRD code in $\mathbb{F}_{q^{m}}^{gr}$, one may obtain a linear
MSRD code in $\mathbb{F}_{q^{m}}^{r_{1}+r_{2}+\cdots+r_{g}}$, with different
numbers of columns $r_{1},r_{2},\ldots,r_{g}\leq r$ per matrix as in (3), by
puncturing or shortening on some coordinates [33, Cor. 7]. Singleton bounds
and MSRD code constructions for the case of different numbers of both rows and
columns at different positions in the matrices in (3) can be found in [6].
However, the codes constructed in [6] are only $\mathbb{F}_{q}$-linear, have
minimum sum-rank distance $2$ or $\sum_{i=1}^{g}r_{i}-1$, or require the
number of rows and columns to be $1$ at some positions.

The following result was proven in [33, Th. 5].

######  Lemma 9 ([33]).

For a positive integer $g$, a linear code
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{gr}$ is MSRD if, and only if, its
dual $\mathcal{C}^{\perp}\subseteq\mathbb{F}_{q^{m}}^{gr}$ is MSRD, in both
cases for the length partition $(g,r)$ and base field $\mathbb{F}_{q}$.

What Lemma 9 implies is that, in order to construct linear MSRD codes, we may
utilize either generator matrices or parity-check matrices, and focus on
either low-dimensional or high-dimensional linear codes. In this work, we will
construct high-dimensional linear MSRD codes by building their parity-check
matrices with a small number of rows. This is because, although not always,
information rates are generally larger than $1/2$ in real scenarios.

###  2.3 PMDS codes

In this subsection, we briefly recall the definitions of locally repairable
codes [17, 24] and PMDS codes [3, 16]. We conclude with Construction 1 from
[36] that turns any MSRD code into a PMDS code, essentially showing that the
former is a subfamily of the latter.

######  Definition 10 (Locally repairable codes [17, 24]).

For positive integers $g$, $r$ and $\delta$, we say that a code
$\mathcal{C}\subseteq\mathbb{F}^{n}$ is a locally repairable code (LRC) with
$(r,\delta)$-localities if $n=g(r+\delta-1)$ and we may partition
$[n]=\Gamma_{1}\cup\Gamma_{2}\cup\ldots\cup\Gamma_{g}$, such that, if we
denote $\nu=r+\delta-1$, then

  1. 1.

$\Gamma_{i}=[(i-1)\nu+1,i\nu]$, thus $|\Gamma_{i}|=\nu$, and

  2. 2.

${\rm d}_{H}(\mathcal{C}_{\Gamma_{i}})\geq\delta$,

where $\mathcal{C}_{\Gamma_{i}}\subseteq\mathbb{F}^{\nu}$ denotes the
projection of $\mathcal{C}$ onto the coordinate in $\Gamma_{i}$, for
$i=1,2,\ldots,g$. The set $\Gamma_{i}$ is called the $i$th local set and $\nu$
is the local-set size. In many occasions, we only use the term locality for
the number $r$, whereas $\delta$ is called the local distance.

Partial MDS (PMDS) codes, introduced in [3, 16], are those LRCs that may
correct any erasure pattern that is information-theoretically correctable
given the locality constraints in Definition 10. Such patterns are exactly
those with $\delta-1$ erasures per local set and an extra $h=gr-k$ erasures
anywhere else, where $k=\dim(\mathcal{C})$. This is equivalent to obtaining an
MDS code after puncturing on any $\delta-1$ coordinates per local set. We will
follow this formulation.

######  Definition 11 (PMDS codes [3, 16]).

We say that a linear code $\mathcal{C}\subseteq\mathbb{F}^{n}$ is a partial
MDS (PMDS) code with $(r,\delta)$-localities if it is an LRC with
$(r,\delta)$-localities and, for any $\Delta_{i}\subseteq\Gamma_{i}$ with
$|\Delta_{i}|=r$, for $i=1,2,\ldots,g$, the restricted code
$\mathcal{C}_{\Delta}\subseteq\mathbb{F}^{gr}$ is MDS, where
$\Delta=\bigcup_{i=1}^{g}\Delta_{i}$.

The following construction is Construction 1 in [36].

######  Construction 1 ([36]).

Fix positive integers $g$ and $r$. Choose a base field size $q$ and an
extension degree $m\geq r$, and define the field of linearity of our target
codes as $\mathbb{F}=\mathbb{F}_{q^{m}}$. Next choose:

  1. 1.

Outer code: A linear code $\mathcal{C}_{out}\subseteq\mathbb{F}_{q^{m}}^{gr}$
that is MSRD for the length partition $(g,r)$ over $\mathbb{F}_{q}$.

  2. 2.

Local codes: MDS codes
$\mathcal{C}_{loc}^{(i)}\subseteq\mathbb{F}_{q}^{r+\delta-1}$, linear over the
base field $\mathbb{F}_{q}$ and of dimension $r$, for $i=1,2,\ldots,g$.

  3. 3.

Global code: Let $\mathcal{C}_{glob}\subseteq\mathbb{F}_{q^{m}}^{n}$, where
$n=g(r+\delta-1)$, be given by

$\mathcal{C}_{glob}=\mathcal{C}_{out}\cdot{\rm
diag}(A_{1},A_{2},\ldots,A_{g}),$

where $A_{1},A_{2},\ldots,A_{g}\in\mathbb{F}_{q}^{r\times(r+\delta-1)}$ are
arbitrary generator matrices of $\mathcal{C}_{loc}^{(i)}$, for
$i=1,2,\ldots,g$.

The following result is [36, Th. 2].

######  Proposition 12 ([36]).

The linear code $\mathcal{C}_{glob}\subseteq\mathbb{F}_{q^{m}}^{n}$ from
Construction 1 has dimension
$k=\dim(\mathcal{C}_{out})=\dim(\mathcal{C}_{glob})$ and is a PMDS code with
$(r,\delta)$-localities.

In conclusion, any MSRD code as in Definition 6 naturally gives a PMDS code
via Construction 1. By puncturing on any $\delta-1$ coordinates per local set,
we recover a linear code that is sum-rank isometric to the original MSRD code
$\mathcal{C}_{out}$. If the generator matrices
$A_{1},A_{2},\ldots,A_{g}\in\mathbb{F}_{q}^{r\times(r+\delta-1)}$ of the local
codes are chosen to be systematic, and we puncture on the $\delta-1$
coordinates corresponding to parity symbols in each local set, then we exactly
recover the MSRD code $\mathcal{C}_{out}$.

######  Remark 13.

If $\delta=1$ or $\delta=2$, then there is no additional restriction on the
base field $\mathbb{F}_{q}$, as MDS codes with minimum Hamming distance $1$ or
$2$ exist over any finite field. However, if $\delta>2$, then we need to
assume that $q\geq r+\delta-1$ in order to use known MDS codes over
$\mathbb{F}_{q}$, such as Reed-Solomon codes [40].

###  2.4 Field sizes in applications of MSRD codes

Before constructing MSRD codes (thus PMDS codes by Construction 1), it is
important to know what we want in an MSRD code. Otherwise we are lost before
starting.

The parameters of the ambient space are $m$, $r$ (matrix sizes), $g$ (number
of matrix sets) and $q$ (base field size). However, the computational
complexity of encoding and decoding with a linear (over $\mathbb{F}_{q^{m}}$)
code in $\mathbb{F}_{q^{m}}^{gr}$ is strongly governed by the size of the
field of linearity: $q^{m}$.

In some applications of MSRD codes, such as constructing PMDS codes
(Subsection 2.3) or universal error-correcting codes in multishot linear
network coding [35], the base field $\mathbb{F}_{q}$ is an artifice only
constrained to contain a given finite field $\mathbb{F}_{q_{0}}$. The field
$\mathbb{F}_{q_{0}}$ is the field of linearity of the local codes in PMDS
codes (Construction 1) or the field of coefficients for linear network coding
[35]. In these scenarios, $q_{0}$ is generally much smaller than the size of
an erased unit, e.g., an erased storage node or a network packet in error (we
are comparing $q_{0}=2,2^{2},2^{3},\ldots$ with MiB $=2^{20\cdot 8}$, GiB
$=2^{30\cdot 8}$, TiB $=2^{40\cdot 8}$, $\ldots$). The final constraints on
the pair $(m,q)$ are that $\mathbb{F}_{q_{0}}\subseteq\mathbb{F}_{q}$ (i.e.,
$q$ is a power of $q_{0}$) and the size of an erased unit, measured in number
of bits, is a multiple of $m\log_{2}(q)$ (the erased unit is a vector with
components in $\mathbb{F}_{q^{m}}$). This means that, in such applications, we
have almost full freedom on the pair $(m,q)$ (to construct PMDS codes we only
need $q\geq\nu$ if $\delta>2$, and there is no restriction on $q$ if
$\delta=2$, by Remark 13). Thus the main focus is on obtaining a size
$|\mathbb{F}_{q^{m}}|=q^{m}$ as small as possible in order to reduce the
computational complexity of encoding and decoding, without worrying about the
exact pair $(m,q)$. For instance, to construct PMDS codes, $(m_{1},q_{1})$ is
better than $(m_{2},q_{2})$ if, and only if, $q_{1}^{m_{1}}<q_{2}^{m_{2}}$, as
long as both $q_{1}\geq\nu$ and $q_{2}\geq\nu$, regardless of the relation
between $q_{1}$ and $q_{2}$, and between $m_{1}$ and $m_{2}$.

However, in other applications, such as rate-diversity optimal multiblock
space-time codes [29, 44] or multilayer/multishot versions of criss-cross
error correction [41], we may not have such flexibility on the pair of
parameters $(m,q)$. In criss-cross error correction [41], errors occur along
rows and columns of matrices in $\mathbb{F}_{q}^{m\times r}$, where in many
cases, $q=2$. Here, codewords need to fit such structures and we do not have
any flexibility on the pair $(m,q)$. Hence we just need to find an MSRD code
with suitable parameters $m$, $r$, $g$ and $q$. When building rate-diversity
optimal multiblock space-time codes, the base field size $q$ corresponds to
the constellation size, $m$ corresponds to the time delay, $r$ is the number
of transmit antennas and $g$ is the number of fading blocks (see [44]).
Therefore, in this case, small $q$ may be desirable for implementation
purposes. As an example, space-time codes based on linearized Reed-Solomon
codes [31] achieve minimum possible delay $m=r$ and constellation size
$q\approx g$, while space-time codes based on cyclic division algebras [43]
require constellation sizes that are exponential in $g$ and which suffer from
approximation errors in the neighbourhood of the complex-plane origin (see
[44]).

If we fix $q$, then it is desirable to obtain linear MSRD codes with smallest
possible value of $m$. This is because of the next proposition, which is left
to the reader to prove. It means that if we find a linear MSRD code for a pair
$(q,m)$, then we may easily obtain a linear MSRD code for the pair $(q,mM)$,
for any positive integer $M$, being all other parameters equal. Thus an MSRD
code with a smaller value of $m$ enables a wider range of attainable values of
$m$.

######  Proposition 14.

For positive integers $m$, $r$ and $g$, and for a linear code
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{gr}$, define

$\mathcal{C}\otimes\mathbb{F}_{q^{mM}}=\left\\{\lambda\mathbf{c}\mid\mathbf{c}\in\mathcal{C},\lambda\in\mathbb{F}_{q^{mM}}\right\\}\subseteq\mathbb{F}_{q^{mM}}^{gr},$

for any positive integer $M$. Then $\mathcal{C}\otimes\mathbb{F}_{q^{mM}}$ is
$\mathbb{F}_{q^{mM}}$-linear,

$\dim_{\mathbb{F}_{q^{m}}}\left(\mathcal{C}\right)=\dim_{\mathbb{F}_{q^{mM}}}\left(\mathcal{C}\otimes\mathbb{F}_{q^{mM}}\right),$

and the minimum sum-rank distances of $\mathcal{C}$ and
$\mathcal{C}\otimes\mathbb{F}_{q^{mM}}$ are the same, in both cases for the
length partition $(g,r)$ over the field $\mathbb{F}_{q}$. In particular,
$\mathcal{C}$ is MSRD if, and only if, so is
$\mathcal{C}\otimes\mathbb{F}_{q^{mM}}$.

A difficult research problem, still open in most cases, is to determine
constraints in $m$, $q$ and $q^{m}$ for the existence of MSRD codes and PMDS
codes. This problem is a highly non-trivial extension of the well known MDS
conjecture (not even the asymptotic order of possible MSRD or PMDS codes is
known in general, whereas we know that MDS codes exist if, and only if, the
code length is at most linear in the field size).

Recently, the following bounds were given in [6, Th. 6.12] for MSRD codes.

######  Proposition 15 ([6]).

For positive integers $m$, $r$ and $g$, let
$\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{gr}$ be a (linear or non-linear) MSRD
code. If we set $h={\rm d}_{SR}(\mathcal{C})-1\geq 2$, then

$g\leq\left\lfloor\frac{h-2}{r}\right\rfloor+\left\lfloor(q-1)\cdot\frac{q^{m}}{q^{r}-1}\right\rfloor+1,\quad\textrm{or}\quad
q^{m}\geq\frac{q^{r}-1}{q-1}\cdot\left(g-\left\lfloor\frac{h-2}{r}\right\rfloor-1\right).$
(6)

For the case $h=2$ and arbitrary $m$ and $r$ (recall that $m\geq r$), we have
the tighter bound

$g\leq\left\lfloor(q-1)\cdot\frac{q^{m}+1}{q^{r}-1}\right\rfloor,\quad\textrm{or}\quad
q^{m}\geq\frac{q^{r}-1}{q-1}\cdot g-1,$ (7)

and if, furthermore, $r$ divides $m$ and $r\geq 2$, then (7) implies the bound

$g\leq(q-1)\cdot\frac{(q^{m}-1)}{q^{r}-1},\quad\textrm{or}\quad
q^{m}\geq\frac{q^{r}-1}{q-1}\cdot g+1.$ (8)

Finally, for the case $m=r$ and arbitrary $g$, we have the bound

$g\leq\left\lfloor\frac{h-2}{r}\right\rfloor+q+1,\quad\textrm{or}\quad q\geq
g-\left\lfloor\frac{h-2}{r}\right\rfloor-1.$ (9)

Similarly in the PMDS literature, the following bounds were proven in [18, Th.
3.5 and 3.8].

######  Proposition 16 ([18]).

Let $\mathcal{C}\subseteq\mathbb{F}_{q^{m}}^{n}$ be a PMDS code as in
Definition 11, with $(r,\delta)$-localities, $g$ local sets and
$h=gr-\dim(\mathcal{C})$. If $\delta+1\leq h\leq g$, then

$q^{m}\geq\left\lfloor\frac{g}{h^{2}}\right\rfloor\cdot{r+\delta-1\choose\delta}-1\geq\left\lfloor\frac{g}{h^{2}}\right\rfloor\cdot\left(\frac{r+\delta-1}{\delta}\right)^{\delta}-1,$
(10)

and if $h<\delta+1$ and $h\leq g$, then

$q^{m}\geq\left\lfloor\frac{g}{h^{2}}\right\rfloor\cdot{r+h-2\choose
h-1}-1\geq\left\lfloor\frac{g}{h^{2}}\right\rfloor\cdot\left(\frac{r+h-2}{h-1}\right)^{h-1}-1.$
(11)

Note that the lower bounds in Proposition 16, when setting $\delta=1$, are
smaller than those in Proposition 15. This makes sense as MSRD codes can be
seen as a subfamily of PMDS codes by setting $\delta=1$ (see Subsection 2.3).

##  3 Extended Moore matrices

This section contains the main method for constructing parity-check matrices
of MSRD codes. The section concludes with a definition of a general family of
MSRD codes (Definition 32). Such codes exist and are explicit as long as
certain sequence $\left(\beta_{1},\beta_{2},\ldots,\beta_{\mu
r}\right)\in\mathbb{F}_{q^{m}}^{\mu r}$ is known. Explicit constructions of
such sequences will be deferred to Section 4.

###  3.1 The definitions

Throughout this subsection, we define the field automorphism

$\begin{array}[]{rcl}\sigma:\mathbb{F}_{q^{m}}&\longrightarrow&\mathbb{F}_{q^{m}}\\\
a&\mapsto&a^{q}.\end{array}$

We now define the conjugacy relation. The following definition is a particular
case of [26, Eq. (2.5)], but already appeared in [25].

######  Definition 17 (Conjugacy [25, 26]).

We say that $a,b\in\mathbb{F}_{q^{m}}$ are conjugate in $\mathbb{F}_{q^{m}}$
with respect to $\sigma$ if there exists $c\in\mathbb{F}_{q^{m}}^{*}$ such
that $b=\sigma(c)c^{-1}a=c^{q-1}a$.

Conjugacy is an equivalence relation, whose classes are called conjugacy
classes. It was shown in [28, Cor. 1] that there are exactly $q-1$ non-zero
conjugacy classes in $\mathbb{F}_{q^{m}}$ with respect to $\sigma$, each of
size $(q^{m}-1)/(q-1)$. Furthermore, they are represented by consecutive
powers of a primitive element of $\mathbb{F}_{q^{m}}$, as observed in the
paragraph after [36, Def. 2].

######  Lemma 18 ([28, 36]).

Let $\gamma\in\mathbb{F}_{q^{m}}^{*}$ be a primitive element of
$\mathbb{F}_{q^{m}}$. Then $\gamma^{0},\gamma^{1},\ldots,\gamma^{q-2}$ are
pair-wise non-conjugate and represent the $q-1$ distinct non-zero conjugacy
classes in $\mathbb{F}_{q^{m}}$ with respect to $\sigma$.

Recently, it was shown in [34, Remark 27] that in some cases we may take the
elements in $\mathbb{F}_{q}^{*}$ as the $q-1$ representatives of the conjugacy
classes in $\mathbb{F}_{q^{m}}$ with respect to $\sigma$.

######  Lemma 19 ([34]).

The $q-1$ elements in $\mathbb{F}_{q}^{*}$ are pair-wise non-conjugate in
$\mathbb{F}_{q^{m}}$ with respect to $\sigma$ if, and only if, $q-1$ and
$(q^{m}-1)/(q-1)$ are coprime.

We now turn to extended Moore matrices. We start by defining truncated norms.
Again, the following definition is a particular case of [26, Eq. (2.3)], but
already appeared in [25].

######  Definition 20 (Truncated norms [25, 26]).

Fix $a\in\mathbb{F}_{q^{m}}$. We define its $i$th truncated norm as

$N_{i}(a)=\sigma^{i-1}(a)\cdots\sigma(a)a=a^{\frac{q^{i}-1}{q-1}},$

for all $i\in\mathbb{N}$. Note that if $a\in\mathbb{F}_{q}$, then
$N_{i}(a)=a^{i}$, for all $i\in\mathbb{N}$.

Observe that the map $N_{i}$ depends on $\sigma$, but we do not write this
dependency for simplicity in the notation. We may now define extended Moore
matrices.

######  Definition 21 (Extended Moore matrices).

Let
$\mathbf{a}=(a_{1},a_{2},\ldots,a_{\ell})\in(\mathbb{F}_{q^{m}}^{*})^{\ell}$
be a vector of $\ell$ pair-wise non-conjugate elements in $\mathbb{F}_{q^{m}}$
with respect to $\sigma$. Let
$\boldsymbol{\beta}_{i}=(\beta_{i,1},\beta_{i,2},\ldots,\beta_{i,\eta_{i}})\in\mathbb{F}_{q^{m}}^{\eta_{i}}$
be an arbitrary vector, for some positive integer $\eta_{i}$, for
$i=1,2,\ldots,\ell$. Define
$\boldsymbol{\beta}=(\boldsymbol{\beta}_{1},\boldsymbol{\beta}_{2},\ldots,\boldsymbol{\beta}_{\ell})\in\mathbb{F}_{q^{m}}^{N}$,
where $N=\eta_{1}+\eta_{2}+\cdots+\eta_{\ell}$. For $h=1,2,\ldots,N$, we
define the extended Moore matrix
$M_{h}(\mathbf{a},\boldsymbol{\beta})\in\mathbb{F}_{q^{m}}^{h\times N}$ by

$M_{h}(\mathbf{a},\boldsymbol{\beta})=\left(\begin{array}[]{lll|c|lll}\beta_{1,1}&\ldots&\beta_{1,\eta_{1}}&\ldots&\beta_{\ell,1}&\ldots&\beta_{\ell,\eta_{\ell}}\\\
\beta_{1,1}^{q}a_{1}&\ldots&\beta_{1,\eta_{1}}^{q}a_{1}&\ldots&\beta_{\ell,1}^{q}a_{\ell}&\ldots&\beta_{\ell,\eta_{\ell}}^{q}a_{\ell}\\\
\beta_{1,1}^{q^{2}}N_{2}(a_{1})&\ldots&\beta_{1,\eta_{1}}^{q^{2}}N_{2}(a_{1})&\ldots&\beta_{\ell,1}^{q^{2}}N_{2}(a_{\ell})&\ldots&\beta_{\ell,\eta_{\ell}}^{q^{2}}N_{2}(a_{\ell})\\\
\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\\
\beta_{1,1}^{q^{h-1}}N_{h-1}(a_{1})&\ldots&\beta_{1,\eta_{1}}^{q^{h-1}}N_{h-1}(a_{1})&\ldots&\beta_{\ell,1}^{q^{h-1}}N_{h-1}(a_{\ell})&\ldots&\beta_{\ell,\eta_{\ell}}^{q^{h-1}}N_{h-1}(a_{\ell})\\\
\end{array}\right).$

Such matrices extend the well known Moore matrices (see [27, Lemma 3.51]) from
one to several conjugacy classes. They extend the matrices in [31, p. 604] in
the sense that the $\eta_{i}$ components of
$\boldsymbol{\beta}_{i}\in\mathbb{F}_{q^{m}}^{\eta_{i}}$ over
$\mathbb{F}_{q^{m}}$ need not be linearly independent over $\mathbb{F}_{q}$,
for $i=1,2,\ldots,\ell$.

The main objective of this manuscript is to turn the matrix
$M_{h}(\mathbf{a},\boldsymbol{\beta})$ into the parity-check matrix of an MSRD
code of length $N$ and dimension $N-h$ (Definition 6). For convenience, we
define MDS matrices and MSRD matrices as follows.

######  Definition 22 (MDS matrices).

If $1\leq h\leq N$, we say that a matrix $M\in\mathbb{F}_{q^{m}}^{h\times N}$
is MDS if any $h$ (distinct) columns of $M$ form an invertible $h\times h$
matrix.

######  Definition 23 (MSRD matrices).

Assume that we partition $N=gr$, for positive integers $g$ and $r$. If $1\leq
h\leq N$, we say that a matrix $M\in\mathbb{F}_{q^{m}}^{h\times N}$ is MSRD
for the length partition $(g,r)$ over the field $\mathbb{F}_{q}$ if

$M\cdot{\rm diag}(A_{1},A_{2},\ldots,A_{g})\in\mathbb{F}_{q^{m}}^{h\times N}$

is an MDS matrix, for all matrices $A_{i}\in{\rm GL}_{r}(\mathbb{F}_{q})$, for
$i=1,2,\ldots,g$.

By Lemma 3, an MDS matrix is nothing but the parity-check matrix of a linear
MDS code. By Proposition 5, an MSRD matrix is nothing but the parity-check
matrix of a linear MSRD code.

Our strategy to characterize MSRD extended Moore matrices will follow two
steps. First, we characterize when extended Moore matrices are MDS. Second, we
characterize when an MDS extended Moore matrix remains an MDS matrix after
multiplication on the right by an appropriate block-diagonal matrix.

###  3.2 MDS extended Moore matrices

In this subsection, we characterise when an extended Moore matrix (Definition
21) is an MDS matrix (Definition 22).

We will need the concept of $h$-wise independence, introduced in [16, Def. 9].

######  Definition 24 ($h$-wise independence [16]).

We say that a subset $T\subseteq\mathbb{F}_{q^{m}}$ is $h$-wise independent
over $\mathbb{F}_{q}$ if any subset of at most $h$ (distinct) elements of $T$
is linearly independent over $\mathbb{F}_{q}$. Analogously, for a positive
integer $\eta$, we say that a vector
$\boldsymbol{\beta}=(\beta_{1},\beta_{2},\ldots,\beta_{\eta})\in\mathbb{F}_{q^{m}}^{\eta}$
is $h$-wise independent if $T=\\{\beta_{1},\beta_{2},\ldots,\beta_{\eta}\\}$
has size $\eta$ and is $h$-wise independent.

Note that the size of $T$ in Definition 24 is not restricted. For $|T|\leq h$,
$T$ is $h$-wise independent over $\mathbb{F}_{q}$ if, and only if, $T$ is
linearly independent over $\mathbb{F}_{q}$.

We will also need the following four auxiliary lemmas. The first of these is
immediate from the $\mathbb{F}_{q}$-linearity of $\sigma$.

######  Lemma 25.

Fix integers $1\leq\eta\leq h$ and an element $a\in\mathbb{F}_{q^{m}}^{*}$.
Assume that there exist
$\lambda_{1},\lambda_{2},\ldots,\lambda_{\eta}\in\mathbb{F}_{q}$ such that
$\lambda_{1}\beta_{1}+\lambda_{2}\beta_{2}+\cdots+\lambda_{\eta}\beta_{\eta}=0$,
for elements $\beta_{1},\beta_{2},\ldots,\beta_{\eta}\in\mathbb{F}_{q^{m}}$.
Then it holds that

$\left(\begin{array}[]{llll}\beta_{1}&\beta_{2}&\ldots&\beta_{\eta}\\\
\beta_{1}^{q}a&\beta_{2}^{q}a&\ldots&\beta_{\eta}^{q}a\\\
\beta_{1}^{q^{2}}N_{2}(a)&\beta_{2}^{q^{2}}N_{2}(a)&\ldots&\beta_{\eta}^{q^{2}}N_{2}(a)\\\
\vdots&\vdots&\ddots&\vdots\\\
\beta_{1}^{q^{h-1}}N_{h-1}(a)&\beta_{2}^{q^{h-1}}N_{h-1}(a)&\ldots&\beta_{\eta}^{q^{h-1}}N_{h-1}(a)\\\
\end{array}\right)\left(\begin{array}[]{c}\lambda_{1}\\\ \lambda_{2}\\\
\vdots\\\ \lambda_{\eta}\end{array}\right)=\mathbf{0}.$

The next lemma follows immediately from the invertibility of Moore matrices
[27, Lemma 3.51] and Lemma 25.

######  Lemma 26.

Fix integers $1\leq\eta\leq h$ and an element $a\in\mathbb{F}_{q^{m}}^{*}$.
The dimension of the $\mathbb{F}_{q}$-linear subspace generated by the
elements $\beta_{1},\beta_{2},\ldots,\beta_{\eta}\in\mathbb{F}_{q^{m}}$ equals
the rank of the matrix

$\left(\begin{array}[]{llll}\beta_{1}&\beta_{2}&\ldots&\beta_{\eta}\\\
\beta_{1}^{q}a&\beta_{2}^{q}a&\ldots&\beta_{\eta}^{q}a\\\
\beta_{1}^{q^{2}}N_{2}(a)&\beta_{2}^{q^{2}}N_{2}(a)&\ldots&\beta_{\eta}^{q^{2}}N_{2}(a)\\\
\vdots&\vdots&\ddots&\vdots\\\
\beta_{1}^{q^{h-1}}N_{h-1}(a)&\beta_{2}^{q^{h-1}}N_{h-1}(a)&\ldots&\beta_{\eta}^{q^{h-1}}N_{h-1}(a)\\\
\end{array}\right)\in\mathbb{F}_{q^{m}}^{h\times\eta}.$

The next lemma may be easily derived by simplifying telescopic products (see
[31, Lemma 24] for more general formulations).

######  Lemma 27.

With notation and assumptions as in Definition 21, it holds that

$M_{h}(\mathbf{a},\boldsymbol{\beta})\cdot{\rm
diag}\left(\beta_{1,1}^{-1},\ldots,\beta_{1,\eta_{1}}^{-1}|\ldots|\beta_{\ell,1}^{-1},\ldots,\beta_{\ell,\eta_{\ell}}^{-1}\right)=$
$\left(\begin{array}[]{lll|c|lll}1&\ldots&1&\ldots&1&\ldots&1\\\
\beta_{1,1}^{q-1}a_{1}&\ldots&\beta_{1,\eta_{1}}^{q-1}a_{1}&\ldots&\beta_{\ell,1}^{q-1}a_{\ell}&\ldots&\beta_{\ell,\eta_{\ell}}^{q-1}a_{\ell}\\\
N_{2}(\beta_{1,1}^{q-1}a_{1})&\ldots&N_{2}(\beta_{1,\eta_{1}}^{q-1}a_{1})&\ldots&N_{2}(\beta_{\ell,1}^{q-1}a_{\ell})&\ldots&N_{2}(\beta_{\ell,\eta_{\ell}}^{q-1}a_{\ell})\\\
\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\\
N_{h-1}(\beta_{1,1}^{q-1}a_{1})&\ldots&N_{h-1}(\beta_{1,\eta_{1}}^{q-1}a_{1})&\ldots&N_{h-1}(\beta_{\ell,1}^{q-1}a_{\ell})&\ldots&N_{h-1}(\beta_{\ell,\eta_{\ell}}^{q-1}a_{\ell})\\\
\end{array}\right).$

The next lemma is a particular case of [25, Th. 23 (1)].

######  Lemma 28 ([25]).

Let the notation and assumptions be as in Definition 21, and further assume
that $h=N=\eta_{1}+\eta_{2}+\cdots+\eta_{\ell}$. Then it holds that

${\rm Rk}\left(\begin{array}[]{lll|c|lll}1&\ldots&1&\ldots&1&\ldots&1\\\
\beta_{1,1}^{q-1}a_{1}&\ldots&\beta_{1,\eta_{1}}^{q-1}a_{1}&\ldots&\beta_{\ell,1}^{q-1}a_{\ell}&\ldots&\beta_{\ell,\eta_{\ell}}^{q-1}a_{\ell}\\\
N_{2}(\beta_{1,1}^{q-1}a_{1})&\ldots&N_{2}(\beta_{1,\eta_{1}}^{q-1}a_{1})&\ldots&N_{2}(\beta_{\ell,1}^{q-1}a_{\ell})&\ldots&N_{2}(\beta_{\ell,\eta_{\ell}}^{q-1}a_{\ell})\\\
\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\\
N_{h-1}(\beta_{1,1}^{q-1}a_{1})&\ldots&N_{h-1}(\beta_{1,\eta_{1}}^{q-1}a_{1})&\ldots&N_{h-1}(\beta_{\ell,1}^{q-1}a_{\ell})&\ldots&N_{h-1}(\beta_{\ell,\eta_{\ell}}^{q-1}a_{\ell})\\\
\end{array}\right)=$ $\sum_{i=1}^{\ell}{\rm
Rk}\left(\begin{array}[]{llll}1&1&\ldots&1\\\
\beta_{i,1}^{q-1}a_{i}&\beta_{i,2}^{q-1}a_{i}&\ldots&\beta_{i,\eta_{i}}^{q-1}a_{i}\\\
N_{2}(\beta_{i,1}^{q-1}a_{i})&N_{2}(\beta_{i,2}^{q-1}a_{i})&\ldots&N_{2}(\beta_{i,\eta_{i}}^{q-1}a_{i})\\\
\vdots&\vdots&\ddots&\vdots\\\
N_{h-1}(\beta_{i,1}^{q-1}a_{i})&N_{h-1}(\beta_{i,2}^{q-1}a_{i})&\ldots&N_{h-1}(\beta_{i,\eta_{i}}^{q-1}a_{i})\end{array}\right).$

The main result of this subsection is the following theorem.

######  Theorem 1.

Let the notation and assumptions be as in Definition 21. For $h=1,2,\ldots,N$,
the extended Moore matrix
$M_{h}(\mathbf{a},\boldsymbol{\beta})\in\mathbb{F}_{q^{m}}^{h\times N}$ is MDS
if, and only if, the vector $\boldsymbol{\beta}_{i}=(\beta_{i,1},\beta_{i,2},$
$\ldots,$ $\beta_{i,\eta_{i}})\in\mathbb{F}_{q^{m}}^{\eta_{i}}$ is $h$-wise
independent over $\mathbb{F}_{q}$, for all $i=1,2,\ldots,\ell$.

###### Proof.

First, assume that $(\beta_{i,1},\beta_{i,2},\ldots,\beta_{i,\eta_{i}})$ is
not $h$-wise independent over $\mathbb{F}_{q}$, for some $i=1,2,\ldots,\ell$.
Then $M_{h}(\mathbf{a},\boldsymbol{\beta})$ contains an $h\times h$ submatrix
that is not invertible by Lemma 25.

Conversely, assume that $(\beta_{i,1},\beta_{i,2},$ $\ldots,$
$\beta_{i,\eta_{i}})$ is $h$-wise independent over $\mathbb{F}_{q}$, for
$i=1,2,\ldots,\ell$. Take an arbitrary $h\times h$ submatrix
$M^{\prime}\in\mathbb{F}_{q^{m}}^{h\times h}$ of
$M_{h}(\mathbf{a},\boldsymbol{\beta})$, and let
$0\leq\eta^{\prime}_{i}\leq\min\\{h,\eta_{i}\\}$ be the number of columns from
the $i$th block of $\eta_{i}$ columns in
$M_{h}(\mathbf{a},\boldsymbol{\beta})$ appearing in $M^{\prime}$, for
$i=1,2,\ldots,\ell$. Note that
$h=\eta^{\prime}_{1}+\eta^{\prime}_{2}+\cdots+\eta^{\prime}_{\ell}$. Since
$(\beta_{i,1},\beta_{i,2},$ $\ldots,$ $\beta_{i,\eta_{i}})$ is $h$-wise
independent over $\mathbb{F}_{q}$ and $\eta^{\prime}_{i}\leq h$, then the
$i$th block of $\eta^{\prime}_{i}$ columns in $M^{\prime}$ forms an
$\eta^{\prime}_{i}\times h$ matrix of full rank $\eta^{\prime}_{i}$ by Lemma
26, for $i=1,2,\ldots,\ell$. Finally, by combining Lemmas 27 and 28, we
conclude that

${\rm
Rk}(M^{\prime})=\eta^{\prime}_{1}+\eta^{\prime}_{2}+\cdots+\eta^{\prime}_{\ell}=h,$

and therefore $M^{\prime}\in\mathbb{F}_{q^{m}}^{h\times h}$ is invertible.
Hence $M_{h}(\mathbf{a},\boldsymbol{\beta})$ is MDS and we are done. ∎

###  3.3 MSRD extended Moore matrices

In this subsection, we characterise when an extended Moore matrix (Definition
21) is an MSRD matrix (Definition 23).

The first characterization is simply combining Proposition 5 with Theorem 1
and the $\mathbb{F}_{q}$-linearity of the map $\sigma$.

######  Proposition 29.

Let the notation and assumptions be as in Definition 21. Further assume that
$\eta_{1}=\eta_{2}=\ldots=\eta_{\ell}=\mu r$, for positive integers $\mu$ and
$r$. Hence $N=gr$, for $g=\ell\mu$. For $h=1,2,\ldots,N$, the extended Moore
matrix $M_{h}(\mathbf{a},\boldsymbol{\beta})\in\mathbb{F}_{q^{m}}^{h\times N}$
is MSRD for the length partition $(g,r)$ over $\mathbb{F}_{q}$ if, and only
if, the vector $(\beta_{i,1}^{\prime},\beta_{i,2}^{\prime},$ $\ldots,$
$\beta_{i,\mu r}^{\prime})$ is $h$-wise independent over $\mathbb{F}_{q}$,
where

$(\beta_{i,1}^{\prime},\beta_{i,2}^{\prime},\ldots,\beta_{i,\mu
r}^{\prime})=(\beta_{i,1},\beta_{i,2},\ldots,\beta_{i,\mu r})\cdot{\rm
diag}(A_{i,1},A_{i,2},\ldots,A_{i,\mu})\in\mathbb{F}_{q^{m}}^{\mu r},$

for all matrices $A_{i,1},A_{i,2},\ldots,A_{i,\mu}\in{\rm
GL}_{r}(\mathbb{F}_{q})$, for all $i=1,2,\ldots,\ell$.

The main result of this subsection is the following theorem.

######  Theorem 2.

Let the notation and assumptions be as in Proposition 29. Assume that
$\boldsymbol{\beta}_{1}=\boldsymbol{\beta}_{2}=\ldots=\boldsymbol{\beta}_{\ell}=(\beta_{1},\beta_{2},\ldots,\beta_{\mu
r})\in\mathbb{F}_{q^{m}}^{\mu r}$, and define the $\mathbb{F}_{q}$-linear
subspace

$\mathcal{H}_{i}=\left\langle\beta_{(i-1)r+1},\beta_{(i-1)r+2},\ldots,\beta_{ir}\right\rangle_{\mathbb{F}_{q}}\subseteq\mathbb{F}_{q^{m}},$
(12)

for $i=1,2,\ldots,\mu$. Then the extended Moore matrix
$M_{h}(\mathbf{a},\boldsymbol{\beta})\in\mathbb{F}_{q^{m}}^{h\times N}$ is
MSRD for the length partition $(g,r)$ over $\mathbb{F}_{q}$ if, and only if,
the following two conditions hold for all $i=1,2,\ldots,\mu$:

  1. 1.

$\dim_{\mathbb{F}_{q}}(\mathcal{H}_{i})=r$, i.e.,
$\beta_{(i-1)r+1},\beta_{(i-1)r+2},\ldots,\beta_{ir}$ are linearly independent
over $\mathbb{F}_{q}$, and

  2. 2.

$\mathcal{H}_{i}\cap\left(\sum_{j\in\Gamma}\mathcal{H}_{j}\right)=\\{0\\}$,
for any set $\Gamma\subseteq[\mu]$, such that $i\notin\Gamma$ and
$|\Gamma|\leq\min\\{h,\mu\\}-1$.

###### Proof.

We prove both implications separately.

$\Longleftarrow$): Take matrices $A_{1},A_{2},\ldots,A_{\mu}\in{\rm
GL}_{r}(\mathbb{F}_{q})$. Condition 1 implies that
$\beta^{\prime}_{(i-1)r+1},\beta^{\prime}_{(i-1)r+2},$ $\ldots,$
$\beta^{\prime}_{ir}$ $\in\mathbb{F}_{q^{m}}$ are linearly independent over
$\mathbb{F}_{q}$, where

$(\beta^{\prime}_{(i-1)r+1},\beta^{\prime}_{(i-1)r+2},\ldots,\beta^{\prime}_{ir})=(\beta_{(i-1)r+1},\beta_{(i-1)r+2},\ldots,\beta_{ir})\cdot
A_{i}\in\mathbb{F}_{q^{m}}^{r},$

for all $i=1,2,\ldots,\mu$. Next, fix an index $i=1,2,\ldots,\mu$, and take a
subset $\Gamma\subseteq[\mu]$, such that $i\notin\Gamma$ and
$|\Gamma|\leq\min\\{h,\mu\\}-1$. Condition 2 and the $\mathbb{F}_{q}$-linear
independence of each set
$\\{\beta^{\prime}_{(j-1)r+1},\beta^{\prime}_{(j-1)r+2},$ $\ldots,$
$\beta^{\prime}_{jr}\\}$ imply that the set

$\bigcup_{j\in\Gamma\cup\\{i\\}}\left\\{\beta^{\prime}_{(j-1)r+1},\beta^{\prime}_{(j-1)r+2},\ldots,\beta^{\prime}_{jr}\right\\}\subseteq\mathbb{F}_{q^{m}}$
(13)

is linearly independent over $\mathbb{F}_{q}$. Since every subset of size at
most $h$ of
$\\{\beta^{\prime}_{1},\beta^{\prime}_{2},\ldots,\beta^{\prime}_{\mu r}\\}$ is
contained in a set of the form (13), we deduce that the vector
$(\beta^{\prime}_{1},\beta^{\prime}_{2},\ldots,\beta^{\prime}_{\mu r})$ is
$h$-wise linearly independent over $\mathbb{F}_{q}$. Hence the extended Moore
matrix $M_{h}(\mathbf{a},\boldsymbol{\beta})\in\mathbb{F}_{q^{m}}^{h\times N}$
is MSRD by Proposition 29.

$\Longrightarrow$): Assume first that Condition 1 does not hold for some
$i=1,2,\ldots,\mu$. Without loss of generality, we may assume that there exist
$\lambda_{1},\lambda_{2},\ldots,\lambda_{r-1}\in\mathbb{F}_{q}$ such that

$\sum_{j=1}^{r-1}\lambda_{j}\beta_{(i-1)r+j}+\beta_{ir}=0.$

Thus if we define the invertible matrix

$A_{i}=\left(\begin{array}[]{c|c}I_{r-1}&\begin{array}[]{c}\lambda_{1}\\\
\vdots\\\ \lambda_{r-1}\end{array}\\\
\hline\cr\begin{array}[]{ccc}0&\ldots&0\end{array}&1\end{array}\right)\in{\rm
GL}_{r}(\mathbb{F}_{q}),$

where $I_{r-1}\in{\rm GL}_{r-1}(\mathbb{F}_{q})$ denotes the
$(r-1)\times(r-1)$ identity matrix, then it holds that

$(\beta_{(i-1)r+1},\ldots,\beta_{ir-1},\beta_{ir})\cdot
A_{i}=(\beta_{(i-1)r+1},\ldots,\beta_{ir-1},0).$

Clearly, $(\beta_{(i-1)r+1},\ldots,\beta_{ir-1},0)\in\mathbb{F}_{q^{m}}^{r}$
is not $h$-wise independent, thus $M_{h}(\mathbf{a},\boldsymbol{\beta})$ is
not MSRD by Proposition 29.

Next, assume that Condition 2 does not hold for some $i=1,2,\ldots,\mu$. Then
we may assume, without loss of generality, that there exists a subset
$\Gamma\subseteq[\mu]$ such that $i\in\Gamma$, $|\Gamma|\leq h$, and there
exist $\lambda_{j,u}\in\mathbb{F}_{q}$, for $u=1,2,\ldots,r$, for
$j\in\Gamma$, such that $\lambda_{j,r}=1$, for $j\in\Gamma$, and

$\sum_{j\in\Gamma}\sum_{u=1}^{r}\lambda_{j,u}\beta_{(j-1)r+u}=0.$

Define, for each $j\in\Gamma$, the invertible matrix

$A_{j}=\left(\begin{array}[]{c|c}I_{r-1}&\begin{array}[]{c}\lambda_{j,1}\\\
\vdots\\\ \lambda_{j,r-1}\end{array}\\\
\hline\cr\begin{array}[]{ccc}0&\ldots&0\end{array}&1\end{array}\right)\in{\rm
GL}_{r}(\mathbb{F}_{q}),$

and define, for convenience, $A_{j}=I_{r}\in{\rm GL}_{r}(\mathbb{F}_{q})$ if
$j\notin\Gamma$. If we set

$(\beta^{\prime}_{1},\beta^{\prime}_{2},\ldots,\beta^{\prime}_{\mu
r})=(\beta_{1},\beta_{2},\ldots,\beta_{\mu r})\cdot{\rm
diag}(A_{1},A_{2},\ldots,A_{\mu}),$

then it holds that

$\sum_{j\in\Gamma}\beta^{\prime}_{jr}=\sum_{j\in\Gamma}\sum_{u=1}^{r}\lambda_{j,u}\beta_{(j-1)r+u}=0.$

Since $|\Gamma|\leq h$, then the vector
$(\beta^{\prime}_{1},\beta^{\prime}_{2},\ldots,\beta^{\prime}_{\mu r})$ is not
$h$-wise independent over $\mathbb{F}_{q}$, hence
$M_{h}(\mathbf{a},\boldsymbol{\beta})$ is not MSRD by Proposition 29. ∎

######  Remark 30.

Observe that, in the case $2=h\leq\mu$, Conditions 1 and 2 in Theorem 2 are
equivalent to the set
$\\{\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{\mu}\\}$ being a
partial spread of size $\mu$ of $r$-dimensional subspaces of
$\mathbb{F}_{q^{m}}\cong\mathbb{F}_{q}^{m}$. In Subsection 4.5, we describe
this case in more detail. General sets of vector spaces satisfying Conditions
1 and 2 in Theorem 2 constitute therefore a natural generalization of the
concept of partial spread.

######  Remark 31.

Observe that Conditions 1 and 2 in Theorem 2, combined, are equivalent to

  1. 1.

$\dim_{\mathbb{F}_{q}}\left(\mathcal{H}_{i}\right)=r$, for $i=1,2,\ldots,\mu$,
and

  2. 2.

$\dim_{\mathbb{F}_{q}}\left(\sum_{i\in\Gamma}\mathcal{H}_{i}\right)=r|\Gamma|=r\min\\{h,\mu\\}$,
for any set $\Gamma\subseteq[\mu]$ of size $|\Gamma|=\min\\{h,\mu\\}$.

In particular, if Conditions 1 and 2 hold, then

$m\geq r\min\\{h,\mu\\},\quad\textrm{or}\quad|\mathbb{F}_{q^{m}}|=q^{m}\geq
q^{r\min\\{h,\mu\\}}.$ (14)

Note that the only additional assumption in Theorem 2 is that
$\boldsymbol{\beta}_{1}=\boldsymbol{\beta}_{2}=\ldots=\boldsymbol{\beta}_{\ell}$.
For different vectors $\boldsymbol{\beta}_{i}$ we still have the same
requirements, including (14).

Hence the field size in (14) is necessary for extended Moore matrices as in
Theorem 2 to be MSRD. However, observe that $q^{m}=q^{r\min\\{h,\mu\\}}$ is
much smaller than the smallest field size required by an MRD code [12, 13, 41]
with base field size $q$, which would be $q^{m}=q^{gr}=q^{\ell\mu r}$ (recall
that $g=\ell\mu$).

In subsections 4.3 and 4.4, we will obtain MSRD extended Moore matrices with
$m=r\min\\{h,\mu\\}$. In that case, we may obtain $m=r$ if, and only if, $h=1$
or $\mu=1$ (as in Subsection 4.3). Recall from Remark 7 that $m\geq r$ is
necessary for MSRD codes to exist. However, in later subsections, we will
obtain field sizes $q^{m}$ which may be larger than $q^{r\min\\{h,\mu\\}}$ but
smaller relative to the parameters $g$ and $r$ (and $\delta$ for PMDS codes).

In conclusion, we have the following general family of MSRD codes.

######  Definition 32.

Let the notation and assumptions be as in Theorem 2. That is, let
$\mathbf{a}=(a_{1},a_{2},\ldots,a_{\ell})\in(\mathbb{F}_{q^{m}}^{*})^{\ell}$
be a vector of $\ell$ pair-wise non-conjugate elements in $\mathbb{F}_{q^{m}}$
with respect to $\sigma$. Let
$\boldsymbol{\beta}_{1}=\boldsymbol{\beta}_{2}=\ldots=\boldsymbol{\beta}_{\ell}=(\beta_{1},\beta_{2},\ldots,\beta_{\mu
r})\in\mathbb{F}_{q^{m}}^{\mu r}$ satisfy Conditions 1 and 2 in Theorem 2. Let
$N=gr$, where $g=\ell\mu$. For $h=1,2,\ldots,N$, we define the following
$k$-dimensional linear MSRD code, where $k=N-h$, for the length partition
$(g,r)$ over the base field $\mathbb{F}_{q}$:

$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})=\left\\{\mathbf{y}\in\mathbb{F}_{q^{m}}^{N}\mid\mathbf{y}M_{h}(\mathbf{a},\boldsymbol{\beta})=\mathbf{0}\right\\}.$

######  Remark 33.

Theorem 2 and the family of MSRD codes in Definition 32 have no meaningful
analogue in the Hamming-metric case ($r=1$) or the rank-metric case ($g=1$).

Setting $r=1$, extended Moore matrices require polynomial field sizes
$q^{m}=q^{\min\\{h,\mu\\}}$ in the code length $g\leq q-1$ (thus worse than
classical Reed-Solomon codes [40]), unless $h=1$ or $\mu=1$. In either of
those cases, we may choose $m=\min\\{h,\mu\\}=1$ and then an extended Moore
matrix is simply a (rectangular) Vandermonde matrix with distinct evaluation
points and possibly with column multipliers. Hence the corresponding MDS codes
in Definition 32 are just generalized Reed-Solomon codes [40].

Setting $g=1$, extended Moore matrices become classical (rectangular) Moore
matrices with possibly $\mathbb{F}_{q}$-linearly dependent evaluation points.
However, by Lemma 26, such rectangular Moore matrices form parity-check
matrices of MRD codes if, and only if, all evaluation points are
$\mathbb{F}_{q}$-linearly independent. Hence the corresponding MRD codes in
Definition 32 are just Gabidulin codes [13, 41].

##  4 Explicit constructions of MSRD codes

What is missing in Definition 32 is finding the sequence
$(\beta_{1},\beta_{2},\ldots,\beta_{\mu r})\in\mathbb{F}_{q^{m}}^{\mu r}$. In
this section, we provide a technique for constructing explicit sequences
$(\beta_{1},\beta_{2},\ldots,\beta_{\mu r})\in\mathbb{F}_{q^{m}}^{\mu r}$
satisfying Conditions 1 and 2 in Theorem 2. This method provides several
explicit subfamilies of the codes in Definition 32, where the vector
$\mathbf{a}\in(\mathbb{F}_{q^{m}}^{*})^{\ell}$ can be explicitly chosen as in
Lemmas 18 or 19.

###  4.1 The technique of tensor products

In this subsection, we explore the method of performing tensor products of
sequences over $\mathbb{F}_{q^{r}}$ and $\mathbb{F}_{q^{m}}$. This technique
is inspired by that used in [14, Sec. IV-B]. However, the codes obtained in
[14, Sec. IV-B] and in this work are not equivalent (by inspecting the
attained parameters).

For the remainder of this section, we will fix an ordered basis
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2},\ldots,\alpha_{r})\in\mathbb{F}_{q^{r}}^{r}$
of $\mathbb{F}_{q^{r}}$ over $\mathbb{F}_{q}$. We will also assume from now on
that $m=r\rho$ (hence $\mathbb{F}_{q^{r}}\subseteq\mathbb{F}_{q^{m}}$), for
some positive integer $\rho$. Choose a vector

$\boldsymbol{\gamma}=(\gamma_{1},\gamma_{2},\ldots,\gamma_{\mu})\in\mathbb{F}_{q^{m}}^{\mu}.$
(15)

Define the tensor product of $\boldsymbol{\alpha}$ with $\boldsymbol{\gamma}$
as

$(\beta_{1},\beta_{2},\ldots,\beta_{\mu
r})=\boldsymbol{\alpha}\otimes\boldsymbol{\gamma}=(\alpha_{1}\gamma_{1},\ldots,\alpha_{r}\gamma_{1}|\ldots|\alpha_{1}\gamma_{\mu},\ldots,\alpha_{r}\gamma_{\mu})\in\mathbb{F}_{q^{m}}^{\mu
r}.$ (16)

In other words, for $i=1,2,\ldots,\mu$, we define

$(\beta_{(i-1)r+1},\beta_{(i-1)r+2},\ldots,\beta_{ir})=\boldsymbol{\alpha}\gamma_{i}=(\alpha_{1}\gamma_{i},\alpha_{2}\gamma_{i},\ldots,\alpha_{r}\gamma_{i})\in\mathbb{F}_{q^{m}}^{r}.$

The main result of this section is the following theorem. The proof is
straightforward and is left to the reader.

######  Theorem 3.

The vector $(\beta_{1},\beta_{2},\ldots,\beta_{\mu
r})\in\mathbb{F}_{q^{m}}^{\mu r}$ in (16) satisfies Conditions 1 and 2 in
Theorem 2, for $i=1,2,\ldots,\mu$, if and only if, the vector
$\boldsymbol{\gamma}=(\gamma_{1},\gamma_{2},\ldots,\gamma_{\mu})\in\mathbb{F}_{q^{m}}^{\mu}=\mathbb{F}_{q^{r\rho}}^{\mu}$
is $t$-wise independent over $\mathbb{F}_{q^{r}}$, for $t=\min\\{h,\mu\\}$.

######  Remark 34.

Observe that, if $\rho\geq\mu$, then we may simply choose
$\boldsymbol{\gamma}=(\gamma_{1},\gamma_{2},\ldots,\gamma_{\mu})\in\mathbb{F}_{q^{m}}^{\mu}$
in Theorem 3 such that $\gamma_{1},\gamma_{2},\ldots,\gamma_{\mu}$ are
linearly independent over $\mathbb{F}_{q^{r}}$. However, in that case,
$m=r\rho\geq r\mu$, and we do not gain anything by considering $\rho>\mu$.
Hence, we may focus only on the case $\rho\leq\mu$.

In other words, we only need to focus on constructing a vector
$\boldsymbol{\gamma}\in\mathbb{F}_{q^{m}}^{\mu}$ that is $t$-wise independent
over $\mathbb{F}_{q^{r}}$, and only in the case $\rho\leq\mu$, where we always
assume that $m=r\rho$. The next subsection provides a coding-theoretic method
to construct such vectors.

###  4.2 Minimum Hamming distance means $t$-wise independence

In this subsection, we revisit the equivalence between the concept of $t$-wise
independent set in $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q^{r}}$ and that of
$\mathbb{F}_{q^{r}}$-linear code in $\mathbb{F}_{q^{r}}^{\mu}$ with minimum
Hamming distance larger than $t$. This equivalence has been used previously in
the PMDS literature in [16, Th. 17], [14, Lemma 7] and throughout [19], among
others, but it seems new in the context of MSRD codes.

In view of Remark 34, we will assume from now on that $\rho\leq\mu$. The
following result is immediate from combining Lemma 3, Definition 24 and the
$\mathbb{F}_{q^{r}}$-linearity of the map $M_{\boldsymbol{\delta}}$ given in
(2).

######  Lemma 35.

Let $\boldsymbol{\delta}\in\mathbb{F}_{q^{m}}^{\rho}$ be an ordered basis of
$\mathbb{F}_{q^{m}}=\mathbb{F}_{q^{r\rho}}$ over $\mathbb{F}_{q^{r}}$.
Consider the matrix representation map
$M_{\boldsymbol{\delta}}:\mathbb{F}_{q^{r\rho}}^{\mu}\longrightarrow\mathbb{F}_{q^{r}}^{\rho\times\mu}$,
as in (2), and define

$H_{\boldsymbol{\gamma}}=M_{\boldsymbol{\delta}}(\boldsymbol{\gamma})\in\mathbb{F}_{q^{r}}^{\rho\times\mu}.$
(17)

The vector $\boldsymbol{\gamma}\in\mathbb{F}_{q^{m}}^{\mu}$ is $t$-wise
independent over $\mathbb{F}_{q^{r}}$ if, and only if, ${\rm
d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})\geq t+1$, for the
$\mathbb{F}_{q^{r}}$-linear code

$\mathcal{C}_{\boldsymbol{\gamma}}=\left\\{\mathbf{y}\in\mathbb{F}_{q^{r}}^{\mu}\mid\mathbf{y}H_{\boldsymbol{\gamma}}=\mathbf{0}\right\\}\subseteq\mathbb{F}_{q^{r}}^{\mu}.$
(18)

Here, we are considering ${\rm
d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})=\mu+1$ if
$\mathcal{C}_{\boldsymbol{\gamma}}=\\{\mathbf{0}\\}$, which is equivalent to
$t=\rho=\mu$ and $H_{\boldsymbol{\gamma}}\in{\rm
GL}_{\mu}(\mathbb{F}_{q^{r}})$, i.e.,
$\boldsymbol{\gamma}\in\mathbb{F}_{q^{r\mu}}^{\mu}$ is an ordered basis of
$\mathbb{F}_{q^{r\mu}}$ over $\mathbb{F}_{q^{r}}$.

In conclusion, to construct $\boldsymbol{\gamma}\in\mathbb{F}_{q^{r}}^{\mu}$,
we may choose a known Hamming-metric code
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ as in
(18), with code length $\mu$, dimension $\mu-\rho$ and minimum Hamming
distance at least $t+1$. As in related works [14, 16, 19], the field size
$q^{m}=\left(q^{r}\right)^{\rho}$ has as exponent $\rho$ the redundancy (i.e.,
codimension) of the code $\mathcal{C}_{\boldsymbol{\gamma}}$.

Hence, the objective is to use known Hamming-metric codes
$\mathcal{C}_{\boldsymbol{\gamma}}$ over the field $\mathbb{F}_{q^{r}}$ with
minimum Hamming distance larger than $t=\min\\{h,\mu\\}$, with large code
length $\mu$ and small redundancy $\rho$ (i.e., large dimension $\mu-\rho$).

###  4.3 Using trivial codes: Recovering linearized RS codes

As a first choice of $\mathcal{C}_{\boldsymbol{\gamma}}$, we choose a trivial
code $\mathcal{C}_{\boldsymbol{\gamma}}=\\{\mathbf{0}\\}$ and recover duals of
linearized Reed-Solomon codes [31]. As in Lemma 35, we define ${\rm
d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})=\mu+1$ if
$\mathcal{C}_{\boldsymbol{\gamma}}=\\{\mathbf{0}\\}\subseteq\mathbb{F}_{q^{r\mu}}^{\mu}$.

######  Theorem 4.

Choose $\mu=\rho=1$, thus $m=r\rho=r$,
$\boldsymbol{\gamma}=1\in\mathbb{F}_{q^{r}}^{1}$,
$\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}\subseteq\mathbb{F}_{q^{r}}^{1}$,
hence

$(\beta_{1},\beta_{2},\ldots,\beta_{r})=\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2},\ldots,\alpha_{r})\in\mathbb{F}_{q^{r}}^{r}.$

Then the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{r}}^{gr}$
in Definition 32 is the dual of a linearized Reed-Solomon code [31, Def. 31],
[11, Def. 2.6], also called linearized Goppa code in [10]. The redundancy $h$
is arbitrary with $1\leq h\leq gr-1$, and the number of matrix sets $g$ may be
arbitrary satisfying that

$1\leq g=\ell\leq q-1.$

The base field is $\mathbb{F}_{q}$, with $q>g$, and the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has size

$|\mathbb{F}_{q^{m}}|=q^{r},\quad\textrm{that is,}\quad m=r,$ (19)

######  Remark 36.

There is an additive gap of $\lfloor(h-2)/r\rfloor+2$ for the parameter $g$
between the upper bound (9) and the value of $g$ achievable by the MSRD codes
in Theorem 4. If $h\leq r+1$, then (9) reads $q\geq g-1$, and such a gap is
reduced to $2$. Asymptotically, if $h=\mathcal{O}(rq)$, then (9) implies that
$g=\mathcal{O}(q)$ for the case $m=r\geq 2$. In this case, the MSRD codes in
Theorem 4 attain such an asymptotic bound.

By [35, Th. 4], such duals are precisely linearized Reed-Solomon codes for
$\mathbf{a}\in(\mathbb{F}_{q^{r}}^{*})^{\ell}$ chosen as in Lemma 18 (see also
[34, Prop. 38] for other cases, and [10] for a general description). Note that
we have chosen to define the MSRD codes in Definition 32 as those whose
parity-check matrix is an MSRD extended Moore matrix. The MSRD code with such
a matrix as its generator matrix is therefore simply a linearized Reed-Solomon
code, if $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ as in this subsection.

In [31], the vectors $\boldsymbol{\beta}_{i}\in\mathbb{F}_{q^{r}}^{r}$, for
$i=1,2,\ldots,\ell$, were allowed to be different, have lengths smaller than
$r$, and a $\sigma$-derivation was allowed to be used in its generator matrix.
However, such extensions do not provide further parameter regimes for finite
fields (to obtain distinct lengths $r_{i}\leq r$ per block, we may simply use
puncturing, see Remark 8).

Linearized Reed-Solomon codes were proposed as PMDS codes, via Construction 1,
originally in [36]. As stated there, the field sizes attainable by such codes
are

$|\mathbb{F}_{q^{m}}|=q^{r}=(g+1)^{r},$ (20)

for $g=q-1$ local sets, and locality $r$ (Definition 10), assuming that
$q\geq\nu=r+\delta-1$ if $\delta>2$. If we do not wish $g+1$ to be a prime
power, but $q$ is even, then we may guarantee the field size

$|\mathbb{F}_{q^{m}}|=q^{r}\leq\left(2\max\\{\nu,g\\}\right)^{r},$ (21)

by choosing $q$ to be the smallest power of $2$ larger than $\max\\{\nu,g\\}$.

We obtain the same MSRD codes if we choose, more generally, the trivial code
$\mathcal{C}_{\boldsymbol{\gamma}}=\\{\mathbf{0}\\}\subseteq\mathbb{F}_{q^{r}}^{\mu}$,
i.e., $\rho=\mu\geq 1$ and $H_{\boldsymbol{\gamma}}\in{\rm
GL}_{\rho}(\mathbb{F}_{q^{r}})$. In other words, if we choose
$\boldsymbol{\gamma}\in\mathbb{F}_{q^{r\rho}}^{\rho}$ to be an ordered basis
of $\mathbb{F}_{q^{r\rho}}$ over $\mathbb{F}_{q^{r}}$. As is well known, the
tensor product

$(\beta_{1},\beta_{2},\ldots,\beta_{r\rho})=\boldsymbol{\alpha}\otimes\boldsymbol{\gamma}=(\alpha_{1}\gamma_{1},\ldots,\alpha_{r}\gamma_{1}|\ldots|\alpha_{1}\gamma_{\rho},\ldots,\alpha_{r}\gamma_{\rho})\in\mathbb{F}_{q^{r\rho}}^{r\rho}$

is in turn an ordered basis of $\mathbb{F}_{q^{r\rho}}$ over $\mathbb{F}_{q}$.
This is the classical proof that, given finite-dimensional field extensions
$K_{1}\subseteq K_{2}\subseteq K_{3}$, then
$[K_{3}:K_{1}]=[K_{3}:K_{2}]\cdot[K_{2}:K_{1}]$. Thus, we obtain duals of
linearized Reed-Solomon codes, as before, but with length $\ell(r\rho)$, for
the length partition $(\ell,r\rho)$ over the field $\mathbb{F}_{q}$, which
does not add anything, as we may choose $r\rho$ instead of $r$ from the
beginning.

###  4.4 Using MDS codes

In this subsection, we explore the case where
$\mathcal{C}_{\boldsymbol{\gamma}}$ is an MDS code.

######  Theorem 5.

Choose any $\mu\leq q^{r}+1$ and $\rho=t=\min\\{h,\mu\\}$, being $h$ arbitrary
with $1\leq h\leq gr-1$. Choose
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ in (18)
as an MDS code of dimension $\mu-t$, thus ${\rm
d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})=t+1$. For instance,
$\mathcal{C}_{\boldsymbol{\gamma}}$ can be chosen as the projective extension
[23, Th. 5.3.4] of a classical Reed-Solomon code [40]. Then the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
in Definition 32 has $g$ matrix sets satisfying that

$g=\ell\mu\leq(q-1)\left(q^{r}+1\right),$

where $\ell$ and $\mu$ may be arbitrary such that

$1\leq\ell\leq q-1\quad\textrm{and}\quad 1\leq\mu\leq q^{r}+1.$

The base field is $\mathbb{F}_{q}$, with
$q\geq\max\left\\{\ell+1,\sqrt[r]{\mu-1}\right\\}$, and the field of linearity
of $\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has size

$|\mathbb{F}_{q^{m}}|=q^{r\min\\{h,\mu\\}},\quad\textrm{that is,}\quad
m=r\min\\{h,\mu\\}.$ (22)

Choosing $\ell=q-1$ and $\mu=q^{r}+1$, thus
$g=\ell\mu=(q-1)\left(q^{r}+1\right)$, then the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has size

$|\mathbb{F}_{q^{m}}|=\left(\frac{g}{q-1}-1\right)^{\min\left\\{h,\frac{g}{q-1}\right\\}}.$
(23)

The parameters attainable by such codes are similar to those achieved by the
codes in [19, Sec. III]. Although not proven nor remarked in [19], the codes
in [19, Sec. III] are PMDS codes that indeed are built using MSRD codes via
Construction 1. However, for the codes in Theorem 5, $g$ may be up to
$(q-1)\left(q^{r}+1\right)$, while in [19, Sec. III], $g$ may only be up to
$\lceil q^{r}/r\rceil$, being all other parameters equal.

We now plug the MSRD codes from Theorem 5 into Construction 1. The following
corollary holds by Proposition 12 and Theorem 5.

######  Corollary 37.

In Construction 1, choose
$\mathcal{C}_{out}=\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
to be the MSRD code in Theorem 5. Assume that $q$ is even and such that
$\mu\leq q^{r}+1$ and $q>\nu=r+\delta-1$. Furthermore, choose $q$ satisfying
also that, either 1) $\mu=q^{r}+1$, or 2) $q$ the smallest power of $2$
satisfying $q>\nu$. Set $\ell=q-1$ and
$g=\ell\mu\leq(q-1)\left(q^{r}+1\right)$. Then
$\mathcal{C}_{glob}\subseteq\mathbb{F}_{q^{m}}^{g\nu}$ in Construction 1 is a
PMDS code with $(r,\delta)$-localities, and its field of linearity has size

$|\mathbb{F}_{q^{m}}|=q^{r\min\\{h,\mu\\}}\leq\max\left\\{\left(2\nu\right)^{r},\left\lfloor\frac{g}{\nu}\right\rfloor-1\right\\}^{\min\left\\{h,\left\lfloor\frac{g}{\nu}\right\rfloor\right\\}}.$
(24)

###  4.5 Using Hamming codes (or spreads)

We now investigate the case $h=2\leq\mu$ (see Remark 30). As we show next, in
this case we obtain the first and only known MSRD codes with arbitrary
parameters except for $h=2$ (minimum sum-rank distance $3$) and with field
sizes $q^{m}$ that are linear in $g$. In addition, such MSRD codes meet the
bounds (8) with equality, hence $g$ may not be larger relative to $q^{m}$, or
$q^{m}$ smaller relative to $g$, for $h=2$ and arbitrary $q$ and $r$.

As shown in Remark 30, when $h=2\leq\mu$, Conditions 1 and 2 in Theorem 2 hold
if, and only if, the set $\\{\mathcal{H}_{1},\mathcal{H}_{2},\ldots,$
$\mathcal{H}_{\mu}\\}$ is a partial spread of size $\mu$ of $r$-dimensional
$\mathbb{F}_{q}$-linear subspaces of
$\mathbb{F}_{q^{m}}\cong\mathbb{F}_{q}^{m}$. Recall that a partial spread is a
set of $r$-dimensional $\mathbb{F}_{q}$-linear subspaces
$\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{\mu}\subseteq\mathbb{F}_{q^{m}}$
such that

$\mathcal{H}_{i}\cap\mathcal{H}_{j}=\\{0\\}$

if $i\neq j$. In the case $m=r\rho$, which we are assuming in this section,
there exist partial spreads of maximum possible size $\mu$ whose union form
the total space $\mathbb{F}_{q^{m}}$, and are therefore simply called spreads.
The first known construction of spreads when $m=r\rho$ was provided by Segre
[42], and coincides exactly with our tensor-product technique (Subsection 4.1)
when choosing
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ as a
$(\mu-\rho)$-dimensional Hamming code [20] (see also [30, Sec. 1.7 or p. 193]
or [23, Sec. 1.8]).

We thus obtain the following subfamily of MSRD codes from Definition 32.

######  Theorem 6.

Consider $1\leq\rho<\mu$, and choose
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ in (18)
as a $(\mu-\rho)$-dimensional Hamming code. In other words, choose the vector
$\boldsymbol{\gamma}=(\gamma_{1},\gamma_{2},\ldots,\gamma_{\mu})\in\left(\mathbb{F}_{q^{r\rho}}^{*}\right)^{\mu}$
in (15) such that its components form the projective space

$\mathbb{P}_{\mathbb{F}_{q^{r}}}(\mathbb{F}_{q^{r\rho}})=\\{[\gamma_{1}],[\gamma_{2}],\ldots,[\gamma_{\mu}]\\},$

where
$[\gamma]=\\{\lambda\gamma\in\mathbb{F}_{q^{r\rho}}^{*}\mid\lambda\in\mathbb{F}_{q^{r}}^{*}\\}$,
for $\gamma\in\mathbb{F}_{q^{r\rho}}^{*}$. Then we have that

$\mu=\frac{q^{r\rho}-1}{q^{r}-1}\quad\textrm{and}\quad t=h={\rm
d}_{H}\left(\mathcal{C}_{\boldsymbol{\gamma}}\right)-1=2.$

Finally, set $\ell=q-1$ and $g=\ell\mu$. Then the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
in Definition 32 satisfies that ${\rm
d}_{SR}(\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta}))=3$ (i.e., $h=2$) and
has $g$ matrix sets, where

$g=(q-1)\cdot\frac{q^{r\rho}-1}{q^{r}-1}.$

The base field is $\mathbb{F}_{q}$, being $q$ an arbitrary prime power, and
the field of linearity of $\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has
size

$|\mathbb{F}_{q^{m}}|=q^{r\rho}=\frac{q^{r}-1}{q-1}\cdot g+1.$ (25)

In particular, for $r\geq 2$, the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
meets the bounds (8) with equality.

######  Remark 38.

Observe that, setting $\rho=1$, the MSRD codes in Theorem 6 coincide with
those from Theorem 4 for $h=2$. Setting $\rho=2$, the MSRD codes in Theorem 6
coincide with those from Theorem 5 for $h=2$.

######  Remark 39.

Theorem 6 above makes use of partial spreads when $r$ divides $m$. There exist
constructions of partial spreads when $r$ does not divide $m$. Using results
from [1, 2], one may prove that the maximum size $\mu$ of a partial spread of
$r$-dimensional $\mathbb{F}_{q}$-linear subspaces
$\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{\mu}\subseteq\mathbb{F}_{q^{m}}$
satisfies that

$\frac{q^{m}-q^{s}}{q^{r}-1}-q^{s}+1\leq\mu\leq\frac{q^{m}-q^{s}}{q^{r}-1},$

where $s\geq 0$ is the remainder of the Euclidean division of $m$ by $r$.
Choosing $g=(q-1)\mu$, the corresponding MSRD codes in Definition 32 satisfy
that

$(q-1)\cdot\left(\frac{q^{m}-q^{s}}{q^{r}-1}-q^{s}+1\right)\leq
g\leq(q-1)\cdot\frac{q^{m}-q^{s}}{q^{r}-1}.$

We will not provide the corresponding construction of PMDS codes via
Construction 1, as there exist linear PMDS codes for $h=2$ with smaller field
sizes [4].

###  4.6 Using BCH codes

In this subsection, we explore the case where
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ is a BCH
code. Assume in this subsection that $q$ and $\mu$ are coprime. Denote the
order of $q^{r}$ modulo $\mu$ by

$s={\rm
ord}_{\mu}\left(q^{r}\right)=\min\left\\{\widetilde{s}\in\mathbb{Z}_{+}\mid\mu\textrm{
divides }q^{r\widetilde{s}}-1\right\\}.$ (26)

Consider the code
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ in (18)
to be a BCH code, see [30, Sec. 7.6] [23, Sec. 4.5 & Ch. 5]. By the BCH bound
[30, Sec. 7.6, Th. 8] [23, Th. 4.5.3], we have that ${\rm
d}_{H}\left(\mathcal{C}_{\boldsymbol{\gamma}}\right)\geq\partial$ if the
minimal generator polynomial of $\mathcal{C}_{\boldsymbol{\gamma}}$ vanishes
in

$a^{b},a^{b+1},a^{b+2},\ldots,a^{b+\partial-2}\in\mathbb{F}_{q^{rs}},$

for integers $b\geq 0$ and $2\leq\partial\leq n$, where
$a\in\mathbb{F}_{q^{rs}}$ is a primitive root of $x^{\mu}-1$. If we choose
$\mathcal{C}_{\boldsymbol{\gamma}}$ to be the largest BCH code whose minimal
generator polynomial has such roots, then by [23, Th. 4.2.1], we have that

$\rho=\mu-\dim\left(\mathcal{C}_{\boldsymbol{\gamma}}\right)=|C_{b}\cup
C_{b+1}\cup C_{b+2}\cup\ldots\cup C_{b+\partial-2}|,$

where $C_{i}\subseteq\\{0,1,\ldots,\mu-1\\}$ is the $i$th $q^{r}$-cyclotomic
coset modulo $\mu$ [30, Sec. 7.5, p. 197] [23, Sec. 4.1], given by

$C_{i}=\\{i,iq^{r},iq^{2r},iq^{3r},\ldots\\}\quad(\textrm{mod }\mu),$

for $i=0,1,\ldots,\mu-1$. The integer $\partial$ is called the prescribed
distance of the BCH code $\mathcal{C}_{\boldsymbol{\gamma}}$, and the set
$C_{b}\cup C_{b+1}\cup C_{b+2}\cup\ldots\cup C_{b+\partial-2}$ is called the
defining set of $\mathcal{C}_{\boldsymbol{\gamma}}$.

By the discussion above, the following theorem holds.

######  Theorem 7.

As above, assume that $q$ and $\mu$ are coprime, and set $s={\rm
ord}_{\mu}\left(q^{r}\right)$, as in (26). Take a positive integer $b\geq 0$,
and choose the code
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ in (18)
to be a BCH code, as above, with prescribed distance $\partial=t+1$ and
defining set $C_{b}\cup C_{b+1}\cup C_{b+2}\cup\ldots\cup C_{b+t-1}$, being
$h$ arbitrary with $1\leq h\leq gr-1$, and being $t=\min\\{h,\mu\\}$. Then the
MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
in Definition 32 has $g=\ell\mu$ matrix sets, where $\ell$ may be arbitrary
with $1\leq\ell\leq q-1$. The base field is $\mathbb{F}_{q}$, where $q$ is
coprime with $\mu$ and satisfies $q>\ell$, and the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has size

$|\mathbb{F}_{q^{m}}|=q^{r\rho}=\left(q^{r}\right)^{|C_{b}\cup C_{b+1}\cup
C_{b+2}\cup\ldots\cup C_{b+t-1}|},$ (27)

that is, $m=r\cdot|C_{b}\cup C_{b+1}\cup C_{b+2}\cup\ldots\cup C_{b+t-1}|$.

We now upper bound the size of the defining set $C_{b}\cup C_{b+1}\cup
C_{b+2}\cup\ldots\cup C_{b+t-1}$. The following observations are trivial and
well known:

$C_{0}=\\{0\\},\quad|C_{i}|\leq s,\quad\textrm{and}\quad C_{iq^{r}}=C_{i},$
(28)

for $i=0,1,2,\ldots,\mu-1$. Therefore, we take $b=0$, and then we have
$|C_{0}|=1$ and we may remove from $C_{0}\cup C_{1}\cup C_{2}\cup\ldots\cup
C_{t-1}$ each cyclotomic coset $C_{i}$ where $i$ is a multiple of $q^{r}$.
Hence

$|C_{0}\cup C_{1}\cup C_{2}\cup\ldots\cup C_{t-1}|\leq
1+s\cdot\left\lceil\frac{q^{r}-1}{q^{r}}\cdot(t-1)\right\rceil.$ (29)

Therefore, we have proven the following enhancement of Theorem 7.

######  Theorem 8.

Let the assumptions and notation be as in Theorem 7. Assume further that
$b=0$. Then the base field is $\mathbb{F}_{q}$, where $q$ is coprime with
$\mu$ and satisfies $q>\ell$, and the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has size

$|\mathbb{F}_{q^{m}}|=q^{r\rho}\leq\left(q^{r}\right)^{1+s\left\lceil\frac{q^{r}-1}{q^{r}}(\min\\{h,\mu\\}-1)\right\rceil}.$
(30)

We may further choose $\mathcal{C}_{\boldsymbol{\gamma}}$ to be a primitive
BCH code, meaning that we choose $\mu=q^{rs}-1$, where $s$ may be chosen
arbitrary (it then follows that $s={\rm ord}_{\mu}\left(q^{r}\right)$), and
then choose $\ell=q-1$. Then the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})$ has size

$|\mathbb{F}_{q^{m}}|=q^{r\rho}\leq
q^{r}\cdot\left(\frac{g}{q-1}+1\right)^{\left\lceil\frac{q^{r}-1}{q^{r}}(h-1)\right\rceil}.$
(31)

We now plug the MSRD codes from Theorem 8 into Construction 1. The following
corollary holds by Proposition 12 and Theorem 8.

######  Corollary 40.

In Construction 1, choose
$\mathcal{C}_{out}=\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
to be the MSRD code in Theorem 8. We further assume that $\mu=q^{rs}-1$, for
an arbitrary positive integer $s$, and where $q$ is the smallest power of $2$
such that $q>\nu=r+\delta-1$. Set $\ell=q-1$ and
$g=\ell\mu=(q-1)\left(q^{rs}-1\right)$. Then
$\mathcal{C}_{glob}\subseteq\mathbb{F}_{q^{m}}^{g\nu}$ in Construction 1 is a
PMDS code with $(r,\delta)$-localities, and its field of linearity has size

$|\mathbb{F}_{q^{m}}|=q^{r\rho}\leq\left(2\nu\right)^{r}\cdot\left(\left\lfloor\frac{g}{\nu}\right\rfloor+1\right)^{\left\lceil\frac{q^{r}-1}{q^{r}}(h-1)\right\rceil}.$
(32)

The field size (32) is not smaller than that achieved by linearized Reed-
Solomon codes (21) in general if $h>r$. However, if $h\leq r$, then $h\leq
q^{r}$, and observe that

$\textrm{if }h\leq
q^{r},\quad\textrm{then}\quad\left\lceil\frac{q^{r}-1}{q^{r}}(h-1)\right\rceil=h-1.$
(33)

Hence, for the parameter regime in which the field sizes (32) improve (21),
that is, for $h\leq r$, it holds that

$|\mathbb{F}_{q^{m}}|\leq\left(2\nu\right)^{r}\cdot\left(\left\lfloor\frac{g}{\nu}\right\rfloor+1\right)^{\left\lceil\frac{q^{r}-1}{q^{r}}(h-1)\right\rceil}=\left(2\nu\right)^{r}\cdot\left(\left\lfloor\frac{g}{\nu}\right\rfloor+1\right)^{h-1}.$
(34)

###  4.7 Using Algebraic-Geometry (AG) codes

In this subsection, we explore the case where
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ is an
Algebraic-Geometry code, or AG code for short. AG codes have only been
proposed to construct PMDS codes in [19], to the best of our knowledge.
However, it is not clear whether or not the PMDS codes in [19] are built from
or may produce MSRD codes, as the obtained parameters in this work and in [19]
are different.

Before starting, it is important to note that we do not obtain asymptotically
smaller field sizes $q^{m}$ than in previous subsections (neither does [19]).
Perhaps surprisingly, the main disadvantage of using AG codes here is that
they are asymptotically good. Assume that ${\rm
d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})=\Omega(\mu)$, meaning that ${\rm
d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})\geq C\mu$, for some constant $C>0$.
Since $\rho>{\rm d}_{H}(\mathcal{C}_{\boldsymbol{\gamma}})$ by the Singleton
bound (Proposition 1), then

$\rho>C\mu.$

Hence, for the base field $\mathbb{F}_{q}$, we may choose $\mu\leq
g\leq(q-1)\mu$, and the obtained field sizes satisfy

$q^{m}=q^{r\rho}>\left(q^{r}\right)^{C\mu}\geq\left(q^{r}\right)^{\frac{Cg}{q-1}}.$

Such field sizes are therefore exponential in the number of matrix sets $g$.
For PMDS codes, the resulting field sizes are asymptotically much larger than
(21), since

$(2g)^{r}\ll\left(q^{\frac{Cg}{q-1}}\right)^{r},\quad\textrm{due
to}\quad(2g)^{q-1}\ll q^{Cg},\quad\textrm{asymptotically},$

since for such AG codes we will have that $g\geq\mu\geq q^{r}\gg q$ if $r\geq
2$. A similar fact was already observed in [36, Sec. VI-B], when comparing the
field size (21) (obtained in [36, Sec. III]) with those obtained in [19] using
AG codes.

However, the codes in Subsection 4.3 (linearized RS codes [31] and their duals
[10]) require $q>g$. Hence, we may not use such MSRD codes over a fixed base
field $\mathbb{F}_{q}$ if we want $q$ to be small and/or fixed and $g$ be
large and/or grow. Even if this is not the case for building PMDS codes, it
may be the case for other applications of MSRD codes where we do not have
flexibility on $q$ (see Subsection 2.4). In such cases, using AG codes will
provide MSRD codes with smaller $m$, thus smaller $q^{m}$, than in previous
subsections, relative to the other code parameters being $q$ smaller than $g$.
For these reasons, we will only describe MSRD codes from now on, and we do not
provide further PMDS codes.

In order to describe the obtained parameters of the MSRD codes in Definition
32, we need to briefly revisit AG codes. For further details, the reader is
referred to [46].

Consider an irreducible projective curve $\mathcal{X}$ over
$\mathbb{F}_{q^{r}}$ (meaning irreducible over the algebraic closure of
$\mathbb{F}_{q^{r}}$) with algebraic function field $\mathcal{F}$, and let
$\mathfrak{g}=\mathfrak{g}(\mathcal{X})=\mathfrak{g}(\mathcal{F})$ be its
genus. Points in $\mathcal{X}$ correspond to places in $\mathcal{F}$ (we may
work indistinctly with $\mathcal{X}$ or $\mathcal{F}$) and we say that they
are rational if they are rational over $\mathbb{F}_{q^{r}}$ (their coordinates
lie in $\mathbb{F}_{q^{r}}$). A divisor over $\mathcal{X}$ is a formal sum
$D=\sum_{P\in\mathcal{X}}\mu_{P}P$, for integers $\mu_{P}\in\mathbb{Z}$ which
are all zero except for a finite number. The support of $D$ is defined as
$\\{P\in\mathcal{X}\mid\mu_{P}\neq 0\\}$, and $D$ is called rational if all
points in its support are rational. We define the degree of the rational
divisor $D$ as $\deg(D)=\sum_{P\in\mathcal{X}}\mu_{P}\in\mathbb{Z}$. All
divisors considered in this paper will be rational (over
$\mathbb{F}_{q^{r}}$).

For divisors $D=\sum_{P\in\mathcal{X}}\mu_{P}P$ and
$E=\sum_{P\in\mathcal{X}}\lambda_{P}P$, we write $D\preceq E$ if
$\mu_{P}\leq\lambda_{P}$, for all $P\in\mathcal{X}$. For an algebraic function
$f\in\mathcal{F}$, we define its divisor as
$(f)=\sum_{P\in\mathcal{X}}\nu_{P}(f)P$, where $\nu_{P}$ is the valuation at
the point $P$ (see [46, Def. 1.1.12]). Hence we may define the Riemann-Roch
space (see [46, Def. 1.1.4]) of a divisor $D$ as the vector space over
$\mathbb{F}_{q^{r}}$ given by

$\mathcal{L}(D)=\\{f\in\mathcal{F}\mid(f)+D\succeq 0\\}.$

Finally, fix rational divisors $D=P_{1}+P_{2}+\cdots+P_{\mu}$ and $G$ over
$\mathcal{X}$ with disjoint supports and where the points
$P_{1},P_{2},\ldots,P_{\mu}$ are all distinct. We define the corresponding
Algebraic-Geometry code (see [46, Eq. (2.3)]), or AG code for short, as the
linear code

$\mathcal{C}(D,G)=\left\\{\left(f(P_{1}),f(P_{2}),\ldots,f(P_{\mu})\right)\mid
f\in\mathcal{L}(G)\right\\}\subseteq\mathbb{F}_{q^{r}}^{\mu}.$ (35)

For our purposes, the most important results are the following two well known
lemmas on the parameters of AG codes. The first is the well known Goppa bound
[46, Cor. 2.2.3 (a)].

######  Lemma 41 (Goppa bound [46]).

If $\deg(G)<\mu$, then

${\rm d}_{H}(\mathcal{C}(D,G))\geq\mu-\dim(\mathcal{C}(D,G))-\mathfrak{g}+1.$

The following lemma is [46, Cor. 2.2.3(b)].

######  Lemma 42 ([46]).

If $2\mathfrak{g}-2<\deg(G)<\mu$, then

$\dim(\mathcal{C}(D,G))=\deg(G)-\mathfrak{g}+1.$

Hence we obtain the following theorem from Lemmas 41 and 42.

######  Theorem 9.

Assume that $2\mathfrak{g}-2<\deg(G)=\mu-h-1$, in particular
$t=\min\\{h,\mu\\}=h$ if $\mathfrak{g}>0$. Define
$\rho=\mu-\deg(G)+\mathfrak{g}-1$, which thus satisfies
$\mathfrak{g}-1<\rho<\mu-\mathfrak{g}+1$. Choose the code
$\mathcal{C}_{\boldsymbol{\gamma}}\subseteq\mathbb{F}_{q^{r}}^{\mu}$ in (18)
to be the AG code $\mathcal{C}_{\boldsymbol{\gamma}}=\mathcal{C}(D,G)$, as
above. Then the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
in Definition 32 has $g=\ell\mu$ matrix sets, where $\ell$ may be arbitrary
with $1\leq\ell\leq q-1$. The base field is $\mathbb{F}_{q}$, where $q>\ell$,
and the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
has size

$|\mathbb{F}_{q^{m}}|=q^{r\rho}=\left(q^{r}\right)^{\mu-\deg(G)+\mathfrak{g}-1}=\left(q^{r}\right)^{h+\mathfrak{g}}.$
(36)

As usual in the AG-code literature, the name of the game is: 1) to be able to
pick as many rational points $P_{1},P_{2},\ldots,P_{\mu}$ as possible in
$\mathcal{X}$ but outside the support of $G$, and 2) to have control over
$\deg(G)$. This is achieved by using one-point AG codes. We assume that
$\mathcal{X}$ has at least $\mu+1$ distinct rational points (over
$\mathbb{F}_{q^{r}}$), $P_{1},P_{2},\ldots,P_{\mu},Q$, and we define
$G=(\mu-h-1)Q$, which thus satisfies that $\deg(G)=\mu-h-1$. The corresponding
one-point AG code is $\mathcal{C}(D,G)$, being $D=P_{1}+P_{2}+\cdots+P_{\mu}$
and $G$ as above. We will explore different choices of $\mathcal{X}$ in the
following subsections.

###  4.8 Using Hermitian AG codes

We start by exploring Hermitian curves $\mathcal{X}$ (see [46, Sec. 8.3]).
Throughout the subsection, we assume that there is a positive integer $s$ such
that

$q^{r}=p^{2s},\quad\textrm{that is,}\quad 2s=r\log_{p}(q),$

where $p$ is the prime number that divides $q$, which can be arbitrary, e.g.,
$p=2$. The Hermitian curve is the projective plane curve with homogeneous
equation

$x^{q^{\frac{r}{2}}+1}-y^{q^{\frac{r}{2}}}z-yz^{q^{\frac{r}{2}}}=0.$

This curve is called a Hermitian curve and has $q^{\frac{3r}{2}}+1$ rational
points (over $\mathbb{F}_{q^{r}}$), and genus

$\mathfrak{g}=\mathfrak{g}(\mathcal{X})=\frac{q^{\frac{r}{2}}\left(q^{\frac{r}{2}}-1\right)}{2}.$

Therefore, we may choose $\mu=q^{3r/2}$ in Theorem 9, and we deduce the
following consequence.

######  Corollary 43.

Let the notation and assumptions be as in Theorem 9, but where $\mathcal{X}$
is the Hermitian curve above. Further assume that $G=(\mu-h-1)Q$ (recall that
$\mu-h\geq 2\mathfrak{g}$), for a rational point $Q$ in $\mathcal{X}$,
different than $P_{1},P_{2},\ldots,P_{\mu}$ that form the support of $D$.
Assume moreover that

$\ell=q-1\quad\textrm{and}\quad\mu=q^{\frac{3r}{2}}.$

Then the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
in Definition 32 has $g=\ell\mu=(q-1)q^{\frac{3r}{2}}$ matrix sets. The base
field is $\mathbb{F}_{q}$, where $q=\ell+1$, and the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
has size

$|\mathbb{F}_{q^{m}}|=\left(q^{r}\right)^{h+\mathfrak{g}}=\mu^{\frac{2}{3}(h+\mathfrak{g})}=\mu^{\frac{1}{3}(2h+\mu^{2/3}-\mu^{1/3})},$
(37)

that is,
$m=r\left(h+\frac{1}{2}\left(\mu^{\frac{2}{3}}-\mu^{\frac{1}{3}}\right)\right)$,
where $\mu=\frac{g}{q-1}$.

Observe that the field size (37) may be asymptotically smaller than the field
sizes (23) and (31) if $h<\mu$ and $\mu^{2/3}-\mu^{1/3}<\varepsilon h$ for a
sufficiently small $\varepsilon>0$. In other words, we may reduce the exponent
$h$ to roughly $2h/3$ for a small enough $\varepsilon>0$. In the next
subsection, we reduce the exponent to roughly $h/2$ by making use of the so-
called Suzuki curves.

###  4.9 Using Suzuki AG codes

In this subsection, we explore Suzuki curves $\mathcal{X}$ (see [21]).
Throughout the subsection, we assume that there is a positive integer $s$ such
that $r$ divides $2s+1$ (hence $r$ is odd), and we consider the even field
size

$q^{r}=2^{2s+1},\quad\textrm{that is,}\quad 2s+1=r\log_{2}(q).$

The Suzuki curve is the projective plane curve with homogeneous equation

$x^{2^{s}}\left(y^{q^{r}}+yx^{q^{r}-1}\right)=z^{2^{s}}\left(z^{q^{r}}+zx^{q^{r}-1}\right).$

This curve has $q^{2r}+1$ rational points over $\mathbb{F}_{q^{r}}$ by [21,
Prop. 2.1], and genus

$\mathfrak{g}=\mathfrak{g}(\mathcal{X})=2^{s}\left(q^{r}-1\right)$

by [21, Lemma 1.9]. Therefore, we may choose $\mu=q^{2r}$ in Theorem 9, hence

$\mathfrak{g}=2^{s}\left(\mu^{\frac{1}{2}}-1\right)\leq\mu^{\frac{1}{4}}\left(\mu^{\frac{1}{2}}-1\right)=\mu^{\frac{3}{4}}-\mu^{\frac{1}{4}},$

and we deduce the following consequence.

######  Corollary 44.

Let the notation and assumptions be as in Theorem 9, but where $\mathcal{X}$
is the Suzuki curve above. Further assume that $G=(\mu-h-1)Q$ (recall that
$\mu-h\geq 2\mathfrak{g}$), for a rational point $Q$ in $\mathcal{X}$,
different than $P_{1},P_{2},\ldots,P_{\mu}$ that form the support of $D$.
Assume moreover that

$\ell=q-1\quad\textrm{and}\quad\mu=q^{2r}.$

Then the MSRD code
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
in Definition 32 has $g=\ell\mu=(q-1)q^{2r}$ matrix sets. The base field is
$\mathbb{F}_{q}$, where $q=\ell+1$, and the field of linearity of
$\mathcal{C}_{k}(\mathbf{a},\boldsymbol{\beta})\subseteq\mathbb{F}_{q^{m}}^{gr}$
has size

$|\mathbb{F}_{q^{m}}|=\left(q^{r}\right)^{h+\mathfrak{g}}=\mu^{\frac{1}{2}(h+\mathfrak{g})}\leq\mu^{\frac{1}{2}\left(h+\mu^{\frac{3}{4}}-\mu^{\frac{1}{4}}\right)},$
(38)

that is, $m=r\left(h+2^{s}\left(\mu^{\frac{1}{2}}-1\right)\right)\leq
r\left(h+\mu^{\frac{3}{4}}-\mu^{\frac{1}{4}}\right)$, where
$\mu=\frac{g}{q-1}$.

Observe now that the field size (38) may be asymptotically smaller than the
field sizes (23), (31) and (37) if $h<\mu$ and
$\mu^{3/4}-\mu^{1/4}<\varepsilon h$ for a sufficiently small $\varepsilon>0$.
In other words, we may reduce the exponent $h$ to roughly $h/2$ for a small
enough $\varepsilon>0$. Finally, in the next subsection, we reduce the
exponent to $4h/i$, where $i$ may grow unbounded, by making use of the second
sequence of curves by García and Stichtenoth.

###  4.10 Using García-Stichtenoth’s AG codes

In this subsection, we explore the second sequence of curves
$(\mathcal{X}_{i})_{i=1}^{\infty}$ given by García and Stichtenoth (see [15]
or [46, Sec. 7.4]). As in Subsection 4.8, we assume throughout the subsection
that there is a positive integer $s$ such that

$q^{r}=p^{2s},\quad\textrm{that is,}\quad 2s=r\log_{p}(q),$

where $p$ is the prime number that divides $q$, which can be arbitrary, e.g.,
$p=2$. In this case, rather than giving the implicit equations of the
projective curve, it is more convenient to define recursively the associated
sequence of algebraic function fields $(\mathcal{F}_{i})_{i=1}^{\infty}$.
First we define $\mathcal{F}_{1}=\mathbb{F}_{q^{r}}(x_{1})$, where $x_{1}$ is
transcendental over $\mathbb{F}_{q^{r}}$, and then we define recursively
$\mathcal{F}_{i+1}=\mathcal{F}_{i}(x_{i+1})$, where $x_{i+1}$ is algebraic
over $\mathcal{F}_{i}$ satisfying the equation

$x_{i+1}^{q^{\frac{r}{2}}}+x_{i+1}=\frac{x_{i}^{q^{\frac{r}{2}}}}{x_{i}^{q^{\frac{r}{2}}-1}+1},$

for all $i\in\mathbb{Z}_{+}$. The $i$th curve $\mathcal{X}_{i}$ has
$q^{\frac{ir}{2}}\left(q^{\frac{r}{2}}-1\right)+1$ rational points, and its
genus is given by

$\mathfrak{g}(\mathcal{X}_{i})=\left\\{\begin{array}[]{ll}\left(q^{\frac{ir}{4}}-1\right)^{2}&\textrm{if
}i\textrm{ is even},\\\
\left(q^{\frac{(i+1)r}{4}}-1\right)\cdot\left(q^{\frac{(i-1)r}{4}}-1\right)&\textrm{if
}i\textrm{ is odd},\\\ \end{array}\right.$

by [15, Remark 3.8]. This means that the number of rational places divided by
the genus, for the $i$th curve, converges to an optimal value, the so-called
Ihara’s constant, as $i$ goes to infinity. See [46, Ch. 7] for more details on
the asymptotic behaviour of AG codes.

To build MSRD codes as in Definition 32, we may choose
$\mu_{i}=q^{\frac{ir}{2}}\left(q^{\frac{r}{2}}-1\right)$ in Theorem 9, hence

$\mathfrak{g}_{i}=\mathfrak{g}(\mathcal{X}_{i})\leq
q^{\frac{ir}{2}}=\frac{\mu_{i}}{q^{\frac{r}{2}}-1},$

for all $i\in\mathbb{Z}_{+}$, and we deduce the following consequence.

######  Corollary 45.

Let the notation and assumptions be as in Theorem 9, but where
$\mathcal{X}_{i}$ is the $i$th curve in the García-Stichtenoth’s sequence
given above, for $i\in\mathbb{Z}_{+}$. We will also add an index $i$ in every
parameter that depends on the $i$th curve. Assume that
$G_{i}=(\mu_{i}-h_{i}-1)Q_{i}$ (recall that $\mu_{i}-h_{i}\geq
2\mathfrak{g}_{i}$), for a rational point $Q_{i}$ in $\mathcal{X}_{i}$,
different than $P_{i,1},P_{i,2},\ldots,P_{i,\mu_{i}}$ that form the support of
$D_{i}$. Assume moreover that

$\mu_{i}=q^{\frac{ir}{2}}\left(q^{\frac{r}{2}}-1\right)\quad\textrm{and}\quad\ell=q-1.$

Then the MSRD code
$\mathcal{C}_{k_{i}}(\mathbf{a}_{i},\boldsymbol{\beta}_{i})\subseteq\mathbb{F}_{q^{m_{i}}}^{g_{i}r}$
in Definition 32, for each $i\in\mathbb{Z}_{+}$, has
$g_{i}=\ell\mu_{i}=(q-1)\left(q^{\frac{r}{2}}-1\right)q^{\frac{ir}{2}}$ matrix
sets. The base field is $\mathbb{F}_{q}$, where $q=\ell+1$, constant in $i$,
and the field of linearity of
$\mathcal{C}_{k_{i}}(\mathbf{a}_{i},\boldsymbol{\beta}_{i})\subseteq\mathbb{F}_{q^{m_{i}}}^{g_{i}r}$
has size

$|\mathbb{F}_{q^{m_{i}}}|=\left(q^{r}\right)^{h_{i}+\mathfrak{g}_{i}}\leq\left(q^{r}\right)^{h_{i}+q^{\frac{ir}{2}}}=\left(\frac{\mu_{i}}{q^{\frac{r}{2}}-1}\right)^{\frac{2}{i}\left(h_{i}+\frac{\mu_{i}}{q^{\frac{r}{2}}-1}\right)}.$
(39)

that is, $m_{i}\leq
r\left(h_{i}+q^{\frac{ir}{2}}\right)=r\left(h_{i}+\frac{\mu_{i}}{q^{\frac{r}{2}}-1}\right)$,
where $\mu_{i}=\frac{g_{i}}{q-1}$.

Observe now that the field size (39) may be asymptotically smaller than the
field sizes (23), (31), (37) and (38) in general if
$\mu_{i}/(q^{r/2}-1)<h_{i}<\mu_{i}$ (a range where
$h_{i}=\Theta(\mu_{i})=\Theta(g_{i})=\Theta(g_{i}r)$). In such cases, we may
reduce the exponent $h_{i}$ to $4h_{i}/i$, where $i$ may grow unbounded. Hence
the coefficient of $h_{i}$ in the exponent may be as small as wanted.

##  5 Summary of results and comparisons with the literature

In this final section, we will summarize the parameters of the MSRD codes and
PMDS codes obtained throughout this work, and compare them to those from the
literature.

The parameters of the MSRD codes obtained in Subsections 4.3, 4.4, 4.5, 4.6,
4.8, 4.9, and 4.10 are summarized in Table 1. The parameters of the PMDS codes
obtained in Subsections 4.3, 4.4, and 4.6 are summarized in Table 2.

Code $\mathcal{C}_{\boldsymbol{\gamma}}$ |  $q$, $r$, $h$ | No. matrix sets $g$ | Field of linearity $q^{m}$
---|---|---|---
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ | Any | $q-1$ |  $q^{r}=(g+1)^{r}$, $m=r$
MDS | Any | $(q-1)\left(q^{r}+1\right)$ | $\left(\frac{g}{q-1}-1\right)^{\min\left\\{h,\frac{g}{q-1}\right\\}}$
Hamming, $\rho\in\mathbb{Z}_{+}$ | $h=2$ | $(q-1)\cdot\frac{q^{r\rho}-1}{q^{r}-1}$ | $q^{r\rho}=\frac{q^{r}-1}{q-1}\cdot g+1$
Pr. BCH, $s\in\mathbb{Z}_{+}$ | Any | $(q-1)\left(q^{rs}-1\right)$ | $\leq q^{r}\cdot\left(\frac{g}{q-1}+1\right)^{\left\lceil\frac{q^{r}-1}{q^{r}}(h-1)\right\rceil}$
Hermitian AG | $q^{r}=p^{2s}$ | $(q-1)q^{\frac{3r}{2}}$ |  $\mu^{\frac{1}{3}(2h+\mu^{2/3}-\mu^{1/3})}$, $\mu=\frac{g}{q-1}$
Suzuki AG | $q^{r}=2^{2s+1}$ | $(q-1)q^{2r}$ |  $\leq\mu^{\frac{1}{2}\left(h+\mu^{3/4}-\mu^{1/4}\right)}$, $\mu=\frac{g}{q-1}$
AG [15], $i\in\mathbb{Z}_{+}$ | $q^{r}=p^{2s}$ | $(q-1)\left(q^{\frac{r}{2}}-1\right)q^{\frac{ir}{2}}$ |  $\leq\left(\frac{\mu_{i}}{q^{\frac{r}{2}}-1}\right)^{\frac{2}{i}\left(h_{i}+\frac{\mu_{i}}{q^{\frac{r}{2}}-1}\right)}$, $\mu_{i}=\frac{g_{i}}{q-1}$
Table 1: Table summarizing the code parameters of the linear MSRD codes obtained in this work throughout Subsections 4.3, 4.4, 4.5, 4.6, 4.8, 4.9, and 4.10. They are $\mathbb{F}_{q^{m}}$-linear codes in $\mathbb{F}_{q^{m}}^{gr}$ with code length $N=gr$, dimension $k=gr-h$, minimum sum-rank distance $d=h+1$. Their codewords can be seen as lists of $g$ matrices over $\mathbb{F}_{q}$ of size $m\times r$, where $m=r\rho$, $\rho\in\mathbb{Z}_{+}$, and $m=r$ only in the first row. The linear MSRD code in the first row was obtained in [31], and later independently in [11] and [39].  Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | Restrictions on $r$, $\delta$, $g$, $h$, $q$ | Field size $q^{m}$
---|---|---
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ | $\max\\{\nu,g\\}<q\leq 2\max\\{\nu,g\\}$ |  $q^{m}\leq(2\max\\{\nu,g\\})^{r}$, $m=r$
MDS |  $g=(q-1)\left(q^{r}+1\right)$ or $(2\nu)^{r}>\frac{g}{\nu}$ | $q^{m}\leq\max\left\\{\left(2\nu\right)^{r},\left\lfloor\frac{g}{\nu}\right\rfloor-1\right\\}^{\min\left\\{h,\left\lfloor\frac{g}{\nu}\right\rfloor\right\\}}$
Primitive BCH |  $g=(q-1)\left(q^{rs}-1\right)$ and $q>\nu$ | $q^{m}\leq(2\nu)^{r}\cdot\left(\left\lfloor\frac{g}{\nu}\right\rfloor+1\right)^{h-1}$
Table 2: Table summarizing the code parameters of the linear PMDS codes
obtained in this work throughout Subsections 4.3, 4.4, and 4.6. They are
$\mathbb{F}_{q^{m}}$-linear codes in $\mathbb{F}_{q^{m}}^{g\nu}$, where $r$ is
the locality, $\delta$ is the local distance, $g$ is the number of local sets,
$h$ is the number of global parities, $\nu=r+\delta-1$ is the local-set size
and $q$ is a power of $2$. The field size of the local codes is a subfield of
$\mathbb{F}_{q}$. The linear PMDS code in the first row was obtained in [36].

###  5.1 Comparison with MSRD codes in the literature

We start by discussing MSRD codes. First of all, smaller values of $g$ and $r$
in Table 1 may be obtained in each row by puncturing or shortening the
corresponding MSRD codes (see Remark 8). However, the comparison between
$q^{m}$ and $g$ (or $r$) would then be lost, as $q$ and $m$ remain unchanged
after puncturing or shortening.

As discussed in the Introduction and after Remark 31, any MRD code [12, 13,
41] is an MSRD code, however, their fields of linearity have size $q^{m}\geq
q^{gr}$, thus exponential in the code length $N=gr$. Equivalently, they
require $m\geq gr$ for the matrix sizes in (3). As the reader may check, all
of the field sizes $q^{m}$ in Table 1 are sub-exponential in $N=gr$ and much
smaller than $q^{gr}$.

The first known construction of MSRD codes with sub-exponential field sizes is
that of linearized Reed-Solomon codes and their duals, which moreover admit
any value of $q$, $r$, $h$ and $g$ as long as $g<q$. They were introduced in
[31], and later independently in [11, 39]. As discussed in Subsection 4.3,
this construction corresponds to the codes in the first row in Table 1. Thus
the comparison with the rest of the obtained MSRD codes can be directly
inspected in that table. We note that these are the only known MSRD codes
satisfying $m=r$ when $g>1$ (thus yielding square matrices in (3)). However,
they require $q>g$ and in particular $q=2$ may not be attained, which is not
the case for the rest of the codes in Table 1. The MSRD codes based on MDS,
Hamming and primitive BCH codes admit a smaller value of $q^{m}$ when $h$ is
small relative to $r$, although not necessarily only when $h<r$. As discussed
in Subsection 4.7, MSRD codes based on AG codes always require field sizes
$q^{m}$ much larger than linearized Reed-Solomon codes if $q>g$. However, MSRD
codes based on AG codes admit values $q\ll g$, and in such cases, they admit
smaller coefficients of $h$ in the exponent of the field size $q^{m}$ than the
rest of MSRD codes.

Some constructions of MSRD codes were recently given in [6]. As explained in
Remark 8, such codes are only $\mathbb{F}_{q}$-linear, and have minimum sum-
rank distance equal to $2$ or $\sum_{i=1}^{g}r_{i}-1$ (total number of
columns, across all matrices, minus $1$), or require the number of rows or
columns to be $1$ at certain positions in the matrices in (3).

Finally, as we wrote in Subsection 4.5, the codes in the third row in Table 1,
based on Hamming codes and valid for $h=2$ (i.e., minimum sum-rank distance
$3$), achieve the maximum possible value of $g$ with respect to the other
parameters, in view of the bound (8). Equivalently, they achieve the smallest
possible value of $m$ with respect to the other parameters. As noted in Table
1, the attainable values of $q$ and $r$ for such construction are arbitrary.
Finally, this is the first and only known family of MSRD codes with field size
$q^{m}$ linear in $g$, hence linear in the code length $N=gr$ if the number of
columns per matrix, $r$, is upper bounded by a constant. Since their minimum
sum-rank distance is $3$, they are either $2$-erasure-correcting or $1$-error-
correcting.

###  5.2 Comparison with PMDS codes in the literature

We now turn to discussing PMDS codes. For small specific values of $r$,
$\delta$, $g$ or $h$, there exist PMDS codes with smaller field sizes than in
Table 2. More concretely, PMDS codes with field sizes that are linear in the
code length $n=g\nu$ were obtained in [3] for $h=1$ and any $\delta$, and for
$h>1$ and $\delta=2$ based on the irreducibility of certain polynomials, which
are only known to cover some parameter values. Finally, PMDS codes with
smaller field sizes than in Table 2 were obtained for $h=2$ and $g=2$ in [4]
and [22], respectively.

To the best of our knowledge, the PMDS codes available for general parameters
with the smallest known field sizes are those in [14, 19, 36].

First of all, the PMDS codes in the first row in Table 2 are exactly those
obtained in [36] (more concretely, in [36, Construction 1]). They have smaller
field sizes than the codes in the second and third rows in general when
$\nu>g$ or when

$r<\min\left\\{\left\lfloor\frac{g}{\nu}\right\rfloor,h-1\right\\}.$

In [14, Cor. 10], PMDS codes are obtained with field sizes

$q^{m}=\mathcal{O}\left(\max\left\\{(2\nu)^{\delta+h},g\right\\}^{h}\right),$
(40)

and later, in [19, Th. 3.8, 3.9, 3.11, 3.12], PMDS codes are obtained with the
following field sizes:

$\begin{split}q^{m}&=\left(\max\left\\{\widetilde{\mathcal{O}}(g),(2\nu)^{\left\lfloor\frac{h+1}{2}\right\rfloor}\right\\}\right)^{\min\\{h,g\\}},\\\
q^{m}&=\left(\max\left\\{\widetilde{\mathcal{O}}(g),2^{r}\right\\}\right)^{\min\\{h,g\\}},\\\
q^{m}&=\left(\max\left\\{\widetilde{\mathcal{O}}(g),(2\nu)^{h+\delta-1}\right\\}\right)^{\min\\{h,g\\}},\\\
q^{m}&=\left(\max\left\\{\widetilde{\mathcal{O}}(g),(2\nu)^{\nu}\right\\}\right)^{\min\\{h,g\\}},\end{split}$
(41)

where $\widetilde{\mathcal{O}}$ corresponds to the big O notation but
disregarding logarithmic multiplicative factors. The PMDS codes in the second
and third rows in Table 2, based on MDS codes and primitive BCH codes, have
smaller field sizes than those in (40) and (41) in most cases when $g$ is
large relative to the other parameters. For instance, if $\nu=\mathcal{O}(1)$
(i.e., $r=\mathcal{O}(1)$ and $\delta=\mathcal{O}(1)$), but $g$ is unbounded,
then the field sizes in the second and third rows of Table 2 are

$q^{m}=\mathcal{O}\left(\left(\frac{g}{\nu}\right)^{\min\left\\{h,\left\lfloor\frac{g}{\nu}\right\rfloor\right\\}}\right)\quad\textrm{and}\quad
q^{m}=\mathcal{O}\left(\left(\frac{g}{\nu}\right)^{h-1}\right),$ (42)

respectively, which are smaller than (40) and (41) in such a parameter regime.
In addition, if $\nu=\mathcal{O}(1)$ and also $h=\mathcal{O}(1)$, and $g$ is
the only unbounded parameter, then the best field size among all known PMDS
codes is that in the third row in Table 2, which reads

$q^{m}=\mathcal{O}\left(g^{h-1}\right)=\mathcal{O}\left(n^{h-1}\right),$ (43)

where $n=g\nu$ is the code length. The existence of PMDS codes with field size
(43) has been proven recently in [5] for $r=2$. In contrast, the codes in the
third row of Table 2 can be explicitly constructed and admit any value of $r$.

Simultaneously and independently to this work, a construction of PMDS codes
was obtained in [7] with field sizes

$q^{m}=q^{h}=\Theta\left(n^{\frac{h}{2}}\right)=\Theta\left(nr^{h-2}\right),$
(44)

for parameters satisfying $g=\Theta(q)$, $r=\Theta(q)$, and
$h\leq\min\\{g,\delta+1\\}$. For this parameter regime, the field sizes (44)
meet the lower bound from Proposition 16 asymptotically, hence they have
optimal field asymptotic order. We remark that the parameter regime of our
PMDS codes (second and third rows in Table 2), is disjoint from the regime
considered in [7], since in our case, we have that
$g=\Omega\left(q^{r}\right)\gg r$, hence it may not happen at the same time
that $g=\Theta(r)$.

Finally, as discussed in Subsection 4.7 and in [36, Sec. VI-B], the PMDS codes
obtained in [19] based on AG codes have larger field sizes than those in the
first row of Table 2, which were already obtained in [36].

## References

  * [1] A. Beutelspacher.  Partial spreads in finite projective spaces and partial designs.  Mathematische Zeitschrift, 145(3):211–229, Oct 1975.
  * [2] A. Beutelspacher.  On $t$-covers in finite projective spaces.  Journal of Geometry, 12(1):10–16, 1979.
  * [3] M. Blaum, J. L. Hafner, and S. Hetzler.  Partial-MDS codes and their application to RAID type of architectures.  IEEE Trans. Info. Theory, 59(7):4510–4519, July 2013.
  * [4] M. Blaum, J. S. Plank, M. Schwartz, and E. Yaakobi.  Construction of partial MDS and Sector-Disk codes with two global parity symbols.  IEEE Trans. Info. Theory, 62(5):2673–2681, May 2016.
  * [5] T. Bogart, A.-L. Horlemann-Trautmann, D. Karpuk, A. Neri, and M. Velasco.  Constructing partial MDS codes from reducible curves.  2020\.  Preprint: arXiv:2007.14829.
  * [6] E. Byrne, H. Gluesing-Luerssen, and A. Ravagnani.  Fundamental properties of sum-rank metric codes.  2020\.  Preprint: arXiv:2010.02779.
  * [7] H. Cai, Y. Miao, M. Schwartz, and X. Tang.  A construction of maximally recoverable codes with order-optimal field size.  2020\.  Preprint: arXiv:2011.13606.
  * [8] H. Cai, Y. Miao, M. Schwartz, and X. Tang.  On optimal locally repairable codes with multiple disjoint repair sets.  IEEE Trans. Info. Theory, 66(4):2402–2416, 2020.
  * [9] G. Calis and O. O. Koyluoglu.  A general construction for PMDS codes.  IEEE Communications Letters, 21(3):452–455, March 2017.
  * [10] X. Caruso.  Residues of skew rational functions and linearized Goppa codes.  2019\.  Preprint: arXiv:1908.08430.
  * [11] X. Caruso and A. Durand.  Reed-Solomon-Gabidulin codes.  2018\.  Preprint: arXiv:1812.09147.
  * [12] P. Delsarte.  Bilinear forms over a finite field, with applications to coding theory.  J. Comb. Theory, S. A, 25(3):226–241, 1978.
  * [13] E. M. Gabidulin.  Theory of codes with maximum rank distance.  Problems Inform. Transmission, 21(1):1–12, 1985.
  * [14] R. Gabrys, E. Yaakobi, M. Blaum, and P. H. Siegel.  Constructions of partial MDS codes over small fields.  IEEE Trans. Info. Theory, 65(6):3692–3701, 2019.
  * [15] A. García and H. Stichtenoth.  On the asymptotic behaviour of some towers of function fields over finite fields.  J. Number Theory, 61(2):248–273, 1996.
  * [16] P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin.  Explicit maximally recoverable codes with locality.  IEEE Trans. Info. Theory, 60(9):5245–5256, Sept 2014.
  * [17] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin.  On the locality of codeword symbols.  IEEE Trans. Info. Theory, 58(11):6925–6934, Nov 2012.
  * [18] S. Gopi, V. Guruswami, and S. Yekhanin.  On maximally recoverable local reconstruction codes.  Electr. Colloq. Comp. Complexity (ECCC), 24(183), 2017.
  * [19] V. Guruswami, L. Jin, and C. Xing.  Constructions of maximally recoverable local reconstruction codes via function fields.  IEEE Trans. Info. Theory, 66(10):6133–6143, 2020.
  * [20] R. W. Hamming.  Error detecting and error correcting codes.  The Bell System Technical Journal, 29(2):147–160, April 1950.
  * [21] J.P. Hansen and H. Stichtenoth.  Group codes on certain algebraic curves with many rational points.  Appl. Alg. Engin. Comm. Comput., 1:67–77, 1990.
  * [22] G. Hu and S. Yekhanin.  New constructions of SD and MR codes over small finite fields.  In Proc. IEEE Int. Symp. Info. Theory, pages 1591–1595, July 2016.
  * [23] W. C. Huffman and V. Pless.  Fundamentals of error-correcting codes.  Cambridge University Press, Cambridge, 2003.
  * [24] G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar.  Codes with local regeneration and erasure correction.  IEEE Trans. Info. Theory, 60(8):4637–4660, Aug 2014.
  * [25] T. Y. Lam.  A general theory of Vandermonde matrices.  Expositiones Mathematicae, 4:193–215, 1986.
  * [26] T. Y. Lam and A. Leroy.  Vandermonde and Wronskian matrices over division rings.  J. Algebra, 119(2):308–336, 1988.
  * [27] R. Lidl and H. Niederreiter.  Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications.  Addison-Wesley, Amsterdam, 1983.
  * [28] S. Liu, F. Manganiello, and F. R. Kschischang.  Matroidal structure of skew polynomial rings with application to network coding.  Finite Fields App., 46(C):326–346, 2017.
  * [29] H.-F. Lu and P. V. Kumar.  A unified construction of space-time codes with optimal rate-diversity tradeoff.  IEEE Trans. Info. Theory, 51(5):1709–1730, May 2005.
  * [30] F. J. MacWilliams and N. J. A. Sloane.  The Theory of Error-Correcting Codes.  North-Holland Mathematical Library, 1983.
  * [31] U. Martínez-Peñas.  Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring.  J. Algebra, 504:587–612, 2018.
  * [32] U. Martínez-Peñas.  Private information retrieval from locally repairable databases with colluding servers.  In Proc. IEEE Int. Symp. Info. Theory, pages 1057–1061, 2019\.
  * [33] U. Martínez-Peñas.  Theory of supports for linear codes endowed with the sum-rank metric.  Des., Codes, Crypto., 87:2295–2320, Feb 2019.
  * [34] U. Martínez-Peñas.  Sum-rank BCH codes and cyclic-skew-cyclic codes.  2020\.  Preprint: arXiv:2009.04949.
  * [35] U. Martínez-Peñas and F. R. Kschischang.  Reliable and secure multishot network coding using linearized reed-solomon codes.  IEEE Trans. Info. Theory, 65(8):4785–4803, 2019.
  * [36] U. Martínez-Peñas and F. R. Kschischang.  Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes.  IEEE Trans. Info. Theory, 65(12):7790–7805, 2019.
  * [37] A. Neri and A.-L. Horlemann-Trautmann.  Random construction of partial MDS codes.  Des., Codes, Crypto., 88:711––725, 2020.
  * [38] R. W. Nóbrega and B. F. Uchôa-Filho.  Multishot codes for network coding using rank-metric codes.  In Proc. 2010 Third IEEE Int. Workshop on Wireless Network Coding, pages 1–6, 2010.
  * [39] T. H. Randrianarisoa and R. Pratihar.  On some automorphisms of rational function fields and their applications in rank metric codes.  2019\.  Preprint: arXiv:1907.05508.
  * [40] I. S. Reed and G. Solomon.  Polynomial codes over certain finite fields.  J. Soc. Ind. and Appl. Math., 8(2):300–304, 1960.
  * [41] R. M. Roth.  Maximum-rank array codes and their application to crisscross error correction.  IEEE Trans. Info. Theory, 37(2):328–336, March 1991.
  * [42] B. Segre.  Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane.  Annali di Matematica Pura ed Applicata, 64:1–76, 1964.
  * [43] B. A. Sethuraman, B. S. Rajan, and V. Shashidhar.  Full-diversity, high-rate space-time block codes from division algebras.  IEEE Trans. Info. Theory, 49(10):2596–2616, 2003.
  * [44] M. Shehadeh and F. R. Kschischang.  Rate-diversity optimal multiblock space-time codes via sum-rank codes.  In Proc. IEEE Int. Symp. Info. Theory, pages 3055–3060, 2020\.
  * [45] R. Singleton.  Maximum distance q-nary codes.  IEEE Trans. Info. Theory, 10(2):116–118, April 1964.
  * [46] H. Stichtenoth.  Algebraic function fields and codes, volume 254 of Graduate Texts in Mathematics.  Springer-Verlag Berlin Heidelberg, 2009.

## Appendix: Tables with even field sizes for MSRD codes

It is usual in the PMDS literature to consider and compare the obtained field
sizes asymptotically, where some parameters grow unbounded (mostly the code
length $n=g\nu$, i.e., the number of local sets $g$ and/or the local-set size
$\nu$). There are not many constructions of MSRD codes so far, so no trend
exists when comparing their parameters. However, in possible applications of
MSRD and PMDS codes, it is reasonable to think that code parameters will
rarely be large (even more so due to the required field sizes). In this
appendix, we provide several tables of attainable field sizes $q^{m}$,
divisible by $2$, among the linear MSRD codes obtained in this work.

First, we give a summary in Table 3, which is similar to Table 1, but where
the field size $q^{m}$ is not compared to $g$, but written as a function of
$q$, $r$ and $h$, excluding $g$. The reason behind this is that typically the
maximum attainable value of $g$ is quite large for most of these codes, and in
most cases we would puncture them in order to have a much smaller number of
matrix sets $g$. The motivation behind this is given in Table 4. That table
contains the case $q=2$, where other parameters vary. Note that, in that case,
linearized Reed-Solomon codes (Subsection 4.3) require $g=1$, thus not being
different than a Gabidulin code.

In Tables 5, 6 and 7, we fix $g$ and let other parameters vary. In contrast,
in Tables 8 and 9, we fix the code length $N=gr$ and let other parameters
vary. In these tables, bold numbers indicate field sizes that are the smallest
among MSRD codes of the same parameters. As linearized Reed-Solomon codes have
the same field sizes for all $h$, a bold number in that row means that the
field size is the smallest for the corresponding parameters for some $h$.

The field sizes attained by linear MSRD codes based on AG codes (Subsections
4.8, 4.9 and 4.10) are quite larger than those obtained by the other linear
MSRD codes for small parameters. In general, MSRD codes based on AG codes (as
in Subsection 4.7) are mostly of asymptotic interest. For this reason, they
are not included in Tables 4, 5, 6, 7, 8 and 9.

Due to Remark 38, the linear MSRD codes based on Hamming codes (Subsection
4.5) are only described for $\rho=3$.

Finally, at the end of each table we consider the smallest field size
attainable by an MRD code for the corresponding parameters. As it can be seen,
MRD codes always require significant larger field sizes than the MSRD codes
from this work, for the same parameters.

Code $\mathcal{C}_{\boldsymbol{\gamma}}$ |  $q$, $r$, $h$ | No. matrix sets $g$ | Field of linearity $q^{m}$
---|---|---|---
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS) | Any | $q-1$ | $q^{r}$
MDS | Any | $(q-1)\left(q^{r}+1\right)$ | $q^{r\min\left\\{h,q^{r}+1\right\\}}$
Hamming, $\rho\in\mathbb{Z}_{+}$ | $h=2$ | $(q-1)\cdot\frac{q^{r\rho}-1}{q^{r}-1}$ | $q^{r\rho}$
Pr. BCH, $s\in\mathbb{Z}_{+}$ | Any | $(q-1)\left(q^{rs}-1\right)$ | $\leq q^{r\left(1+s\left\lceil\frac{q^{r}-1}{q^{r}}(h-1)\right\rceil\right)}$
Hermitian AG | $q^{r}=p^{2s}$ | $(q-1)q^{\frac{3r}{2}}$ | $q^{r\left(h+\frac{1}{2}\left(q^{r}-q^{\frac{r}{2}}\right)\right)}$
Suzuki AG | $q^{r}=2^{2s+1}$ | $(q-1)q^{2r}$ | $q^{r\left(h+2^{s}\left(q^{r}-1\right)\right)}$
AG [15], $i\in\mathbb{Z}_{+}$ | $q^{r}=p^{2s}$ | $(q-1)\left(q^{\frac{r}{2}}-1\right)q^{\frac{ir}{2}}$ | $\leq q^{r\left(h_{i}+q^{\frac{ir}{2}}\right)}$
Table 3: Table summarizing the code parameters of the linear MSRD codes obtained in this work. In contrast with Table 1, field sizes are described in terms of $q$, $r$ and $h$, excluding $g$.  Table for $q=2$ | $r=2$ | $r=3$ | $r=4$ | $r=5$ | $r=6$
---|---|---|---|---|---
Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | $2^{m}$ | $g$ | $2^{m}$ | $g$ | $2^{m}$ | $g$ | $2^{m}$ | $g$ | $2^{m}$ | $g$
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS) | $2^{2}$ | $1$ | $2^{3}$ | $1$ | $2^{4}$ | $1$ | $2^{5}$ | $1$ | $2^{6}$ | $1$
MDS, $h=2$ | $2^{4}$ | $5$ | $2^{6}$ | $9$ | $2^{8}$ | $17$ | $2^{10}$ | $33$ | $2^{12}$ | $65$
MDS, $h=3$ | $2^{6}$ | $2^{9}$ | $2^{12}$ | $2^{15}$ | $2^{18}$
MDS, $h=4$ | $2^{8}$ |  | $2^{12}$ |  | $2^{16}$ |  | $2^{20}$ |  | $2^{24}$ |
Hamming, $\rho=3$, $h=2$ | $2^{6}$ | $21$ | $2^{9}$ | $73$ | $2^{12}$ | $273$ | $2^{15}$ | $1057$ | $2^{18}$ | $4161$
Pr. BCH, $s=2$, $h=2$ | $2^{6}$ | $15$ | $2^{9}$ | $63$ | $2^{12}$ | $255$ | $2^{15}$ | $1023$ | $2^{18}$ | $4095$
Pr. BCH, $s=2$, $h=3$ | $2^{10}$ | $2^{15}$ | $2^{20}$ | $2^{25}$ | $2^{30}$
Pr. BCH, $s=2$, $h=4$ | $2^{14}$ |  | $2^{21}$ |  | $2^{28}$ |  | $2^{35}$ |  | $2^{42}$ |
Pr. BCH, $s=3$, $h=2$ | $2^{8}$ | $63$ | $2^{12}$ | $511$ | $2^{16}$ | $4095$ | $2^{20}$ | $2^{15}-1$ | $2^{24}$ | $2^{18}-1$
Pr. BCH, $s=3$, $h=3$ | $2^{14}$ | $2^{21}$ | $2^{28}$ | $2^{35}$ | $2^{42}$
Pr. BCH, $s=3$, $h=4$ | $2^{20}$ |  | $2^{30}$ |  | $2^{40}$ |  | $2^{50}$ |  | $2^{60}$ |
Table 4: Table for fixed $q=2$, while other parameters vary.  Table for $g=7$, $q$ even | $r=2$ | $r=3$ | $r=4$ | $r=5$ | $r=6$
---|---|---|---|---|---
Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS), $\mathbf{\forall}h\geq 1$ | $\mathbf{2^{6}}$ | $2^{3}$ | $\mathbf{2^{9}}$ | $2^{3}$ | $\mathbf{2^{12}}$ | $2^{3}$ | $\mathbf{2^{15}}$ | $2^{3}$ | $\mathbf{2^{18}}$ | $2^{3}$
MDS, $h=2$ | $2^{8}$ | $2^{2}$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
MDS, $h=3$ | $2^{12}$ | $\mathbf{2^{9}}$ | $\mathbf{2^{12}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
MDS, $h=4$ | $2^{16}$ |  | $2^{12}$ |  | $2^{16}$ |  | $2^{20}$ |  | $2^{24}$ |
Hamming, $\rho=3$, $h=2$ | $\mathbf{2^{6}}$ | $2$ | $2^{9}$ | $2$ | $2^{12}$ | $2$ | $2^{15}$ | $2$ | $2^{18}$ | $2$
Pr. BCH, $s=1,2$, $h=2$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
Pr. BCH, $s=1,2$, $h=3$ | $2^{10}$ | $\mathbf{2^{9}}$ | $\mathbf{2^{12}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
Pr. BCH, $s=1,2$, $h=4$ | $2^{14}$ |  | $2^{12}$ |  | $2^{16}$ |  | $2^{20}$ |  | $2^{24}$ |
Best MRD code possible, $\mathbf{\forall}h\geq 1$ | $2^{14}$ | $2$ | $2^{28}$ | $2$ | $2^{42}$ | $2$ | $2^{56}$ | $2$ | $2^{70}$ | $2$
Table 5: Table for fixed $g=7$, while other parameters vary.  Table for $g=15$, $q$ even | $r=2$ | $r=3$ | $r=4$ | $r=5$ | $r=6$
---|---|---|---|---|---
Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS), $\mathbf{\forall}h\geq 1$ | $\mathbf{2^{8}}$ | $2^{4}$ | $\mathbf{2^{12}}$ | $2^{4}$ | $\mathbf{2^{16}}$ | $2^{4}$ | $\mathbf{2^{20}}$ | $2^{4}$ | $\mathbf{2^{24}}$ | $2^{4}$
MDS, $h=2$ | $2^{8}$ | $2^{2}$ | $2^{12}$ | $2^{2}$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
MDS, $h=3$ | $2^{12}$ | $2^{18}$ | $\mathbf{2^{12}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
MDS, $h=4$ | $2^{16}$ |  | $2^{24}$ |  | $\mathbf{2^{16}}$ |  | $\mathbf{2^{20}}$ |  | $\mathbf{2^{24}}$ |
Hamming, $\rho=3$, $h=2$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $2^{12}$ | $2$ | $2^{15}$ | $2$ | $2^{18}$ | $2$
Pr. BCH, $s=1,2$, $h=2$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
Pr. BCH, $s=1,2$, $h=3$ | $2^{10}$ | $2^{15}$ | $\mathbf{2^{12}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
Pr. BCH, $s=1,2$, $h=4$ | $2^{14}$ |  | $2^{21}$ |  | $\mathbf{2^{16}}$ |  | $\mathbf{2^{20}}$ |  | $\mathbf{2^{24}}$ |
Best MRD code possible, $\mathbf{\forall}h\geq 1$ | $2^{30}$ | $2$ | $2^{45}$ | $2$ | $2^{60}$ | $2$ | $2^{75}$ | $2$ | $2^{90}$ | $2$
Table 6: Table for fixed $g=15$, while other parameters vary.  Table for $g=31$, $q$ even | $r=2$ | $r=3$ | $r=4$ | $r=5$ | $r=6$
---|---|---|---|---|---
Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS), $\mathbf{\forall}h\geq 1$ | $\mathbf{2^{10}}$ | $2^{5}$ | $\mathbf{2^{15}}$ | $2^{5}$ | $\mathbf{2^{20}}$ | $2^{5}$ | $\mathbf{2^{25}}$ | $2^{5}$ | $\mathbf{2^{30}}$ | $2^{5}$
MDS, $h=2$ | $\mathbf{2^{8}}$ | $2^{2}$ | $2^{12}$ | $2^{2}$ | $2^{16}$ | $2^{2}$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
MDS, $h=3$ | $2^{12}$ | $2^{18}$ | $2^{24}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
MDS, $h=4$ | $2^{16}$ |  | $2^{24}$ |  | $2^{32}$ |  | $\mathbf{2^{20}}$ |  | $\mathbf{2^{24}}$ |
Hamming, $\rho=3$, $h=2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $\mathbf{2^{12}}$ | $2$ | $2^{15}$ | $2$ | $2^{18}$ | $2$
Pr. BCH, $s=1,2,3$, $h=2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $\mathbf{2^{12}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
Pr. BCH, $s=1,2,3$, $h=3$ | $2^{14}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{20}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
Pr. BCH, $s=1,2,3$, $h=4$ | $2^{20}$ |  | $2^{21}$ |  | $2^{28}$ |  | $\mathbf{2^{20}}$ |  | $\mathbf{2^{24}}$ |
Best MRD code possible, $\mathbf{\forall}h\geq 1$ | $2^{62}$ | $2$ | $2^{93}$ | $2$ | $2^{124}$ | $2$ | $2^{155}$ | $2$ | $2^{186}$ | $2$
Table 7: Table for fixed $g=31$, while other parameters vary.  Table for $N=gr=30$, $q$ even | $r=2$ | $r=3$ | $r=4$ | $r=5$ | $r=6$
---|---|---|---|---|---
Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS), $\mathbf{\forall}h\geq 1$ | $\mathbf{2^{8}}$ | $2^{4}$ | $\mathbf{2^{12}}$ | $2^{4}$ | $\mathbf{2^{16}}$ | $2^{4}$ | $\mathbf{2^{15}}$ | $2^{3}$ | $\mathbf{2^{18}}$ | $2^{3}$
MDS, $h=2$ | $2^{8}$ | $2^{2}$ | $2^{12}$ | $2^{2}$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
MDS, $h=3$ | $2^{12}$ | $2^{18}$ | $\mathbf{2^{12}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
MDS, $h=4$ | $2^{16}$ |  | $2^{24}$ |  | $\mathbf{2^{16}}$ |  | $2^{20}$ |  | $2^{24}$ |
Hamming, $\rho=3$, $h=2$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $2^{12}$ | $2$ | $2^{15}$ | $2$ | $2^{18}$ | $2$
Pr. BCH, $s=1,2$, $h=2$ | $\mathbf{2^{6}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
Pr. BCH, $s=1,2$, $h=3$ | $2^{10}$ | $2^{15}$ | $\mathbf{2^{12}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
Pr. BCH, $s=1,2$, $h=4$ | $2^{14}$ |  | $2^{21}$ |  | $\mathbf{2^{16}}$ |  | $2^{20}$ |  | $2^{24}$ |
Best MRD code possible, $\mathbf{\forall}h\geq 1$ | $2^{30}$ | $2$ | $2^{30}$ | $2$ | $2^{30}$ | $2$ | $2^{30}$ | $2$ | $2^{30}$ | $2$
Table 8: Table for fixed $N=gr=30$, while other parameters vary.  Table for $N=gr=62$, $q$ even | $r=2$ | $r=3$ | $r=4$ | $r=5$ | $r=6$
---|---|---|---|---|---
Code $\mathcal{C}_{\boldsymbol{\gamma}}$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$ | $q^{m}$ | $q$
Trivial $\mathcal{C}_{\boldsymbol{\gamma}}=\\{0\\}$ (Lin. RS), $\mathbf{\forall}h\geq 1$ | $\mathbf{2^{10}}$ | $2^{5}$ | $\mathbf{2^{15}}$ | $2^{5}$ | $\mathbf{2^{20}}$ | $2^{5}$ | $\mathbf{2^{20}}$ | $2^{4}$ | $\mathbf{2^{24}}$ | $2^{4}$
MDS, $h=2$ | $\mathbf{2^{8}}$ | $2^{2}$ | $2^{12}$ | $2^{2}$ | $2^{16}$ | $2^{2}$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
MDS, $h=3$ | $2^{12}$ | $2^{18}$ | $2^{24}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
MDS, $h=4$ | $2^{16}$ |  | $2^{24}$ |  | $2^{32}$ |  | $\mathbf{2^{20}}$ |  | $\mathbf{2^{24}}$ |
Hamming, $\rho=3$, $h=2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $\mathbf{2^{12}}$ | $2$ | $2^{15}$ | $2$ | $2^{18}$ | $2$
Pr. BCH, $s=1,2,3$, $h=2$ | $\mathbf{2^{8}}$ | $2$ | $\mathbf{2^{9}}$ | $2$ | $\mathbf{2^{12}}$ | $2$ | $\mathbf{2^{10}}$ | $2$ | $\mathbf{2^{12}}$ | $2$
Pr. BCH, $s=1,2,3$, $h=3$ | $2^{14}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{20}}$ | $\mathbf{2^{15}}$ | $\mathbf{2^{18}}$
Pr. BCH, $s=1,2,3$, $h=4$ | $2^{20}$ |  | $2^{21}$ |  | $2^{28}$ |  | $\mathbf{2^{20}}$ |  | $\mathbf{2^{24}}$ |