An alternative decoding method for Gabidulin codes in characteristic zero
Autor: | Sven Müelich, David Mödinger, Martin Bossert, Sven Puchinger |
---|---|
Rok vydání: | 2016 |
Předmět: |
FOS: Computer and information sciences
Discrete mathematics Rank (linear algebra) Information Theory (cs.IT) Computer Science - Information Theory Zero (complex analysis) 020206 networking & telecommunications 010103 numerical & computational mathematics 02 engineering and technology Type (model theory) 01 natural sciences Matrix (mathematics) Finite field Metric (mathematics) 0202 electrical engineering electronic engineering information engineering 0101 mathematics Decoding methods Computer Science::Information Theory Numerical stability Mathematics |
Zdroj: | ISIT |
Popis: | Gabidulin codes, originally defined over finite fields, are an important class of rank metric codes with various applications. Recently, their definition was generalized to certain fields of characteristic zero and a Welch--Berlekamp like algorithm with complexity $O(n^3)$ was given. We propose a new application of Gabidulin codes over infinite fields: low-rank matrix recovery. Also, an alternative decoding approach is presented based on a Gao type key equation, reducing the complexity to at least $O(n^2)$. This method immediately connects the decoding problem to well-studied problems, which have been investigated in terms of coefficient growth and numerical stability. 5 pages, accepted at IEEE International Symposium on Information Theory 2016 |
Databáze: | OpenAIRE |
Externí odkaz: |