论文标题
在总和度量中进行通用解码
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 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.
