Generic Decoding in the Sum-Rank Metric

Sven Puchinger, Julian Renner, Johan Rosenkilde

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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.

Original languageEnglish
Pages (from-to)5075-5097
Number of pages23
JournalIEEE Transactions on Information Theory
Volume68
Issue number8
DOIs
StatePublished - 1 Aug 2022

Keywords

  • Decisional sum-rank syndrome decoding problem
  • erasure decoding
  • generic decoding
  • probabilistic hardness reduction
  • sum-rank-metric codes

Fingerprint

Dive into the research topics of 'Generic Decoding in the Sum-Rank Metric'. Together they form a unique fingerprint.

Cite this