Generic Decoding in the Sum-Rank Metric

DOI10.1109/TIT.2022.3167629MaRDI QIDQ5096972zbMATH OpenFDO

Authors Sven Puchinger, Julian Renner, Johan Rosenkilde

Publication date 19 August 2022

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

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

zbMATH Keywords

codes in sum-rank metricgeneric decoding algorithm

Mathematics Subject Classification ID

Decoding (94B35)

Abstract: We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.

Cited in

(7)

• Duals of linearized Reed-Solomon codes
• On decoding high-order interleaved sum-rank-metric codes
• On the hardness of the Lee syndrome decoding problem
• S-semantics -- an example
• Interpolation-based decoding of folded variants of linearized and skew Reed-Solomon codes
• Distinguishing and recovering generalized linearized Reed-Solomon codes
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory

This page was built for publication: Generic Decoding in the Sum-Rank Metric

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