Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio

In this paper, we mainly focus on the rank distance, which is defined to be the rank of the difference between two matrices $A,B\in {𝔽}_q^{m\times n}$ i.e., $d(A,B):=\mathrm{rank}(A-B)$. In what follows, $d(\cdot ,\cdot )$ refers to the rank distance. For $\rho \in [0,1]$, a code $C\subseteq {\mathrm{\Sigma }}^n$ over an alphabet $\mathrm{\Sigma }$ is said to be $(\rho ,\mathrm{\ell })$-list decodable if for any $𝒚\in {𝔽}_q^n$, it holds that

where $d(𝒙,𝒚)$ denotes the distance between $𝒙$ and $𝒚$. Here, $\rho$ is called the list decoding radius, and $\mathrm{\ell }$ is called the list size. The stronger notion of $(\rho ,\mathrm{\ell })$-average-radius list decodability is defined in the same way, except that we replace the maximum of the distances $d({𝒄}_i,𝒚)$ by the average of these distances. The formal definition is given as follows.

In [24], Shangguan and Tamo proved the generalized Singleton bound for list decoding, generalizing the classical Singleton bound for unique decoding. For linear codes, this generalized Singleton bound states that if $C\subseteq {𝔽}_q^n$ is an $[n,k]$-linear code that is $(\rho ,\mathrm{\ell })$-list decodable in the Hamming metric, then it holds that $\rho \le \frac{\mathrm{\ell }}{\mathrm{\ell }+1}\left(1-\frac{k}{n}\right)$. In [12], they noted that this generalized Singleton bound also holds for rank-metric codes.

They further showed that this bound is tight for rank-metric codes by proving that random Gabidulin codes attain it with high probability. (This is a nontrivial task; in fact, even proving that random linear rank-metric codes attain the generalized Singleton bound is far from obvious.) However, the column-to-row ratio of these codes is quite small, which makes them less appealing for practical applications.

In this paper, we prove that there exist Gabidulin codes with constant column-to-row ratio $\mathrm{\Omega }(\epsilon )$ that are list decodable up to the radius $\frac{\mathrm{\ell }}{\mathrm{\ell }+1}(1-\frac{k}{n}-\epsilon )$.

Complementing this result, we also show that the column-to-row ratio is at most $O(\epsilon )$ for any rank-metric code that is average-radius list decodable up to the generalized Singleton bound. Thus, our results are essentially tight.

Our proof is inspired by [13]. To explain our proof, we first briefly review the techniques in [13]. In [13], they proposed the notion of a reduced intersection matrix, whose kernel corresponds to the list of codewords. Let $C$ be an $[n,k]$ linear code and $G$ be its generator matrix, which is a $k\times n$ matrix. Given $\mathrm{\ell }+1$ distinct codewords ${𝒄}_1,\mathrm{\dots },{𝒄}_{\mathrm{\ell }+1}$ with ${𝒄}_i={𝒙}_{i}G=(c_{i1},\mathrm{\dots },c_{in})$ that are close to a vector $𝒚=(y_1,\mathrm{\dots },y_n)$, where the coordinates $c_{ij}$ and $y_j$ are in the alphabet $𝔽$, we define the intersection index set $I_j:=\{h\in [n]:y_h=c_{jh}\}$. For a subset $J\subseteq [n]$, let $G_J$ (resp. ${𝒚}_J$) be the submatrix (resp. subvector) of $G$ (resp. $𝒚$) formed by the columns (resp. components) with indices in $J$. Then, we have ${𝒚}_{I_i}-{𝒙}_i{G}_{I_i}=0$. If $a\in I_i\cap I_j$, then $({𝒙}_i-{𝒙}_j)G_a=0$. This means that for each element in $I_i\cap I_j$, we can establish a linear equation. Since these $\mathrm{\ell }+1$ codewords are very close to $𝒚$, it is expected that we can obtain many equations of the form $({𝒙}_i-{𝒙}_j)G_a=0$. By removing the linear dependence of these equations, we obtain a reduced intersection matrix $R_{G,I_{[\mathrm{\ell }]}}$ such that $({𝒙}_2-{𝒙}_1,\mathrm{\dots },{𝒙}_{\mathrm{\ell }+1}-{𝒙}_1)R_{G,I_{[\mathrm{\ell }]}}=0$, where $I_{[\mathrm{\ell }]}$ is a shorthand for the tuple $(I_1,\mathrm{\dots },I_n)$. On the other hand, if $R_{G,I_{[\mathrm{\ell }]}}$ has full rank, then we cannot find $\mathrm{\ell }+1$ distinct codewords that are close to a vector $𝒚$ and thus $C$ is list decodable. Thus, the essence of their paper is to investigate the full rankness of $R_{G,I_{[\mathrm{\ell }]}}$.

