Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation

2015/01/20 by Li, Wenhui, Nielsen, Johan S. R., Puchinger, Sven +1
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1501.04797

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 over skew polynomial rings which occur in error and erasure decoding of ℓ-Interleaved Gabidulin codes. The algorithm is based on module minimisation and has time complexity O(ℓ μ²) where μ measures the size of the input problem.

Related

• Row Reduction Applied to Decoding of Rank Metric and Subspace Codes
• Gabidulin Decoding via Minimal Bases of Linearized Polynomial Modules
• Efficient Decoding of Gabidulin Codes over Galois Rings
• General Linearized Polynomial Interpolation and Its Applications
• Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm