1. Generic Decoding in the Sum-Rank Metric.
- Author
-
Puchinger, Sven, Renner, Julian, and Rosenkilde, Johan
- Subjects
- *
DECODING algorithms , *LINEAR codes , *HARDNESS , *GENERIC drugs , *COMPLEXITY (Philosophy) - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF