Decoding Interleaved Gabidulin Codes by Module Minimization

• Applicant: Professor Dr.-Ing. Martin Bossert
• Subject Area: Electronic Semiconductors, Components and Circuits, Integrated Systems, Sensor Technology, Theoretical Electrical Engineering
• Term: from 2014 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 261867389

• Final Report Year: 2019

Final Report Abstract

The main results of the project are as follows: 1. Application of module minimization for decoding Gabidulin codes (defined with skew polynomials instead of linearized polynomials). Before, module minimization was only applied to Reed–Solomon (RS) codes. An extension for interleaved Gabidulin codes was done. Further, also decoding the class of Mahdavifar– Vardy codes is possible. 2. Proof that the low-rank matrix recovery problem can be reduced to the decoding of Gabidulin codes over fields with characteristic zero. 3. A novel decoding method for interleaved Gabidulin codes in characteristic zero using the Alekhnovich algorithm for row reduction of skew polynomial matrices. 4. The first decoder with sub-quadratic complexity for Gabidulin codes was found. This result is based on the fact that several accelerations of operations for linearized polynomials were developed. 5. Reed–Solomon codes as well as their rank metric analogon, Gabidulin codes over fields of characteristic zero causes numerical issues when floating point operations are used. In order to avoid numerical instabilities, exact computations can be used, e.g., over the field of rational numbers. We found bounds for the growths of the numerators and denominators of the considered fractions during encoding and decoding. The usage of rational numbers is only started and several open problems remain. However, it is a promising method since then codes can play an important role in the field of signal processing. Further, it could be extended to complex numbers, where real and imaginary part are rational numbers.

Publications

• Channel Coding Inspired Contributions to Compressed Sensing. PhD thesis, Universität Ulm, 2015
  Henning Alexander Zörlein
  
• Decoding Evaluation Codes and their Interleaving. PhD thesis, Universität Ulm, 2015
  Wenhui Li
  
• Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation. International Workshop on Coding and Cryptography, 2015
  Wenhui Li, Johan S. R. Nielsen, Sven Puchinger, and Vladimir Sidorenko
  
• An Alternative Decoding Method for Gabidulin Codes in Characteristic Zero. IEEE International Symposium on Information Theory (ISIT), pages 2549–2553, 2016
  Sven Müelich, Sven Puchinger, David Mödinger, and Martin Bossert
  
• Sub-quadratic Decoding of Gabidulin Codes. IEEE International Symposium on Information Theory (ISIT), pages 2554–2558, 2016
  Sven Puchinger and Antonia Wachter-Zeh
  
• Decoding Interleaved Gabidulin Codes using Alekhnovich’s Algorithm. Electronic Notes in Discrete Mathematics, 57:175–180, 2017
  Sven Puchinger, Sven Müelich, David Mödinger, Johan Rosenkilde né Nielsen, and Martin Bossert
  
• Low-Rank Matrix Recovery using Gabidulin Codes in Characteristic Zero. Electronic Notes in Discrete Mathematics, 57:161–166, 2017
  Sven Müelich, Sven Puchinger, and Martin Bossert
  
• Popov Form Computation for Matrices of Ore Polynomials. Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pages 253–260, 2017
  Mohamed Khochtali, Johan Rosenkilde né Nielsen, and Arne Storjohann
  
• Row Reduction Applied to Decoding of Rank-Metric and Subspace Codes. Designs, Codes and Cryptography, 82(1-2):389–409, 2017
  Sven Puchinger, Johan Rosenkilde né Nielsen, Wenhui Li, and Vladimir Sidorenko
  
• Algebraic Decoding over Finite and Complex Fields using Reliability Information. PhD thesis, Universität Ulm, 2018
  Mostafa Hosni Mohamed
  
• Construction and Decoding of Evaluation Codes in Hamming and Rank Metric. PhD thesis, Universität Ulm, 2018
  Sven Puchinger
  
• Fast Operations on Linearized Polynomials and their Applications in Coding Theory. Journal of Symbolic Computation, 89:194–215, 2018
  Sven Puchinger and Antonia Wachter-Zeh
  
• Reed–Solomon Codes over Fields of Characteristic Zero. IEEE International Symposium on Information Theory (ISIT), 2019
  Carmen Sippel, Cornelia Ott, Sven Puchinger, and Martin Bossert