Row reduction applied to decoding of rank-metric and subspace codes

DOI10.1007/S10623-016-0257-9MaRDI QIDQ510489zbMATH OpenOpenAlexFDO

Authors Sven Puchinger, Johan Rosenkilde né Nielsen, V. R. Sidorenko, Wenhui Li

Publication date 10 February 2017

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.04728

zbMATH Keywords

Gabidulin codesskew polynomialsrow reductionMahdavifar-Vardy codesmodule minimisationshift register synthesis

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05) Skew fields, division rings (12E15)

Abstract: We show that decoding of $ell$-Interleaved Gabidulin codes, as well as list-$ell$ decoding of Mahdavifar--Vardy codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of $F[x]$ matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding $ell$-Interleaved Gabidulin codes. We obtain an algorithm with complexity $O(ellm{u}^2)$ where $mu$ measures the size of the input problem and is proportional to the code length $n$ in the case of decoding. Further, we show how to perform the interpolation step of list-$ell$-decoding Mahdavifar--Vardy codes in complexity $O(ell{n}^2)$, where $n$ is the number of interpolation constraints.

Recommendations

• Decoding interleaved Gabidulin codes using Alekhnovich's algorithm
• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases
• Fast decoding of Gabidulin codes
• List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
• Algebraic decoding of folded Gabidulin codes

Cites work

• scientific article; zbMATH DE number 3711820 (Why is no real title available?)
• scientific article; zbMATH DE number 3785096 (Why is no real title available?)
• scientific article; zbMATH DE number 1461545 (Why is no real title available?)
• scientific article; zbMATH DE number 2151192 (Why is no real title available?)
• scientific article; zbMATH DE number 822685 (Why is no real title available?)
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• A computational view on normal forms of matrices of Ore polynomials
• A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes
• A linear algebraic approach to multisequence shift-register synthesis
• Algebraic List-Decoding of Subspace Codes
• An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations
• Bilinear forms over a finite field, with applications to coding theory
• Bounds on List Decoding of Rank-Metric Codes
• DIEUDONNÉ DETERMINANTS FOR SKEW POLYNOMIAL RINGS
• Decoding interleaved Gabidulin codes using Alekhnovich's algorithm
• Efficient algorithms for order basis computation
• Efficient decoding of Reed-Solomon codes beyond half the minimum distance
• Evading subspaces over large fields and explicit list-decodable rank-metric codes
• Factoring multivariate polynomials over finite fields
• Fast operations on linearized polynomials and their applications in coding theory
• Fast skew-feedback shift-register synthesis
• Fraction-free row reduction of matrices of Ore polynomials.
• Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them
• Les déterminants sur un corps non commutatif
• Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
• Linear codes using skew polynomials with automorphisms and derivations
• Linearized Polynomial Interpolation and Its Applications
• List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
• List decoding of Reed-Solomon codes from a Gröbner basis perspective
• Maximum-rank array codes and their application to crisscross error correction
• On lattice reduction for polynomial matrices
• On solutions of linear functional systems
• On transform-domain error and erasure correction by Gabidulin codes
• Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes
• Sub-Quadratic Decoding of One-Point Hermitian Codes
• Theory of codes with maximum rank distance
• Theory of non-commutative polynomials

Cited in

(6)

• Decoding interleaved Gabidulin codes using Alekhnovich's algorithm
• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases
• Fast decoding of lifted interleaved linearized Reed-Solomon codes for multishot network coding
• On decoding high-order interleaved sum-rank-metric codes
• Rank-metric codes and their applications
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory

This page was built for publication: Row reduction applied to decoding of rank-metric and subspace codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510489)