Row Reduction Applied to Decoding of Rank Metric and Subspace Codes

We show that error and erasure decoding of $\ell$-Interleaved Gabidulin codes, as well as list-$\ell$ decoding of Mahdavifar--Vardy codes can be solved by row reducing skew polynomial matrices. Inspired by row reduction of $\mathbb{F}[x]$ matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into certain normal forms. We apply this to solve generalised shift register problems, or Pad\'e approximations, over skew polynomial rings, which occur in error and erasure decoding $\ell$-Interleaved Gabidulin codes. We obtain an algorithm with complexity $O(\ell \mu^2)$ where $\mu$ measures the size of the input problem and is proportional to the code length $n$ in the case of decoding. Further, we show how to list-$\ell$ decode Mahdavifar--Vardy subspace codes in $O(\ell r^2 m^2)$ time, where $m$ is a parameter proportional to the dimension of the codewords' ambient space and $r$ is the dimension of the received subspace.