Generic Decoding in the Sum-Rank Metric

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2022-08, Vol.68 (8), p.5075-5097
Main Authors: Puchinger, Sven, Renner, Julian, Rosenkilde, Johan
Format: Article
Language:English
Subjects:
Algorithms
Codes
Complexity theory
Decisional sum-rank syndrome decoding problem
Decoders
Decoding
erasure decoding
Europe
generic decoding
Linear codes
Measurement
probabilistic hardness reduction
sum-rank-metric codes
Technological innovation
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2022.3167629