In this paper, we investigate the list decodability of rank-metric codes, where distance is measured using the rank metric rather than the Hamming metric. Thus, we cannot construct the reduced intersection matrix $R_{G,I_{[\mathrm{\ell }]}}$ row by row as in [13]. Instead, we present another construction of a reduced intersection matrix, which captures the property of the rank distance. Let us first represent the codeword of our rank-metric code as a vector $𝒄\in {𝔽}^n$ where $𝔽$ is the extension field of ${𝔽}_q$. This is done by fixing an ${𝔽}_q$-linear isomorphism $𝔽\cong {𝔽}_q^{[𝔽:{𝔽}_q]}$. The rank distance between two codewords $d({𝒄}_1,{𝒄}_2)$ is the maximum number of ${𝔽}_q$-linear independent components in ${𝒄}_1-{𝒄}_2$. One can find the precise definition in Section 2. Similar to Hamming codes, a linear rank-metric code has a generator matrix $G$ and each codeword can be encoded as $𝒄=𝒙G$. Given two vectors ${𝒚}_1,{𝒚}_2\in {𝔽}^n$ with rank distance $d$, we can find a $(n-d)\times n$ matrix $A$ over ${𝔽}_q$ of full rank such that $A{({𝒚}_1-{𝒚}_2)}^{\top }=0$. The major difference between the rank metric and the Hamming metric is that for each vector $𝒗$ that lies in the vector space spanned by the rows in $A$, we always have $𝒗{({𝒚}_1-{𝒚}_2)}^{\top }=0$. Thus, we cannot include all $𝒗$ in our equations. Instead, we include $A$ as a whole.

With this observation in mind, we present our new reduced intersection matrix. Assume distinct codewords ${𝒄}_1,\mathrm{\dots },{𝒄}_{\mathrm{\ell }+1}$ with ${𝒄}_i={𝒙}_{i}G$ are close to a vector $𝒚=(y_1,\mathrm{\dots },y_n)$. Assume that $d(𝒚,{𝒙}_{i}G)=a_i$ and there exists an $a_i\times n$ matrix $A_i$ of full rank over ${𝔽}_q$ such that $A_i{(𝒚-{𝒙}_{i}G)}^{\top }=0$. By replacing $𝒚$ with $𝒚-{𝒙}_{1}G$ and ${𝒙}_i={𝒙}_i-{𝒙}_1$, we have $A_1{𝒚}^{\top }=0$ and $A_i{(𝒚-{𝒙}_{i}G)}^{\top }=0$. Let $𝒱=(V_1,\mathrm{\dots },V_{\mathrm{\ell }+1})$ where $V_i$ is the vector space spanned by the rows in $A_i$.²²2In our analysis, we need to consider ${𝒱}_{[t]}=(V_1,\mathrm{\dots },V_t)$ for $t=1,\mathrm{\dots },\mathrm{\ell }+1$. Here, we only consider ${𝒱}_{[\mathrm{\ell }+1]}$ for simplicity. Then, we construct a reduced intersection matrix $R_{G,𝒱}$ to represent all these relations as $R_{G,𝒱}{(𝒚,{𝒙}_2,\mathrm{\dots },{𝒙}_{\mathrm{\ell }+1})}^{\top }=0$ which can be found in (9). If $R_{G,𝒱}$ has full rank, which means that we cannot find such $\mathrm{\ell }+1$ distinct codewords, then our rank-metric code is list decodable. Thus, it suffices to study the rank of $R_{G,𝒱}$. If our decoding radius is slightly off the generalized Singleton bound (with a gap of $\epsilon$), then $R_{G,𝒱}$ is not square. This makes the full rank condition easier to meet.

