Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation

W Li (1) , Johan Sebastian Rosenkilde Nielsen (2) , S Puchinger (1) , V Sidorenko (1)

1 INT - University of Ulm. - Institute of Communications Engineering [Ulm]
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption

For many algebraic codes the main part of decoding can be reduced to a shift register synthesis problem. In this paper we present an approach for solving generalised shift register problems over skew polynomial rings which occur in error and erasure decoding of L-interleaved Gabidulin codes. The algorithm is based on module minimisation and has time complexity O(L*mu^2) where mu measures the size of the input problem.

Keywords: Skew Polynomials; Ore Polynomials; Shift Register Synthe-sis; Module Minimisation; Gabidulin Codes

Domains: Computer Science [cs]; Information Theory [cs.IT]

W Li, Johan Sebastian Rosenkilde Nielsen, S Puchinger, V Sidorenko. Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation. WCC2015 - 9th International Workshop on Coding and Cryptography 2015, Anne Canteaut, Gaëtan Leurent, Maria Naya-Plasencia, Apr 2015, Paris, France. ⟨hal-01245068⟩