Sub-quadratic decoding of Gabidulin codes
Authors:
- 11 August 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2554-2558
Abstract
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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- On transform-domain error and erasure correction by Gabidulin codesDesigns, Codes and Cryptography, 2014
- Error resilience in distributed storage via rank-metric codes2012
- Fast decoding of Gabidulin codesDesigns, Codes and Cryptography, 2012
- Designing a Rank Metric Based McEliece CryptosystemLecture Notes in Computer Science, 2010
- Elliptic periods for finite fieldsFinite Fields and Their Applications, 2009
- Rank-Metric Codes for Priority Encoding Transmission with Network Coding2007
- Maximum-rank array codes and their application to crisscross error correctionIEEE Transactions on Information Theory, 1991
- Bilinear forms over a finite field, with applications to coding theoryJournal of Combinatorial Theory, Series A, 1978
- Theory of Non-Commutative PolynomialsAnnals of Mathematics, 1933
- On a Special Class of PolynomialsTransactions of the American Mathematical Society, 1933