We restrict $G$ to a subspace $V$ by defining $G_V$ to be the column space of $GA$ where the columns of $A$ span $V$. This can be seen as a generalization of puncturing in the Hamming metric. By introducing a subspace $V$, we obtain a submatrix $R_{G,𝒱}^V$ of $R_{G,𝒱}$ by restricting $G$ to $V$. Using results from [12], we show that if $G$ is a symbolic Gabidulin code (see Definition 15), then the submatrix $R_{G,𝒱}^V$ is invertible and has the same rank as $R_{G,𝒱}$ when the dimension of $V$ is not too small, i.e., $dim(V)\ge n-\frac{\lambda k}{\mathrm{\ell }}$, where $\lambda >0$ is a small parameter depending on $\epsilon$. This means if each variable of this symbolic Gabidulin code is chosen uniformly at random, with high probability, $R_{G,𝒱}^V$ has full rank. To show that a Gabidulin code is list decodable, we need to enumerate all possible $t$-tuples $(V_1,\mathrm{\dots },V_t)$ for $t=1,\mathrm{\dots },\mathrm{\ell }+1$ and take a union bound over all these tuples. Thus, we need to show that $R_{G,𝒱}$ is of full rank with high probability $1-\exp (\mathrm{\Omega }(-n^2))$ for each $𝒱$. To do this, we borrow the idea of [13] to bound the failure probability.

Let us briefly review the idea of our algorithm. Let ${𝒆}_1,\mathrm{\dots },{𝒆}_n$ be a standard basis of ${𝔽}_q^n$. We first fix a non-singular maximal square submatrix $W$ of $R_{G,𝒱}$. The reason we need a square submatrix is that it is easy to calculate the determinant of $W$ to bound the failure probability that $W$ is non-singular. Initially, since $G$ is the generator matrix of a symbolic Gabidulin code, $W$ is a nonsingular matrix. If $W$ remains non-singular with the assignment $X_1={\alpha }_1,\mathrm{\dots },X_n={\alpha }_n$, we are done. Otherwise, we face the situation where $M$ is non-singular under the partial assignment $X_1={\alpha }_1,\mathrm{\dots },X_{j-1}={\alpha }_{j-1}$ but becomes singular under $X_1={\alpha }_1,\mathrm{\dots },X_j={\alpha }_j$. In this case, we call $j$ a faulty index and remove the corresponding columns from the generator matrix $G$. Then, we come to the submatrix $R_{G,𝒱}^V$ for some subspace $V=\text{span}\{{𝒆}_i:i\in [n]/\{j\}\}$. Note that we have already shown that $R_{G,𝒱}^V$ has full rank if $V$ has large dimension. Then, we find a new maximal square submatrix $W$ of $R_{G,𝒱}^V$ and continue the argument. We show that, with high probability, there are not too many faulty indices, which implies that we can finally find a maximal square submatrix $W$ that has full rank under the assignment. This means $R_{G,𝒱}$ has full rank, completing the proof.

