Sub-quadratic decoding of Gabidulin codes
Sub-quadratic decoding of Gabidulin codes
复制标题
DOI：
10.1109/isit.2016.7541760
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
S. Puchinger;A. Wachter-Zeh
中科院分区：
文献类型：
--
作者：
S. Puchinger;A. Wachter-Zeh
本文介绍了如何在码长的次二次时间内用加比度林码解码错误和擦除，从而改进了以往至少具有二次复杂度的算法。复杂度的降低是通过对线性化多项式的加速运算实现的。特别地，我们提出了线性化多项式的除法、多点求值和插值的快速算法，并展示了如何有效地计算最小子空间多项式。
This paper shows how to decode errors and erasures with Gabidulin codes in sub-quadratic time in the code length, improving previous algorithms which had at least quadratic complexity. The complexity reduction is achieved by accelerating operations on linearized polynomials. In particular, we present fast algorithms for division, multi-point evaluation and interpolation of linearized polynomials and show how to efficiently compute minimal subspace polynomials.