Algebraic decoding of folded Gabidulin codes

Abstract

An efficient interpolation-based decoding algorithm for $h$-folded Gabidulin codes is presented that can correct rank errors beyond half the minimum rank distance for any code rate $0\le R\le 1$. The algorithm serves as a list decoder or as a probabilistic unique decoder and improves upon existing schemes, especially for high code rates. A probabilistic unique decoder with adjustable decoding radius is presented. The decoder outputs a unique solution with high probability and requires at most $\mathcal {O}({s^2n^2})$ operations in $\mathbb {F}_{q^m}$, where $1\le s\le h$ is a decoding parameter and $n\le m$ is the length of the unfolded code over $\mathbb {F}_{q^m}$. An upper bound on the average list size of folded Gabidulin codes and on the decoding failure probability of the decoder is given. Applying the ideas to a list decoding algorithm by Mahdavifar and Vardy (List-decoding of subspace codes and rank-metric codes up to Singleton bound, ISIT 2012) improves the performance when used as probabilistic unique decoder and gives an upper bound on the failure probability.

1 Introduction

Decoding schemes for folded Gabidulin codes were independently introduced in [13] and [10]. Both constructions allow to correct rank errors up to the Singleton bound in rank-metric for very small code rates.

We present a new interpolation-based decoding algorithm for folded Gabidulin codes that can correct rank errors beyond half the minimum rank distance for any code rate. This scheme can be used as a list decoder which outputs a list of all codewords up to the decoding radius. Although the worst-case list size of this approach is exponential in the length of the code, we show that the decoder returns a list of size one with high probability. This allows to use the scheme as a probabilistic unique decoder that outputs a unique solution by allowing a very low failure probability. We present a probabilistic unique decoding algorithm with adjustable decoding radius that allows to further reduce the failure probability by backing off the decoding radius.

We compare our results for folded Gabidulin codes with punctured (or interleaved) Gabidulin codes. Punctured Gabidulin codes with probabilistic unique decoding were proposed in [12, 16] and [19]. These decoding algorithms achieve the best known decoding radius close to the Singleton bound by allowing decoding failures with small probability. Later in [9] a list decoding algorithm for punctured Gabidulin codes was suggested, which has the same decoding radius when the list size is allowed to be exponential in the code length. An explicit construction and a list decoding algorithm for punctured Gabidulin codes was presented in [8]. The output of this decoder is a basis for the affine subspace containing all candidate messages, which is a large list with high probability.

This paper is structured as follows. In Sect. 2, we describe the notation and give basic definitions. Section 3 explains the ideas of our interpolation-based decoding algorithm for folded Gabidulin codes and shows the improvements upon existing schemes for high code rates. In Sect. 4, we show how the interpolation-based decoder can be used for list and probabilistic unique decoding of folded Gabidulin codes. Section 5 describes how these results apply to the decoding scheme by Mahdavifar and Vardy [13]. Section 6 concludes this paper.

Part of this work was presented at the International Workshop on Coding and Cryptography (WCC), Apr. 2015, Paris, France [1]. In this paper we give detailed proofs and extend the results to probabilistic unique decoding of low-rate folded Gabidulin codes.

2 Preliminaries

2.1 Finite fields and matrices

Let q be a power of a prime, denote by $\mathbb {F}_{q}$ the finite field of order q and by $\mathbb {F}_{q^m}$ its extension field of degree m. Vectors and matrices are denoted by bold lowercase and uppercase letters such as $\mathbf {a}$ and $\mathbf {A}$ and their elements are indexed beginning from zero. We denote the rank and the kernel of a matrix $\mathbf {A} \in \mathbb {F}_{q}^{m \times n}$ over $\mathbb {F}_{q}$ by ${{\mathrm{rk}}}(\mathbf {A})$ and $\ker (\mathbf {A})$, respectively. There is a bijective mapping between any row vector $\mathbf {a} \in \mathbb {F}_{q^m}^n$ and a matrix $\mathbf {A} \in \mathbb {F}_{q}^{m \times n}$ under any fixed basis of $\mathbb {F}_{q^m}$ over $\mathbb {F}_{q}$. The rank of a row vector $\mathbf {a}\in \mathbb {F}_{q^m}^n$ is defined as ${{\mathrm{rk}}}(\mathbf {a})={{\mathrm{rk}}}(\mathbf {A})$ where $\mathbf {A} \in \mathbb {F}_{q}^{m \times n}$ is the corresponding matrix over $\mathbb {F}_{q}$. By $[a,b]$ we denote the set of integers $\{a,a+1,\dots ,b\}$.

2.2 Linearized polynomials

For any element $\alpha \in \mathbb {F}_{q^m}$ and any integer i let $\alpha ^{[i]}\overset{{{\mathrm{def}}}}{=}\alpha ^{q^{i}}$ be the Frobenius power of $\alpha$. A nonzero polynomial of the form

$$\begin{aligned} p(x)=\sum _{i=0}^{l}p_ix^{[i]} \end{aligned}$$

(1)

with $p_i\in \mathbb {F}_{q^m}$, $p_l\ne 0$, is called a linearized polynomial of q-degree $\deg _q(p(x))=l$, see [11, 15]. The set of all roots of p(x) is an $\mathbb {F}_{q}$-linear subspace of $\mathbb {F}_{q^m}$. A linearized polynomial of q-degree l can have at most l linearly independent roots in $\mathbb {F}_{q^m}$, i.e., a root space of dimension at most l. If the dimension of the root space of a linearized polynomial p(x) equals the q-degree $\deg _q(p(x))$ we call it a minimal linearized polynomial for this root space. The evaluation of a linearized polynomial forms a linear map over $\mathbb {F}_{q}$, i.e., for all $a,b\in \mathbb {F}_{q}$ and $x_1,x_2\in \mathbb {F}_{q^m}$, we have

$$\begin{aligned} p(ax_1+bx_2)=ap(x_1)+bp(x_2). \end{aligned}$$

(2)

The noncommutative composition

$$\begin{aligned} p^{(1)}(x)\otimes p^{(2)}(x)\overset{{{\mathrm{def}}}}{=}p^{(1)}(p^{(2)}(x)) \end{aligned}$$

of two linearized polynomials $p^{(1)}(x)$ and $p^{(2)}(x)$ of q-degree $d_1$ and $d_2$ is a linearized polynomial of q-degree $d_1+d_2$. The set of all linearized polynomials over $\mathbb {F}_{q^m}$ forms a noncommutative ring $\mathbb {L}_{q^m}\![x]$ with identity under addition “+” and composition “$\otimes$”. We denote the set of all linearized polynomials from $\mathbb {L}_{q^m}\![x]$ with q-degree less than k by $\mathbb {L}_{q^m}\![x]_{<k}$.

Lemma 1

The set $\mathbb {L}_{q^m}\![x]_{<k}$ forms a commutative group under addition “+”.

Proof

The coefficients of every linearized polynomial of degree at most $k-1$ can be written as a vector of length k over $\mathbb {F}_{q^m}$. The addition of polynomials is equivalent to the addition of the coefficient vectors over the field and the statement of the lemma follows. $\square$

The Moorematrix of a vector $\mathbf {a}=(a_0 \ a_1 \ \dots \ a_{n-1})\in \mathbb {F}_{q^m}^n$ is defined as

$$\begin{aligned} \mathbf {M}_{r}( \mathbf {a} )= \begin{pmatrix} a_{0} &{} a_{1} &{} \dots &{} a_{n-1}\\ a_{0}^{[1]} &{} a_{1}^{[1]} &{} \dots &{} a_{n-1}^{[1]}\\ \vdots &{}\vdots &{}\ddots &{} \vdots \\ a_{0}^{[r-1]} &{} a_{1}^{[r-1]} &{} \dots &{} a_{n-1}^{[r-1]}\\ \end{pmatrix}. \end{aligned}$$

(3)

The rank of $\mathbf {M}_{r}( \mathbf {a} )$ is $\min \{r,n\}$ if the elements $a_0,\dots ,a_{n-1}$ are linearly independent over $\mathbb {F}_{q}$, see [11].

2.3 (Folded) Gabidulin codes

A rank-metric code $\mathcal {C}$ of length $N$ is a set of $M\times N$ matrices over $\mathbb {F}_{q}$. Each codeword of $\mathcal {C}$ can be represented by a vector of length $N$ over $\mathbb {F}_{q^M}$. The minimum rank distance d of $\mathcal {C}$ is defined as

