Complexity of decoding Gabidulin codes
Maximilien Gadouleau, Zhiyuan Yan · 2008
In this paper, we analyze the complexity of decoding Gabidulin codes using the analogs in rank metric codes of the extended Euclidean algorithm or the Berlekamp-Massey algorithm. We show that a subclass of Gabidulin codes reduces the complexity and the memory requirements of the decoding algorithm. We also simplify an existing algorithm for finding roots of linearized polynomials for decoding Gabidulin codes. Finally we analyze and compare the asymptotic complexities of different decoding algorithms for Gabidulin codes.