Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes

We show that the root-finding step in interpolation based decoding of interleaved Gabidulin codes can be solved by finding a so-called minimal approximant basis of a matrix over a linearized polynomial ring. Based on existing fast algorithms for computing such bases over ordinary polynomial rings, we develop fast algorithms for computing them over linearized polynomials. As a result, root finding costs O∼(`ωM(n)) operations in Fqm, where ` is the interleaving degree, n the code length, Fqm the base field of the code, 2 ≤ ω ≤ 3 the matrix multiplication exponent, and M(n) ∈ O(n1.635) is the complexity of multiplying two linearized polynomials of degree at most n. This is an asymptotic improvement upon the previously fastest algorithm of complexity O(`3n2), in some cases O(`2n2).