Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes
Hannes Bartz, Thomas Jerkovits, Sven Puchinger, Johan Rosenkilde · 2019
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).