$$\begin{aligned} d = \min _{\mathbf {x},\mathbf {y} \in \mathcal {C},\mathbf {x}\ne \mathbf {y}} d_r(\mathbf {x}, \mathbf {y}) \overset{{{\mathrm{def}}}}{=}\min _{\mathbf {x},\mathbf {y} \in \mathcal {C},\mathbf {x}\ne \mathbf {y}} {{\mathrm{rk}}}(\mathbf {X}-\mathbf {Y}) \end{aligned}$$

(4)

where $\mathbf {X},\mathbf {Y}$ are the matrix representations of $\mathbf {x},\mathbf {y}\in \mathcal {C}$ over $\mathbb {F}_{q}$. If $\mathcal {C}$ forms a group under addition over $\mathbb {F}_{q}$ we have $\mathbf {X}'=\mathbf {X}-\mathbf {Y}\in \mathcal {C}\setminus \{\mathbf {0}\}$ for $\mathbf {X}\ne \mathbf {Y}$ and get

$$\begin{aligned} d&= \min _{\mathbf {x},\mathbf {y} \in \mathcal {C},\mathbf {x}\ne \mathbf {y}} {{\mathrm{rk}}}(\mathbf {X}-\mathbf {Y}) = \min _{\mathbf {x}' \in \mathcal {C}\setminus \{\mathbf {0}\}} {{\mathrm{rk}}}(\mathbf {X'}). \end{aligned}$$

In this case the minimum distance corresponds to the minimum rank of a nonzero codeword in $\mathcal {C}$.

Denote by $\mathcal {B}^{(t)}(\mathbf {Y})$ a ball of radius $t$ in rank-metric around a matrix $\mathbf {Y}$ containing all matrices lying within rank distance at most $t$ from $\mathbf {Y}$. The volume $|\mathcal {B}^{(t)}(\mathbf {Y})|$ is independent of the center $\mathbf {Y}$ (see e.g., [6]).

The Singleton-like bound for rank-metric codes states that

$$\begin{aligned} |\mathcal {C}|&\le \left( q^M\right) ^{N-d+1} \nonumber \\ \Longleftrightarrow \qquad d&\le N-\log _{q^M}\left( |\mathcal {C}|\right) +1. \end{aligned}$$

(5)

if $M \ge N$, see [4, 5].

Codes which fulfill this bound with equality are called maximum rank distance (MRD) codes. A special class of MRD codes are Gabidulin codes [4, 5], which are the analogs of Reed–Solomon codes in rank-metric. As channel model we use the rank error channel

$$\begin{aligned} \mathbf {Y}=\mathbf {C}+\mathbf {E}. \end{aligned}$$

(6)

For fixed $t={{\mathrm{rk}}}(\mathbf {E})$ the error matrix $\mathbf {E}$ is assumed to be uniformly distributed over all $M\times N$ matrices of rank $t$ over $\mathbb {F}_{q}$.

Folded Gabidulin codes were proposed independently in [13] and [10]. In [10] the coefficients of the message polynomial are restricted to belong to a subfield of $\mathbb {F}_{q^m}$. In this work we consider folded Gabidulin codes as defined in [13].

Definition 1

(h-folded Gabidulin code) Let $\{\alpha ^0,\alpha ^1,\dots ,\alpha ^{n-1}\}\subset \mathbb {F}_{q^m}$ with $n\le m$ be linearly independent over $\mathbb {F}_{q}$ called code locators. Let $h$ be a positive integer that divides n and let $N=n/h$. An $h$-folded Gabidulin code ${\mathrm {F}}{\mathrm {Gab}}[h;n,k]$ of length $N$, dimension k is defined as

$$\begin{aligned} \left\{ \left( \begin{bmatrix} f(\alpha ^0) \\ f(\alpha ^1) \\ \vdots \\ f(\alpha ^{h-1}) \\ \end{bmatrix}, \begin{bmatrix} f(\alpha ^h) \\ f(\alpha ^{h+1}) \\ \vdots \\ f(\alpha ^{2h-1}) \\ \end{bmatrix},\dots , \begin{bmatrix} f(\alpha ^{n-h}) \\ f(\alpha ^{n-h+1}) \\ \vdots \\ f(\alpha ^{n-1}) \\ \end{bmatrix}\right) : f(x)\in \mathbb {L}_{q^m}\![x]_{<k}\right\} . \end{aligned}$$

(7)

A codeword of an h-folded Gabidulin code is a matrix $\mathbf {c}\in \mathbb {F}_{q^m}^{h\times N}$ or $\mathbf {C}\in \mathbb {F}_{q}^{hm \times N}$ where each element of $\mathbb {F}_{q^m}$ is written as a column vector of length m over $\mathbb {F}_{q}$. The jth column of $\mathbf {c}$ is

$$\begin{aligned} \mathbf {c}_j=\left( f(\alpha ^{jh}) \dots f(\alpha ^{(j+1)h-1})\right) ^T \end{aligned}$$

and can be seen as an element of the field $\mathbb {F}_{q^{hm}}$ for $j\in [0,N-1]$. Folded Gabidulin codes are codes of length $N$ over a large field $\mathbb {F}_{q^M}=\mathbb {F}_{q^{hm}}$ that can be decoded over the small field $\mathbb {F}_{q^m}$. An $h$-folded Gabidulin code is a nonlinear code over $\mathbb {F}_{q^{hm}}$ since for any $a,b\in \mathbb {F}_{q^{hm}}$ and any $\mathbf {c},\mathbf {c}'\in \mathcal {C}$ the $\mathbb {F}_{q^{hm}}$-linear combination $a\mathbf {c}+b\mathbf {c}'$ is not necessarily contained in $\mathcal {C}$. A folded Gabidulin code is $\mathbb {F}_{q^m}$-linear since the unfolded code is an $\mathbb {F}_{q^m}$-linear subspace of $\mathbb {F}_{q^m}^n$. This also implies that the code is linear over $\mathbb {F}_{q}$.

The number of codewords in $\mathcal {C}$ is $|\mathcal {C}|=q^{mk}$. The code rate of a folded Gabidulin code is the same as the code rate of the unfolded code [13], i.e.,

$$\begin{aligned} R=\frac{\log _{q^{hm}}\left( |\mathcal {C}|\right) }{N}=\frac{k}{n}. \end{aligned}$$

The following theorem shows that folded Gabidulin codes are MRD codes if and only if $h$ divides k.

Theorem 1

The minimum rank distance of an $h$-folded Gabidulin code $\mathcal {C}$ with parameters $n,k,h,N=\frac{n}{h}$ is $d=N-\lceil \frac{k}{h}\rceil +1$.

Proof

An $h$-folded Gabidulin code forms a group under addition since $\mathbb {L}_{q^m}\![x]_{<k}$ forms an additive group over $\mathbb {F}_{q^m}$ by Lemma 1. Thus the minimum distance of the code is given by the minimum rank of a nonzero codeword, i.e.,

$$\begin{aligned} d = \min _{\mathbf {c} \in \mathcal {C}^*} {{\mathrm{rk}}}(\mathbf {C}) \end{aligned}$$

where $\mathcal {C}^*\overset{{{\mathrm{def}}}}{=}\mathcal {C}\setminus \{\mathbf {0}\}$. Let $\mathbf {C}\in \mathcal {C}^*$ be a codeword generated by the evaluation of $f(x)\in \mathbb {L}_{q^m}\![x]_{<k}$ at the code locators $\{\alpha _0,\alpha _1,\dots ,\alpha _{n-1}\}$. Since $N\le hm$ we have ${{\mathrm{rk}}}(\mathbf {C})\le N$. If the column rank of $\mathbf {C}$ is

$$\begin{aligned} {{\mathrm{rk}}}(\mathbf {C})=N-z \end{aligned}$$

