Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric

DOI10.1109/TIT.2021.3067318MaRDI QIDQ4958205zbMATH OpenOpenAlexFDO

Authors Hannes Bartz, Thomas Jerkovits, Sven Puchinger, Johan Rosenkilde

Publication date 7 September 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

decoding algorithmsinterleaved Gabidulin codes in rank metriclifted interleaved Gabidulin codes in subspace metriclinearized Reed-Solomon codes in sum-rank metric

Mathematics Subject Classification ID

Decoding (94B35)

Abstract: We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.

Cited in

(9)

• Fast dimension reduction using Rademacher series on dual BCH codes
• Rank-metric codes and their applications
• Codes in the sum-rank metric: fundamentals and applications
• Skew differential Goppa codes and their application to McEliece cryptosystem
• Simple Codes and Sparse Recovery with Fast Decoding
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory
• Interpolation-based decoding of folded variants of linearized and skew Reed-Solomon codes
• Fast decoding of lifted interleaved linearized Reed-Solomon codes for multishot network coding
• Fast decoding of interleaved linearized Reed-Solomon codes and variants

This page was built for publication: Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric

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