Row Reduction Applied to Decoding of Rank Metric and Subspace Codes

We show that decoding of $\mathrm{\ell }$-Interleaved Gabidulin codes, as well as list-$\mathrm{\ell }$ decoding of Mahdavifar–Vardy codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of $\text{F}[x]$ matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding $\mathrm{\ell }$-Interleaved Gabidulin codes. We obtain an algorithm with complexity $O(\mathrm{\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 perform the interpolation step of list-$\mathrm{\ell }$-decoding Mahdavifar–Vardy codes in complexity $O(\mathrm{\ell }{n}^2)$, where $n$ is the number of interpolation constraints.