then by $\mathbb {F}_{q}$-elementary column operations (Gaussian elimination) we will get $\mathbf {C}'$ with z zero columns and $N-z$ linearly independent columns. From (2) it follows that $\mathbf {C}'$ is generated by the evaluation of f(x) at the new code locators $\alpha _i'$ that are obtained from $\alpha _i$ by $\mathbb {F}_{q}$-elementary operations for all $i\in [0,n-1]$. Thus the new code locators $\{\alpha _0',\alpha _1'\dots ,\alpha _{n-1}'\}$ are linearly independent and we have $f(\alpha _i')=0$ for all $i\in [0,n-1]$ at most $k-1$ times. Hence the number of zero columns z in $\mathbf {C}'$ satisfies

$$\begin{aligned} z\le \Big \lfloor \frac{k-1}{h}\Big \rfloor =\Big \lceil \frac{k}{h}\Big \rceil -1 \end{aligned}$$

(8)

and

$$\begin{aligned} d= \min _{\mathbf {c} \in \mathcal {C}^*} {{\mathrm{rk}}}(\mathbf {C})\ge N-\Big \lceil \frac{k}{h}\Big \rceil +1. \end{aligned}$$

(9)

From the Singleton bound (5) we have

$$\begin{aligned} \log _{q^{hm}} q^{mk}&\le N-d+1 \nonumber \\ \Longleftrightarrow \quad d&\le N-\frac{k}{h}+1. \end{aligned}$$

(10)

Combining (9) and (10) we get

$$\begin{aligned} N-\Big \lceil \frac{k}{h}\Big \rceil +1\le d \le N-\frac{k}{h}+1 \end{aligned}$$

(11)

and the statement of the theorem follows, since d is an integer. $\square$

Thus folded Gabidulin codes fulfill the Singleton bound (5) with equality (i.e., are MRD codes) if and only if $h$ divides k. If h does not divide k then the code has still the best minimum distance for the given parameters $N,k$ and $h$ but the size of the code book could be larger in this case.

3 Improved interpolation-based decoding of high-rate folded Gabidulin codes

The interpolation-based list decoding algorithm for folded Gabidulin codes by Mahdavifar and Vardy in [13] is closely related to the list decoding algorithm for folded Reed–Solomon codes by Guruswami and Rudra [7] and Vadhan [17]. The normalized decoding radius $\tau _\text {MV}=t/N$ of this decoder is

$$\begin{aligned} \tau _\text {MV}<\frac{s}{s+1}\left( 1-\frac{h}{h-s+1}R\right) \end{aligned}$$

(12)

where the integer $1\le s\le h$ is a decoding parameter. For $s\approx \sqrt{h}$ a normalized decoding radius $\tau _\text {MV}<1-R-\epsilon$ with $\epsilon =1/2s$ can be achieved (see [13, Theorem 12]). Observe that $\tau _\text {MV}$ is positive if $R<\frac{h-s+1}{h}$. Thus the decoder in [13] cannot correct any errors for code rates larger than $\frac{h-s+1}{h}$ (or $1-\frac{\sqrt{h}-1}{h}$ for $s=\sqrt{h}$). But many applications require high-rate codes.

In this section we present an improved list decoding scheme that can correct errors beyond the unique decoding radius d / 2 for any code rate $R>0$. The scheme is motivated by Justesen’s idea for decoding folded Reed–Solomon codes [7, Sec. III-B] and improves upon [13] for high code rates.

Our decoding scheme consists of an interpolation step and a root-finding step. In comparison with [13] the code construction remains the same (Definition 1) but the set of interpolation points in the interpolation step is chosen differently.

3.1 Interpolation step

Suppose we receive a matrix

$$\begin{aligned} \mathbf {y}= \left( \begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{h-1} \\ \end{bmatrix}, \begin{bmatrix} y_{h} \\ y_{h+1} \\ \vdots \\ y_{2h-1} \\ \end{bmatrix},\dots , \begin{bmatrix} y_{n-h} \\ y_{n-h+1} \\ \vdots \\ y_{n-1} \\ \end{bmatrix} \right) = \mathbf {c}+\mathbf {e} \end{aligned}$$

(13)

where $\mathbf {e}=\left( \mathbf {e}_0^T,\mathbf {e}_1^T,\dots ,\mathbf {e}_{N-1}^T\right) \in \mathbb {F}_{q^m}^{h\times N}$ with row vectors $\mathbf {e}_j\in \mathbb {F}_{q^m}^h$. The error matrix over $\mathbb {F}_{q}$ is denoted by $\mathbf {E}=\left( \mathbf {E}_0^T,\mathbf {E}_1^T,\dots ,\mathbf {E}_{N-1}^T\right) \in \mathbb {F}_{q}^{hm\times N}$ with $\mathbf {E}_j\in \mathbb {F}_{q}^{hm}$. Denote by

$$\begin{aligned} \mathbf {y}_j=(y_{jh} \ y_{jh+1} \dots y_{(j+1)h-1})^T\in \mathbb {F}_{q^m}^h\end{aligned}$$

the jth column of $\mathbf {y}$ for $j\in [0,N-1]$. The code locators in Definition 1 are consecutive powers of a primitive element $\alpha \in \mathbb {F}_{q^m}$ and thus form a polynomial basis over $\mathbb {F}_{q}$. This allows to use $(s+1)$-dimensional interpolation points of the form

$$\begin{aligned} \left( \alpha ^i, y_i,y_{i+1},\dots ,y_{i+s-1}\right) , \qquad i\in [0,n-s]. \end{aligned}$$

In other words, the received symbols $\mathbf {y}_j$ of the received matrix $\mathbf {y}$ in (13) are sampled using a sliding window of size $s$. The choice of the interpolation points is crucial for the performance of the decoder.

In [13] each $(s+1)$-dimensional interpolation point only contains values strictly chosen from one received symbol $\mathbf {y}_j,j\in [0,N-1]$ resulting in $h-s+1$ interpolation points per received symbol. Instead of using only $h-s+1$ interpolation points per received symbol $\mathbf {y}_j$, we “overlap” to the neighboring symbol to get $h$ interpolation points per symbol. Since $\alpha ^n\ne \alpha ^0$ and $f(\alpha ^n)\ne f(\alpha ^0)$, we cannot “exceed” the last received symbol $\mathbf {y}_{N-1}$ and wrap around to the first code symbol $\mathbf {y}_{0}$. Thus we can use only $h-s+1$ interpolation points for the last symbol. In total we get $Nh-(s-1)$ interpolation points. In the interpolation step we must solve the following problem.

Problem 1

Given an integer $s\in [1,h]$ and a degree constraint $D$, find a nonzero $(s+1)$-variate linearized polynomial of the form

$$\begin{aligned} Q\left( x,y_1,\dots ,y_s\right) = Q_0(x) + Q_1(y_1) + \dots + Q_s(y_s) \end{aligned}$$

(14)

which satisfies the following conditions:

• $Q(\alpha ^{jh+i},y_{jh+i},y_{jh+i+1},\dots ,y_{jh+i+s-1}) = 0$, $\forall i \in [0,h-1], j \in [0,N-2]$,

• $Q(\alpha ^{n-h+i},y_{n-h+i},y_{n-h+i+1},\dots ,y_{n-h+i+s-1}) = 0$, $\forall i \in [0,h-s]$,

• $\deg _q(Q_0(x)) < D$,

• $\deg _q(Q_\ell (y_\ell ))< D-(k-1)$, $\forall \ell \in [1,s]$.

The following example illustrates the choice of the interpolation points in Problem 1.

Example 1

(Interpolation Step) Suppose we transmit a codeword of a folded Gabidulin code with parameters $N=4$ and $h=3$ over a rank error channel (6) and we receive a matrix

$$\begin{aligned} \mathbf {y}= \left( \begin{bmatrix} y_{0} \\ y_{1} \\ y_{2} \end{bmatrix}, \begin{bmatrix} y_{3} \\ y_{4} \\ y_{5} \\ \end{bmatrix}, \begin{bmatrix} y_{6} \\ y_{7} \\ y_{8} \\ \end{bmatrix}, \begin{bmatrix} y_{9} \\ y_{10} \\ y_{11} \\ \end{bmatrix} \right) . \end{aligned}$$

Denote by $\mathcal {I}_\text {HR}$ and $\mathcal {I}_\text {MV}$ the set of interpolation points for the improved high-rate decoder (Problem 1) and the Mahdavifar–Vardy decoder in [13], respectively. For decoding parameter $s=2$ we have the following sets of interpolation points:

$$\begin{aligned} \begin{aligned} \mathcal {I}_\text {HR}=\big \{&(\alpha ^0,y_0,y_1),(\alpha ^1,y_1,y_2),(\alpha ^2,y_2,y_3),\\&(\alpha ^3,y_3,y_4),(\alpha ^4,y_4,y_5),(\alpha ^5,y_5,y_6),\\&(\alpha ^6,y_6,y_7),(\alpha ^7,y_7,y_8),(\alpha ^8,y_8,y_9),\\&(\alpha ^9,y_9,y_{10}),(\alpha ^{10},y_{10},y_{11})\big \} \end{aligned} \qquad \begin{aligned} \mathcal {I}_\text {MV}=\big \{&(\alpha ^0,y_0,y_1),(\alpha ^1,y_1,y_2),\\&(\alpha ^3,y_3,y_4),(\alpha ^4,y_4,y_5),\\&(\alpha ^6,y_6,y_7),(\alpha ^7,y_7,y_8),\\&(\alpha ^9,y_9,y_{10}),(\alpha ^{10},y_{10},y_{11})\big \}. \end{aligned} \end{aligned}$$

The improved high-rate decoder uses the interpolation points from the set $\mathcal {I}_\text {MV}$ plus three additional interpolation points that wrap around to the neighboring symbols.

A solution to Problem 1 can be found by solving a homogeneous linear system of equations. Denote the component polynomials of (14) by

$$\begin{aligned} Q_0(x)=\sum _{j=0}^{D-1}q_{0,j}x^{[j]}, \qquad Q_\ell (y_\ell )=\sum _{j=0}^{D-k}q_{\ell ,j}y_\ell ^{[j]}, \qquad \forall \ell \in [1,s]. \end{aligned}$$

Let the matrix $\mathbf {T}$ contain all $Nh-(s-1)$ interpolation points from Problem 1 as rows and denote by $\mathbf {t}_\ell$ the $\ell$th column of $\mathbf {T}$ for $\ell \in [0,s]$. The coefficients of (14) can be found by solving the homogeneous linear system of equations

$$\begin{aligned} \mathbf {R}\cdot \mathbf {q}_I^T=\mathbf {0} \end{aligned}$$

(15)

where $\mathbf {R}$ is an $Nh-(s-1) \times D(s+1)-s(k-1)$ matrix

$$\begin{aligned} \mathbf {R}=\Big (\mathbf {M}_{D}( \mathbf {t}_{0}^T )^T,\mathbf {M}_{D-k+1}( \mathbf {t}_{1}^T )^T,\dots ,\mathbf {M}_{D-k+1}( \mathbf {t}_{s}^T )^T\Big ) \end{aligned}$$

(16)

and

$$\begin{aligned} \mathbf {q}_I=\left( q_{0,0},\dots ,q_{0,D-1} \ | \ q_{1,0},\dots ,q_{1,D-k} \ | \ \dots \ | \ q_{s,0},\dots ,q_{s,D-k}\right) . \end{aligned}$$

(17)

Lemma 2

A nonzero polynomial fulfilling the interpolation constraints in Problem 1 exists if

$$\begin{aligned} D=\Bigg \lceil \frac{Nh-2(s-1)+sk}{s+1}\Bigg \rceil . \end{aligned}$$

(18)

Proof

Problem 1 forms a homogeneous system of $Nh-(s-1)$ equations in $D(s+1)-s(k-1)$ unknowns. This system has a nonzero solution if the number of conditions is less than the number of unknowns, i.e., if

$$\begin{aligned} Nh-(s-1)< D(s+1)-s(k-1) \quad \Longleftrightarrow \quad D\ge \frac{Nh-2(s-1)+sk}{s+1}. \end{aligned}$$

(19)

$\square$

We define a univariate polynomial $P(x)\in \mathbb {L}_{q^m}\![x]$ as

$$\begin{aligned} P(x)\overset{{{\mathrm{def}}}}{=}Q(x,f(x),f(\alpha x),\dots , f(\alpha ^{s-1} x))=Q_0(x)+\sum _{\ell =1}^{s}Q_\ell (f(\alpha ^{\ell -1}x)) \end{aligned}$$

(20)

where $f(x)\in \mathbb {L}_{q^m}\![x]_{<k}$.

Lemma 3

Let ${{\mathrm{rk}}}\left( \mathbf {e}_0^T,\mathbf {e}_1^T,\dots ,\mathbf {e}_{N-1}^T\right) =t$. Then the linearized polynomial P(x) in (20) has at least $Nh-(s-1)-t(h+s-1)$ linearly independent roots in $\mathbb {F}_{q^m}$.

Proof

Since $Q(x,y_1,\dots ,y_s)$ is a linearized polynomial we can perform $\mathbb {F}_{q}$-elementary operations on the set of interpolation points from Problem 1 without affecting its root space. Then by $\mathbb {F}_{q}$-elementary operations on the set of interpolation points we can have at most $t(h+s-1)$ interpolation points that are corrupted by the rank errors and at least $Nh-(s-1)-t(h+s-1)$ interpolation points of the form

$$\begin{aligned} \left( \beta _j,f(\beta _j),f(\alpha \beta _j),\dots ,f(\alpha ^{s-1}\beta _j)\right) \end{aligned}$$

for all $j\in [0,Nh-s-t(h+s-1)]$ that are not corrupted by rank errors. The elements $\beta _j\in \mathbb {F}_{q^m}$ are obtained by $\mathbb {F}_{q}$-elementary operations on the code locators $\alpha ^0,\dots ,\alpha ^{n-1}$ and thus linearly independent over $\mathbb {F}_{q}$. From the interpolation constraints in Problem 1 we have

$$\begin{aligned} Q\left( \beta _j,f(\beta _j),f(\alpha \beta _j),\dots ,f(\alpha ^{s-1}\beta _j)\right) = P(\beta _j)=0 \end{aligned}$$

for all $j\in [0,Nh-s-t(h+s-1)]$ which implies that P(x) has at least $Nh-(s-1)-t(h+s-1)$ linearly independent roots in $\mathbb {F}_{q^m}$. $\square$

The result of Lemma 3 is illustrated in Example 2 in the Appendix. The decoding radius for the improved high-rate decoder is expressed as follows.

Theorem 2

Let $Q\left( x,y_1,\dots ,y_s\right) \ne 0$ fulfill the interpolation constraints in Problem 1. If the rank of the error matrix $t={{\mathrm{rk}}}(\mathbf {E})$ satisfies

$$\begin{aligned} t<\frac{s}{s+1}\left( \frac{Nh-k-(s-2)}{h+s-1}\right) \end{aligned}$$

(21)

then

$$\begin{aligned} P(x) = Q(x,f(x),f(\alpha x),\dots , f(\alpha ^{s-1} x))=0. \end{aligned}$$

(22)

Proof

By Lemma 3 the polynomial P(x) has at least $Nh-(s-1)-t(h+s-1)$ linearly independent roots in $\mathbb {F}_{q^m}$. If we choose

$$\begin{aligned} D\le Nh-(s-1)-t(h+s-1) \end{aligned}$$

(23)

then P(x) has more linearly independent roots than its degree which is only fulfilled if $P(x)=0$. Combining (19) and (23) we obtain

$$\begin{aligned} Nh-(s-1)+s(k-1)&< (s+1)(Nh-(s-1)-t(h+s-1))\\ \Longleftrightarrow \quad t&< \frac{s}{s+1}\left( \frac{Nh-k-(s-2)}{h+s-1}\right) . \end{aligned}$$

$\square$

The normalized decoding radius $\tau _{HR}=t/N$ for the improved high-rate decoding approach is

$$\begin{aligned} \tau _{HR}<\frac{s}{s+1}\cdot \frac{h}{h+s-1}\left( 1-R\right) -\frac{s(s-2)}{N(s+1)(h+s-1)}. \end{aligned}$$

(24)

The “termination loss” $\frac{s(s-2)}{N(s+1)(h+s-1)}$ is caused by the reduced number of interpolation points for the last symbol (no wrap around to the first symbol). The term vanishes with order $1/N$ for large $N$ and $h$ while keeping $s<<h$.

Lemma 4

The optimal decoding parameter $s$ for $N\rightarrow \infty$ is $s_\text {opt}=\sqrt{h-1}$.

Proof

For $N\rightarrow \infty$ the “termination loss” $\frac{s(s-2)}{N(s+1)(h+s-1)}$ vanishes. In order to maximize the decoding radius choose $s$ such that

$$\begin{aligned} \frac{d}{ds}\tau _{HR}(s,h)&= \frac{d}{d s}\left( \frac{s}{s+1}\cdot \frac{h}{h+s-1}(1-R)\right) \\&= -\frac{(s^2h- h^2+h)}{(s^2+sh+h-1)^2}(1-R) \mathop {=}\limits ^{!} 0. \end{aligned}$$

This is fulfilled for $s= \pm \sqrt{h-1}$ and since $1\le s\le h$ we have $s_{\text {opt}}=\sqrt{h-1}$.

$\square$

For the optimal decoding parameter $s_{opt}=\sqrt{h-1}$ and for $N\rightarrow \infty$ we get the maximum normalized decoding radius

$$\begin{aligned} \tau _{HR}^*\approx \frac{h}{2\sqrt{h-1}+h}(1-R). \end{aligned}$$

(25)

3.2 Root-finding step

In the root-finding step we must find all polynomials $f(x)\in \mathbb {L}_{q^m}\![x]_{<k}$ that are a solution to (22). This corresponds to solving a linear system of equations. Define the polynomial P(x) as in (20) and define the polynomials

$$\begin{aligned} B_i(x)=q_{1,i} + q_{2,i}x + \dots + q_{s,i}x^{s-1} \end{aligned}$$

for $i\in [0,k-1]$. The ith coefficient $p_i$ of P(x) is then equal to

$$\begin{aligned} p_i&=q_{0,i}+f_iB_0(\alpha ^{[i]}) + f_{i-1}^{[1]}B_1(\alpha ^{[i]}) + \dots + f_0^{[i]}B_i(\alpha ^{[i]}). \end{aligned}$$

The solution space of the interpolation system (15) can have dimension larger than one in general. In this case there exists a set of $\mathbb {F}_{q^m}$-linearly independent linearized polynomials with coefficients from $\mathbb {F}_{q^m}$ that are a solution to Problem 1. Similar to [2, 19] we use a basis for the solution space of (15) to increase the probability that the root-finding system has full rank. We now lower bound the dimension of the solution space of (15).

Lemma 5

Let ${{\mathrm{rk}}}(\mathbf {E})=t$. Then the dimension $d_I$ of the solution space of the interpolation system (15) is at least $s(D-k+1)-t(h+s-1)$.

Proof

The first $D$ columns of $\mathbf {R}$ form an $N(h+s-1)\times D$ Moore matrix $\mathbf {M}_{D}( \mathbf {t}_0^T )^T$ of rank $D$ since the elements in $\mathbf {t_0}$ are linearly independent and $D<Nh-(s-1)$. The matrices $\mathbf {M}_{D-k+1}( \mathbf {t}_1^T )^T\dots \,\mathbf {M}_{D-k+1}( \mathbf {t}_s^T )^T$ are linear combinations of the columns of $\mathbf {M}_{D}( \mathbf {t}_0^T )^T$ and thus do not increase the rank. Thus the rank of $\mathbf {R}$ only depends on $D$ and the rank of the error matrix $\mathbf {E}$. By Lemma 3 an error of rank $t$ affects at most $t(h+s-1)$ interpolation points and thus increases the rank of $\mathbf {R}$ by at most $t(h+s-1)$ since $t(h+s-1)<D(s+1)-s(k-1)$. Hence we have ${{\mathrm{rk}}}(\mathbf {R})\le D+t(h+s-1)$. The dimension of the solution space of the interpolation system (15) is

$$\begin{aligned} d_I\overset{{{\mathrm{def}}}}{=}\dim \ker (\mathbf {R})&\ge D(s+1)-s(k-1)-{{\mathrm{rk}}}(\mathbf {R})\\&=s(D-k+1)-t(h+s-1). \end{aligned}$$

$\square$

We now set up the root-finding system using $d_I$ polynomials. Define the polynomials

$$\begin{aligned} B_i^{(\ell )}(x)=q_{1,i}^{(\ell )}+q_{2,i}^{(\ell )}x+q_{3,i}^{(\ell )}x^2+\dots +q_{s,i}^{(\ell )}x^{s-1} \end{aligned}$$

for $\ell \in [1,d_I]$ and the vectors

$$\begin{aligned} \mathbf {b}_{i,j}=\left( B_i^{(1)}(\alpha ^{[j]}) \ B_i^{(2)}(\alpha ^{[j]}) \ \dots \ B_i^{(d_I)}(\alpha ^{[j]})\right) ^T \end{aligned}$$

and $\mathbf {q}_{0,i}=\left( q_{0,i}^{(1)} \ q_{0,i}^{(2)} \ \dots \ q_{0,i}^{(d_I)}\right) ^T$ for $i,j\in [0,k-1]$. Defining the root-finding matrix

$$\begin{aligned} \mathbf {B}= \begin{pmatrix} \mathbf {b}_{0,0} &{} &{} &{} \\ \mathbf {b}_{1,1}^{[-1]} &{} \mathbf {b}_{0,1}^{[-1]} &{} &{} \\ \vdots &{} \dots &{} \ddots &{} \\ \mathbf {b}_{k-1,k-1}^{[-(k-1)]} &{} \mathbf {b}_{k-2,k-1}^{[-(k-1)]} &{} \dots &{} \mathbf {b}_{0,k-1}^{[-(k-1)]} \end{pmatrix} \end{aligned}$$

(26)

and $\mathbf {q}=\left( \mathbf {q}_{0,0} \ \mathbf {q}_{0,1}^{[-1]} \dots \ \mathbf {q}_{0,k-1}^{[-(k-1)]}\right) ^T$, the coefficients of f(x) can be found by solving the truncated system

$$\begin{aligned} \mathbf {B}\cdot \mathbf {f}=-\mathbf {q} \end{aligned}$$

(27)

for $\mathbf {f}=\left( f_0 \ f_1^{[-1]} \ \dots \ f_{k-1}^{[-(k-1)]}\right) ^T$. The root-finding system (27) has always a solution if (21) holds since the transmitted message polynomial f(x) is a solution to (22) if t satisfies (21).

Proposition 1

Solving (27) requires at most $\mathcal {O}({k^2})$ operations in $\mathbb {F}_{q^m}$.

Proof

The $kd_I\times k$ matrix $\mathbf {B}$ has an upper block triangular structure. To solve (27) we only need one equation per $\mathbf {b}_{i,j}$ for $i,j\in [0,k-1]$ such that $B^{(\ell )}(\alpha ^{[j]})\ne 0$. Thus the system can be solved via back substitution requiring at most $\mathcal {O}({k^2})$ operations in $\mathbb {F}_{q^m}$. $\square$

4 List and unique decoding for high code rates

We show how to use the interpolation-based decoding principle from Sect. 3 as a list decoder or as a probabilistic unique decoder which returns a unique solution with (very) high probability.

4.1 List decoding for high code rates

The solution space of the root-finding system (27) is an affine subspace over $\mathbb {F}_{q}$. In case the root-finding system (27) is underdetermined, i.e., ${{\mathrm{rk}}}(\mathbf {B})<k$, we obtain a list of possible message polynomials f(x) which satisfy (22).

Lemma 6

The dimension of the $\mathbb {F}_{q}$-affine solution space of the root-finding system (27) is at most $m(s-1)$.

Proof

The root-finding matrix $\mathbf {B}$ has full rank if and only if all diagonal elements $\mathbf {b}_{0,0}, \dots , \mathbf {b}_{0,k-1}$ are nonzero vectors. The entries of each $\mathbf {b}_{0,i}$ are the evaluations of $d_I$ polynomials of degree at most $s-1$ at $\alpha ^{[i]},i\in [0,k-1]$. Since the conjugates $\alpha , \alpha ^{[1]},\dots ,\alpha ^{[k-1]}$ are all distinct and $\deg (B_0^{(\ell )}(x))<s$ for all $\ell \in [1,d_I]$, we can have $\mathbf {b}_{0,i}=\mathbf {0},i\in [0,k-1]$ at most $(s-1)$ times. For each $\mathbf {b}_{0,i}=\mathbf {0}, i\in [0,k-1]$ the coefficient $f_i$ can be any element in $\mathbb {F}_{q^m}$. Thus we have at most $q^{m(s-1)}$ solutions and the dimension of the $\mathbb {F}_{q}$-affine solution space is at most $m(s-1)$. $\square$

In the worst case the decoder outputs an exponential number of candidate message polynomials. Using more interpolation polynomials to solve the root-finding system does not reduce the worst case size of the list but helps to reduce the average list size.

We will now derive the average list size for folded Gabidulin codes using similar ideas as in [19] and [14].

Lemma 7

Let the $t$ fulfill (21). The average list size $\bar{L}_f(t)$ of an h-folded Gabidulin code C, i.e., the average number of codewords in any ball of radius t that contains a codeword, is then upper bounded by

$$\begin{aligned} \bar{L}_f(t)<1+4q^{-m(h(N- t)-k) + t(N-t)}. \end{aligned}$$

(28)

Proof

Let $\mathbf {Y}\in \mathbb {F}_{q}^{hm\times N}$ be a matrix chosen uniformly at random from all matrices in $\mathbb {F}_{q}^{hm\times N}$. The number of matrices lying within rank distance at most $t$ from $\mathbf {Y}$ in $\mathbb {F}_{q}^{hm\times N}$ is upper bounded by $|\mathcal {B}^{(t)}(\mathbf {Y})|<4q^{(mh+N)t-t^2}$ and independent of $\mathbf {Y}$ (see e.g., [18]). If $t$ satisfies (21) we know that the causal (transmitted) codeword is contained in $\mathcal {B}^{(t)}(\mathbf {Y})$. There are $q^{mk}-1$ noncausal codeword matrices out of $q^{mhN}$ possible matrices which can be in $\mathcal {B}^{(t)}(\mathbf {Y})$. Thus there are on average

$$\begin{aligned} \frac{q^{mk}-1}{q^{mhN}}\cdot |\mathcal {B}^{(t)}(\mathbf {Y})| <\frac{q^{mk}}{q^{mhN}}\cdot 4q^{(mh+N)t-t^2} =4q^{-m(h(N- t)-k) + t(N-t)} \end{aligned}$$

noncausal codewords in $\mathcal {B}^{(t)}(\mathbf {Y})$. Including the causal codeword we get (28). $\square$

4.2 A probabilistic unique decoder for high code rates

The interpolation-based decoding scheme from Sect. 3 can be used as a probabilistic unique decoder. The main idea behind this decoder is to output a unique solution or declare a decoding failure if the list size is larger than one. We will now show that in most cases we obtain a unique solution, i.e., a list of size one.

The root-finding system (22) has a unique solution if $\mathbf {B}$ has rank k which is fulfilled if and only if at least one entry of each $\mathbf {b}_{0,i},i\in [0,k-1]$ is nonzero.

Lemma 8

Denote by $d_I$ the dimension of the solution space of (15). The probability $P_e$ that $\mathbf {B}$ is singular is upper bounded by

$$\begin{aligned} P_e<k\left( \frac{k}{q^m}\right) ^{d_I}=k\left( \frac{k}{q^m}\right) ^{s(D-k+1)-t(h-s+1)} \end{aligned}$$

(29)

under the assumption that the coefficients of the polynomials $B_0^{(1)}(x),\dots ,B_0^{(d_I)}(x)$ are independent and uniformly distributed over $\mathbb {F}_{q^m}$.

Proof

Evaluating $B_0^{(\ell )}(x),\forall \ell \in [1,d_I]$ at the conjugates $\alpha ,\alpha ^{[1]},\dots ,\alpha ^{[k-1]}$ gives $\ell$ codewords of a $(k,s)$ Reed–Solomon code $\mathcal {C}_{RS}$. The triangular matrix $\mathbf {B}$ has rank k if the diagonal elements are nonzero, i.e., if we get at least one codeword of weight k. Under the assumption that the coefficients of $B_0^{(\ell )}(x),\ell \in [1,d_I]$ are uniformly distributed over $\mathbb {F}_{q^m}$ we get a uniform distribution over the code book of $\mathcal {C}_{RS}$. Using the approximation from [3, Equation 1] the probability $P_\text {s}$ to get a codeword of full weight k is

$$\begin{aligned} P_\text {s}&=\frac{\text {no. of weight } k \text { codewords}}{\text {total no. of codewords}}\approx \frac{\text {no. of weight }k\text { vectors in }\mathbb {F}_{q^m}^k}{\text {total no. of vectors in }\mathbb {F}_{q^m}^k}=\left( 1\!-\!\frac{1}{q^m}\right) ^k\!. \end{aligned}$$

The probability that one $B_i^{(\ell )}(\alpha ^{[j]})$ in $\mathbf {b}_{0,i}$ is zero is $1-P_\text {s}$. The coefficients of the polynomials $B_0^{(\ell )}(x), \ell \in [1,d_I]$ are independent by assumption and thus the entries of each $\mathbf {b}_{0,i}, i\in [0,k-1]$ also independent. The probability that $\mathbf {b}_{0,i}=\mathbf {0}, i\in [0,k-1]$ is upper bounded by

$$\begin{aligned} (1-P_\text {s})^{d_I}=\left( 1-\left( 1-\frac{1}{q^m}\right) ^k\right) ^{d_I}<\left( \frac{k}{q^m}\right) ^{d_I}. \end{aligned}$$

The probability that at least one $\mathbf {b}_{0,i}=\mathbf {0}$ for $i=0,\dots ,k-1$ is thus upper bounded by

$$\begin{aligned} P_e<\text {Pr}\left[ \bigcup _{i=0}^{k-1}\mathbf {b}_{0,i}=\mathbf {0}\right] \le \sum _{i=0}^{k-1} \left( \frac{k}{q^m}\right) ^{d_I} = k\left( \frac{k}{q^m}\right) ^{d_I}. \end{aligned}$$

$\square$

Equation (29) shows that using more polynomials to set up the root-finding system increases the probability that the root-finding matrix $\mathbf {B}$ has full rank, i.e., to get a unique solution. We now relate the dimension of the solution space $d_I$ to the decoding radius and the failure probability. The result is summarized in Theorem 3.

Theorem 3

Consider an $h$-folded Gabidulin code ${\mathrm {F}}{\mathrm {Gab}}[h;n,k]$. Let the coefficients of the polynomials $B_0^{(1)}(x),\dots ,B_0^{(d_I)}(x)$ be independent and uniformly distributed over $\mathbb {F}_{q^m}$. Let $\mu >0$ be an integer. If the rank of the error matrix $t={{\mathrm{rk}}}(\mathbf {E})$ satisfies

$$\begin{aligned} t\le \frac{s}{s+1}\left( \frac{Nh-k-(s-2)}{h+s-1}\right) -\frac{\mu }{(s+1)(h+s-1)} \end{aligned}$$

(30)

then we can find a unique solution f(x) satisfying (22) with probability at least

$$\begin{aligned} 1-k\left( \frac{k}{q^m}\right) ^\mu \end{aligned}$$

requiring at most $\mathcal {O}({s^2n^2})$ operations in $\mathbb {F}_{q^m}$.

Proof

We restrict the dimension of the solution space of the homogeneous interpolation system (15) to be larger than a threshold $\mu$, i.e., $d_I\ge \mu$, and get

$$\begin{aligned} \mu + t(h+s-1) + s(k-1) \le Ds. \end{aligned}$$

(31)

To ensure that f(x) is a root of P(x) in (22), the degree $D$ must satisfy (23). We combine (23) and (31) and get

$$\begin{aligned} \mu +t(h+s-1)+s(k-1)&\le s(Nh-(s-1)-t(h+s-1))\\ \Longleftrightarrow \quad t&\le \frac{s}{s+1}\left( \frac{Nh-k-(s-2)}{h+s-1}\right) -\frac{\mu }{(s+1)(h+s-1)}. \end{aligned}$$

The probability of getting a unique solution follows from Lemma 8. The overall complexity is dominated by the interpolation step, which can be solved for $\mu \le s$ by the efficient algorithm from [2] requiring at most $\mathcal {O}({s^2nD(h-s+1)})<\mathcal {O}({s^2n^2})$ operations in $\mathbb {F}_{q^m}$. $\square$

Theorem 3 shows that there is a tradeoff between the failure probability and the decoding radius. Note that for $\mu =1$ the decoding radius is equal to the list decoding radius (21). This is a major difference to decoding interleaved Gabidulin codes since probabilistic unique decoding of interleaved Gabidulin codes using only one interpolation polynomial to solve the root-finding system (i.e., $\mu =1$) is not possible.

The normalized decoding radius $\tau _u=t/N$ for the probabilistic unique decoder is

$$\begin{aligned} \tau _u \le \frac{s}{s+1}\cdot \frac{h}{h+s-1}(1-R)-\frac{s(s-2)+\mu }{N(s+1)(h+s-1)}. \end{aligned}$$

(32)

The decoding radius can be adjusted at the decoder by the choice of the maximum degree of the interpolation polynomials. Substituting (30) in (23) we obtain

$$\begin{aligned} D(s+1) \le Nh+s(k-2)+\mu +1 \end{aligned}$$

and choose the degree constraint $D$ for the unique decoder

$$\begin{aligned} D&= \frac{Nh+s(k-2)+\mu +1}{s+1}. \end{aligned}$$

The pseudo-code for the probabilistic unique decoding algorithm is given in Algorithm 1. The function InterpolateBasis($\cdot$) denotes the efficient interpolation algorithm from [2].

4.3 Performance analysis

We will compare the normalized decoding radius of the decoder from this section to the schemes in [9, 13] and [5]. The intersection point of the normalized decoding radii of the decoder in [13] (Mahdavifar–Vardy) and our improved high-rate decoder is

$$\begin{aligned} \tau _\text {MV}=\tau _\text {HR} \qquad \Longleftrightarrow \qquad R=\frac{((N+1)(s-1)-1)(h-s+1)}{2Nh(s-1)}. \end{aligned}$$

The high-rate decoder improves upon [13] for code rates $R\ge \frac{((N+1)(s-1)-1)(h-s+1)}{2Nh(s-1)}$ if the same decoding parameter $s$ is used for both decoding algorithms.

In Fig. 1 we consider a folded Gabidulin code with parameters $N=10$, $h=20$ and $s=6$. Figure 1 shows that the decoder in [13] (Mahdavifar–Vardy) cannot correct rank errors for code rates larger than $\frac{h-s+1}{h}=\frac{3}{4}$.

The decoder for punctured Gabidulin codes (different code construction) in [9] (Guruswami-Xing) has a larger decoding radius for all rates. Due to the structure of the root-finding system in [9] the decoder outputs a basis for all possible candidate polynomials, which is a large list with high probability. Thus this decoder cannot be used as a probabilistic unique decoder. The size of this list was reduced by pre-coding the coefficients of the message polynomials using hierarchical subspace evasive sets in [8] but is still exponential in the length of the code. Note that the code construction by Mahdavifar and Vardy and in this work is the same, whereas the code construction in [9] is different (i.e., no folded Gabidulin code).

Our improved high-rate decoder can correct rank errors for any code rate and will return a list of size one with high probability which is a major benefit for applications. Figure 1 shows that for the given code parameters the scheme improves upon [13] for $R\ge 0.405$ and that the termination loss is already negligible for a code of length $N=10$.

Fig. 1

The normalized decoding radius vs. the code rate R for folded Gabidulin codes with $N=10$, $h=20$ and decoding parameter $s=6$. For comparison we show the decoding radius for punctured Gabidulin codes (Color figure online)

In Fig. 2 the decoding radius for the optimal decoding parameters for each decoder is plotted. The presented decoding scheme improves upon [13] for $R>0.45$ for the given code parameters. The figure shows that using $h-s+1$ interpolation points per symbol that do not wrap around to neighboring symbols (Mahdavifar-Vardy) gives a better decoding performance for low code rates. The improved high-rate decoder uses $(s-1)$ additional interpolation points (i.e., $h$ interpolation points) per symbol (full wrap around) and performs better for high code rates. Using less than the maximum $(s-1)$ additional interpolation points per symbol that wrap around to the neighboring symbols (partial wrap around) did not improve the decoding radius for any code rate.

Fig. 2

The normalized decoding radius vs. the code rate R for folded Gabidulin codes with $N=10$, $h=20$ and optimal decoding parameter $s$ for each decoder (Color figure online)

4.4 Simulation results

Consider an $h$-folded Gabidulin code with parameters $m=n=12, k=5, h=3$ and $N=4$. For parameters $s=2$ and $\mu =1$ our decoder can correct $t=1$ rank errors. We simulated $10^{7}$ transmissions over a rank error channel (6) with $t=1$ and observed a fraction of $1.10\cdot 10^{-3}$ decoding failures (upper bound $6.10\cdot 10^{-3}$). For $\mu =2$ we simulated $3\cdot 10^{7}$ transmissions with $t=1$ and observed a fraction of $2.06\cdot 10^{-7}$ decoding failures (upper bound $7.45\cdot 10^{-6}$). The simulation results show, that the assumptions in the upper bound of that failure probability are reasonable. The average list size using Lemma 7 is upper bounded by $\bar{L}_f(t=1)<1+1.14\cdot 10^{-13}$ for the given code parameters.

5 Probabilistic unique decoding of low-rate folded Gabidulin codes

The structure of the root-finding system in the list decoding algorithm by Mahdavifar and Vardy [13] is the same as in our decoding algorithm. We now apply our ideas from Sect. 4 to the list decoding scheme in [13] and present a probabilistic unique decoding scheme for low-rate folded Gabidulin codes. The difference between the approach from Sect. 4 and the Mahdavifar and Vardy decoder is in the choice of the interpolation points. Each $(s+1)$-dimensional interpolation point only contains values strictly chosen from one received symbol $\mathbf {y}_j,j\in [0,N-1]$.

Problem 2

(MV Interpolation Problem) Given an integer $s\in [1,h]$ and a degree constraint $D$, find a nonzero $(s+1)$-variate linearized polynomial of the form

$$\begin{aligned} Q\left( x,y_1,\dots ,y_s\right) = Q_0(x) + Q_1(y_1) + \dots + Q_s(y_s) \end{aligned}$$

(33)

that satisfies the following conditions:

• $Q(\alpha ^{jh+i},y_{jh+i},y_{jh+i+1},\dots ,y_{jh+i+s-1}) = 0$, $\forall i \in [0,h-s], j \in [0,N-1]$,

• $\deg _q(Q_0(x)) < D$,

• $\deg _q(Q_\ell (y_\ell ))< D-(k-1)$, $\forall \ell \in [1,s]$.

Let the matrix $\mathbf {T}_\text {MV}$ contain all $N(h-s+1)$ interpolation points

$$\begin{aligned} \left( \alpha ^{jh+i},y_{jh+i},y_{jh+i+1},\dots ,y_{jh+i+s-1}\right) \end{aligned}$$

for all $i \in [0,h-s], j \in [0,N-1]$ from Problem 2 as rows and denote by $\mathbf {t}_{\text {MV},\ell }$ the $\ell$th column of $\mathbf {T}_\text {MV}$ for $\ell \in [0,s]$. The $N(h-s+1)\times (D(s+1)-s(k-1))$ interpolation-matrix $\mathbf {R}_\text {MV}$ is defined as

$$\begin{aligned} \mathbf {R}_\text {MV}=\left( \mathbf {M}_{D}( \mathbf {t}_{\text {MV},0}^T )^T, \mathbf {M}_{D-k+1}( \mathbf {t}_{\text {MV},1}^T )^T,\dots , \mathbf {M}_{D-k+1}( \mathbf {t}_{\text {MV},s}^T )^T\right) \end{aligned}$$

(34)

and the coefficient vector $\mathbf {q}_I$ is defined as in (17). The coefficients of the required polynomial can be found by solving the linear system

$$\begin{aligned} \mathbf {R}_\text {MV}\cdot \mathbf {q}_I^T=\mathbf {0}. \end{aligned}$$

(35)

In order to calculate the dimension of the solution space of (35) we first need to upper bound on the rank of $\mathbf {R}_\text {MV}$.

Lemma 9

Let ${{\mathrm{rk}}}(\mathbf {E})=t$. Then the dimension $d_I$ of the solution space of the interpolation system (35) is at least $s(D-k+1)-t(h-s+1)$.

Proof

By similar arguments as in the proof of Lemma 5 the rank of $\mathbf {R}_\text {MV}$ only depends on $D$ and the rank of the error matrix, i.e., ${{\mathrm{rk}}}(\mathbf {E})=t$. An error of rank $t$ corrupts at most $t(h-s+1)$ interpolation points and increases the rank of $\mathbf {R}_\text {MV}$ by at most $t(h-s+1)$, since $t(h-s+1)<D(s+1)-s(k-1)$. Hence we have ${{\mathrm{rk}}}(\mathbf {R}_\text {MV})\le D+t(h-s+1)$. The solution space of (35) has therefore dimension

$$\begin{aligned} d_I\overset{{{\mathrm{def}}}}{=}\dim \ker (\mathbf {R}_\text {MV})&\ge D(s+1)-s(k-1)-{{\mathrm{rk}}}(\mathbf {R}_\text {MV})\\&=s(D-k+1)-t(h-s+1). \end{aligned}$$

$\square$

Theorem 4

Consider an $h$-folded Gabidulin code ${\mathrm {F}}{\mathrm {Gab}}[h;n,k]$ and let the coefficients of the polynomials $B_0^{(1)}(x),\dots ,B_0^{(d_I)}(x)$ be independent and uniformly distributed over $\mathbb {F}_{q^m}$. If the rank of the error matrix $t={{\mathrm{rk}}}(\mathbf {E})$ satisfies

$$\begin{aligned} t\le \frac{s(N(h-s+1)-(k-1))-\mu }{(s+1)(h-s+1)} \end{aligned}$$

(36)

we can find a unique solution f (x) satisfying (22) with probability at least

$$\begin{aligned} 1-k\left( \frac{k}{q^m}\right) ^\mu \end{aligned}$$

requiring at most $\mathcal {O}({s^2n^2})$ operations in $\mathbb {F}_{q^m}$.

Proof

We restrict the dimension $d_I$ of the solution space of the interpolation system (35) to be larger than a threshold $\mu$, i.e., $\mu \le d_I$ and get

$$\begin{aligned} \mu&+t(h-s+1)+s(k-1)\le Ds. \end{aligned}$$

(37)

To ensure that f(x) is a root of P(x) in (22) the degree $D$ must satisfy (see [13, Corollary 9])

$$\begin{aligned} D\le (N-t)(h-s+1). \end{aligned}$$

(38)

Combining (37) and (38) we get

$$\begin{aligned} t&\le \frac{s(N(h-s+1)-(k-1))-\mu }{(s+1)(h-s+1)}. \end{aligned}$$

(39)

The failure probability follows from Lemma 8. For $\mu \le s$ the efficient interpolation algorithm from [2] can be used requiring at most $\mathcal {O}({s^2n^2})$ operations in $\mathbb {F}_{q^m}$. $\square$

The normalized decoding radius $\tau _{MV,u}=t/N$ is

$$\begin{aligned} \tau _{MV,u}\le \frac{s}{s+1}\left( 1-\frac{h}{h-s+1}R\right) -\frac{\mu -s}{N(s+1)(h-s+1)}. \end{aligned}$$

Substituting (39) in (38) we get the degree constraint

$$\begin{aligned} D&\le \frac{N(h-s+1)-s(k-1)+\mu }{s+1}. \end{aligned}$$

This allows to adjust the decoding radius at the decoder by choosing the maximum allowed degree of the interpolation polynomial. For the low-rate probabilistic unique decoder line 1 in Algorithm 1 has to be replaced by

6 Conclusion

We presented an interpolation-based decoding algorithm for $h$-folded Gabidulin codes that can correct rank errors beyond half the minimum rank distance for any code rate $0\le R\le 1$. The decoding performance is improved for high-rate codes which is a major benefit for applications. The scheme can be used as a list decoder or as a probabilistic unique decoder which outputs a unique solution with very high probability. We derived an upper bound on the average list size of folded Gabidulin codes and showed that probabilistic unique decoding of folded Gabidulin codes is possible. An efficient decoder with adjustable decoding radius was presented that allows to control the decoding radius vs. failure probability tradeoff. We applied the ideas for the root-finding step to a list decoding algorithm for low-rate folded Gabidulin codes by Mahdavifar and Vardy [13]. This improves the performance when used as probabilistic unique decoder and gives an upper bound on the failure probability.

Appendix

Example 2

(Root Space of Interpolation Polynomial) Suppose we transmit a codeword $\mathbf {c}$ of a folded Gabidulin code with parameters $N=5$ and $h=3$ and we receive

$$\begin{aligned} \mathbf {y}=\mathbf {c}+\mathbf {e}= \left( \begin{bmatrix} y_{0} \\ y_{1} \\ y_{2} \end{bmatrix}, \begin{bmatrix} y_{3} \\ y_{4} \\ y_{5} \\ \end{bmatrix}, \begin{bmatrix} y_{6} \\ y_{7} \\ y_{8} \\ \end{bmatrix}, \begin{bmatrix} y_{9} \\ y_{10} \\ y_{11} \\ \end{bmatrix}, \begin{bmatrix} y_{12} \\ y_{13} \\ y_{14} \\ \end{bmatrix} \right) \end{aligned}$$

where

$$\begin{aligned} \mathbf {e}= \left( \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} e_{1} \\ e_{2} \\ e_{3} \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}, \begin{bmatrix} e_{1} \\ e_{2} \\ e_{3} \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix} \right) \end{aligned}$$

