2020/01/14 by Sven Puchinger, Puchinger, Sven, Julian Renner +3 · 6 citations
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Networks Research
paper · pdf · doi:10.48550/arxiv.2001.04812
openalex publication_date 2020/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.