Skip to Main content Skip to Navigation
Conference papers

Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation

Abstract : 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, or Padé approximations , over skew polynomial rings which occur in error and erasure decoding of l-Interleaved Gabidulin codes. We obtain an algorithm with complexity O(l µ^2) where µ measures the size of the input problem. The approach uses a flexible module description, inspired by recent advances in decoding of Reed–Solomon codes, which could potentially be applied to other skew polynomial problems.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Jean-Pierre Tillich <>
Submitted on : Thursday, February 18, 2016 - 1:28:18 PM
Last modification on : Friday, April 30, 2021 - 9:59:37 AM
Long-term archiving on: : Saturday, November 12, 2016 - 11:10:39 PM


Files produced by the author(s)


  • HAL Id : hal-01275870, version 1


W Li, J.S.R 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-01275870⟩



Record views


Files downloads