TY - GEN

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

AU - Bartz, Hannes

AU - Jerkovits, Thomas

AU - Puchinger, Sven

AU - Rosenkilde, Johan

N1 - Publisher Copyright:
© 2019 IEEE.

PY - 2019/8

Y1 - 2019/8

N2 - 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(n1635) 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).

AB - 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(n1635) 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).

KW - Interleaved Gabidulin Codes

KW - Interpolation-Based Decoding

KW - Order Bases

KW - Rank-Metric Codes

KW - Root Finding

UR - http://www.scopus.com/inward/record.url?scp=85081107853&partnerID=8YFLogxK

U2 - 10.1109/ITW44776.2019.8989290

DO - 10.1109/ITW44776.2019.8989290

M3 - Conference contribution

AN - SCOPUS:85081107853

T3 - 2019 IEEE Information Theory Workshop, ITW 2019

BT - 2019 IEEE Information Theory Workshop, ITW 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE Information Theory Workshop, ITW 2019

Y2 - 25 August 2019 through 28 August 2019

ER -