Generic Decoding in the Sum-Rank Metric
From MaRDI portal
Publication:5096972
DOI10.1109/TIT.2022.3167629zbMATH Open1505.94117arXiv2001.04812MaRDI QIDQ5096972FDOQ5096972
Johan Rosenkilde, Julian Renner, Sven Puchinger
Publication date: 19 August 2022
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2001.04812
Cited In (7)
- On decoding high-order interleaved sum-rank-metric codes
- S-semantics -- an example
- On the hardness of the Lee syndrome decoding problem
- Duals of linearized Reed-Solomon codes
- 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
- Distinguishing and recovering generalized linearized Reed-Solomon codes
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)