with $t={{\mathrm{rk}}}(\mathbf {e})=1$. For decoding parameter $s=2$ the set of interpolation points from Problem 1 is

$$\begin{aligned} \mathcal {I}_\text {HR}=\Big \{&\big (\alpha ^{0},f(\alpha ^{0}),f(\alpha ^{1})\big ),&\big (\alpha ^{1},f(\alpha ^{1}),f(\alpha ^{2})\big ),&\big (\alpha ^{2},f(\alpha ^{2}),f(\alpha ^{3})+e_1\big ),\\&\big (\alpha ^{3},f(\alpha ^{3})+e_1,f(\alpha ^{4})+e_2\big ),&\big (\alpha ^{4},f(\alpha ^{4})+e_2,f(\alpha ^{5})+e_3\big ),&\big (\alpha ^{5},f(\alpha ^{5})+e_3,f(\alpha ^{6})\big ),\\&\big (\alpha ^{6},f(\alpha ^{6}),f(\alpha ^{7})\big ),&\big (\alpha ^{7},f(\alpha ^{7}),f(\alpha ^{8})\big ),&\big (\alpha ^{8},f(\alpha ^{8}),f(\alpha ^{9})+e_1\big ),\\&\big (\alpha ^{9},f(\alpha ^{9})+e_1,f(\alpha ^{10})+e_2\big ),&\big (\alpha ^{10},f(\alpha ^{10})+e_2,f(\alpha ^{11})+e_3\big ),&\big (\alpha ^{11},f(\alpha ^{11})+e_3,f(\alpha ^{12})\big ),\\&\big (\alpha ^{12},f(\alpha ^{12}),f(\alpha ^{13})\big ),&\big (\alpha ^{13},f(\alpha ^{13}),f(\alpha ^{14})\big ) \Big \}. \end{aligned}$$

