Complexity of decoding Gabidulin codes
- 1 March 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1081-1085
- https://doi.org/10.1109/ciss.2008.4558679
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Probabilistic algorithm for finding roots of linearized polynomialsDesigns, Codes and Cryptography, 2007
- Fast decoding of rank-codes with rank errors and column erasuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Finite FieldsPublished by Cambridge University Press (CUP) ,1996
- 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
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969
- Nonbinary BCH decoding (Abstr.)IEEE Transactions on Information Theory, 1968
- Cyclic decoding procedures for Bose- Chaudhuri-Hocquenghem codesIEEE Transactions on Information Theory, 1964
- Contributions to the theory of finite fieldsTransactions of the American Mathematical Society, 1934
- On a Special Class of PolynomialsTransactions of the American Mathematical Society, 1933