TY - GEN
T1 - Sub-quadratic decoding of Gabidulin codes
AU - Puchinger, Sven
AU - Wachter-Zeh, Antonia
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/8/10
Y1 - 2016/8/10
N2 - 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.
AB - 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.
KW - Fast Decoding
KW - Gabidulin Codes
KW - Linearized Polynomials
KW - Skew Polynomials
UR - http://www.scopus.com/inward/record.url?scp=84985961504&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2016.7541760
DO - 10.1109/ISIT.2016.7541760
M3 - Conference contribution
AN - SCOPUS:84985961504
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2554
EP - 2558
BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016
Y2 - 10 July 2016 through 15 July 2016
ER -