Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

Abstract

We prove that Alekhnovich's algorithm can be used for row reduction of skew polynomial matrices. This yields an $O({\ell }^3{n}^{(\omega +1)/2}\log (n))$ decoding algorithm for $\ell$-Interleaved Gabidulin codes of length $n$, where $\omega$ is the matrix multiplication exponent, improving in the exponent of $n$ compared to previous results.

6 pages, presented at the International Workshop on Algebraic and Combinatorial Coding Theory (ACCT) 2016, submitted to Electronic Notes in Discrete Mathematics (volume devoted to ACCT 2016)