Complementing our positive result, we also show that a capacity-achieving list decodable rank-metric code must satisfy $m=\mathrm{\Omega }(n/\epsilon )$. Our proof generalizes the proof in [1] in the rank-metric case. In particular, we first fix a subspace $V_0\subseteq {𝔽}_{q^m}^n$ of dimension $b=4\epsilon n$ and let ${\overline{V}}_0$ be a complement of $V_0$. Then, we construct a collection $ℱ$ of subspaces of dimension $R-\epsilon$ in ${\overline{V}}_0$, where $R$ is the rate of our rank-metric code. For any two subspaces $V_1,V_2\in ℱ$, $dim(V_1+V_2)\ge (R+\epsilon )n$. We manage to show that $ℱ$ has a large size. Using a probabilistic argument, we find a codeword $M$ in the rank-metric code $C$ such that for most subspaces $V\in ℱ$, there is a corresponding codeword $M_V$ in $C$ satisfying the condition that the kernel of $M-M_V$ contains $V$. Since the number of such subspaces is greater than $\mathrm{\ell }{q}^{4\epsilon n}$, by the pigeonhole principle, we can find $\mathrm{\ell }$ distinct codewords $M_{V_1},\mathrm{\dots }{M}_{V_{\mathrm{\ell }}}$ such that the kernel of $M-M_{V_i}$ also contains $V_0$. Then, we show that these $\mathrm{\ell }+1$ codewords $M,M_{V_1},\mathrm{\dots }{M}_{V_{\mathrm{\ell }}}$ are contained in a ball of small radius in the rank metric. This implies an upper bound on the list decoding radius, thus completing the proof.

${𝔽}_q^n$ is a vector space of dimension $n$ over ${𝔽}_q$. We denote by $𝒙$ a row vector in ${𝔽}_q^n$ and ${𝒙}^{\top }$ a column vector. Let ${𝒆}_1,\mathrm{\dots },{𝒆}_n$ be the standard basis of ${𝔽}_q^n$. Given a matrix $A\in {𝔽}_q^{m\times n}$, we denote by $⟨A⟩$ the subspace spanned by the column vectors in $A$. For a $t$-tuple ${𝒱}_{[t]}=(V_1,\mathrm{\dots },V_t)$ and $J\subseteq [t]$, define ${𝒱}_J={(V_i)}_{i\in J}$.

We first review some basic facts and results about rank-metric codes. The rank distance $d(A,B)$ between two matrices $A,B\in {𝔽}_q^{m\times n}$ is defined to be the rank of $A-B$, i.e., $d(A,B):=\mathrm{rank}(A-B)$. Indeed, this defines a distance [8]. A rank-metric code $C$ is a subset of ${𝔽}_q^{m\times n}$ whose rate and minimum distance are given by

Without loss of generality, we always assume that $m\ge n$, since otherwise we can exchange $n$ and $m$. It is convenient to treat an $m\times n$ matrix $A$ over ${𝔽}_q$ as a vector $𝒗=(v_1,\mathrm{\dots },v_n)\in {𝔽}_{q^m}^n$ by identifying ${𝔽}_q^m$ with ${𝔽}_{q^m}$ (by fixing a basis of ${𝔽}_{q^m}$) and viewing each column of $A$ as an element in ${𝔽}_{q^m}$. Then, we have $\mathrm{rank}(A)={dim}_{{𝔽}_q}({\mathrm{span}}_{{𝔽}_q}\{v_1,\mathrm{\dots },v_n\})$. In this way, a rank-metric code $C$ may be viewed as a subset of ${𝔽}_{q^m}^n$, and we can study linear rank-metric codes, i.e, codes that are ${𝔽}_{q^m}$-subspaces.

For $G\in {𝔽}^{k\times n}$ over an extension field $𝔽/{𝔽}_q$, $A\in {𝔽}_q^{n\times d}$, and $V=⟨A⟩\subseteq {𝔽}_q^n$, define $G_V\subseteq {𝔽}^n$ to be the column space of $GA$. The following results on the list decoding of symbolic Gabidulin codes can be found (implicitly) in [12].