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

Abstract

We show that the root-finding step in interpolationbased 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∼(l^wM(n)) operations in Fqm, where l is the interleaving degree, n the code length, Fqm the base field of the code, 2 ≤ w ≤ 3 the matrix multiplication exponent, and M(n) in O(n^1.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(l^3n^2), in some cases O(l^2n^2).