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

Hannes Bartz, Thomas Jerkovits, Sven Puchinger, Johan Sebastian Heesemann Rosenkilde

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

59 Downloads (Pure)


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).
Original languageEnglish
Title of host publicationProceedings of IEEE Information Theory Workshop
Number of pages5
Publication date2020
ISBN (Electronic)978-1-5386-6900-6
Publication statusPublished - 2020
Event2019 IEEE Information Theory Workshop - Donners Event, Visby, Sweden
Duration: 25 Aug 201928 Aug 2019


Conference2019 IEEE Information Theory Workshop
LocationDonners Event
Internet address


  • Interleaved Gabidulin Codes
  • Interpolation Based Decoding
  • Order Bases
  • Rank-Metric Codes
  • Root Finding

Fingerprint Dive into the research topics of 'Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes'. Together they form a unique fingerprint.

Cite this