By performing $\mathbb {F}_{q}$-elementary operations on $\mathcal {I}_\text {HR}$ we eliminate the errors from the interpolation points for the code locators $\alpha ^8,\alpha ^9,\dots ,\alpha ^{11}$ and get the noncorrupted interpolation points

$$\begin{aligned}&\big (\alpha ^{8}-\alpha ^{2},f(\alpha ^{8}-\alpha ^{2}),f(\alpha (\alpha ^{8}-\alpha ^{2}))\big ),&\big (\alpha ^{9}-\alpha ^3,f(\alpha ^{9}-\alpha ^3),f(\alpha (\alpha ^{9}-\alpha ^3))\big ),\\&\big (\alpha ^{10}-\alpha ^4,f(\alpha ^{10}-\alpha ^4),f(\alpha (\alpha ^{10}-\alpha ^4))\big ),&\big (\alpha ^{11}-\alpha ^5,f(\alpha ^{11}-\alpha ^5),f(\alpha (\alpha ^{11}-\alpha ^5))\big ). \end{aligned}$$

In total we have $t(h+s-1)=4$ interpolation points that are corrupted by errors and $Nh-(s-1)-t(h+s-1)=10$ noncorrupted interpolation points. The new code locators for the noncorrupted interpolations points are linearly independent over $\mathbb {F}_{q}$ and thus P(x) must have at least 10 linearly independent roots in $\mathbb {F}_{q^m}$.