Date: Monday, January 30, 2017 ǀ 14:00
Location: Gebäude N1, 1. Stock, Raum N1135, Theresienstr. 90
Fakultät für Elektrotechnik und Informationstechnik
Professur für Coding for Communications and Data Storage
Speaker: Rudolf Mößbauer Tenure Track Assistant Professor Antonia Wachter-Zeh
Abstract:
In many applications, errors do not appear in the classical way of corrupting a certain number of symbols in a vector, but in specific patterns within arrays. This talk deals with list decoding of errors in arrays, in two different metrics: the rank-metric and the cover (crisscross) metric.List decoding generalizes the standard model of error correction: by increasing the error-correction radius beyond half the minimum distance, more than one codeword might lie within the decoding spheres. Therefore, the output of the decoder is a list of codewords. The first part of this talk deals with a short introduction to error-correcting codes, the definition of list decoding, and the two metrics for array codes which are considered later: the rank metric and the cover metric.In the second part, we will analyze the possibility of list decoding rank-metric codes and, in particular, Maximum Rank Distance (MRD) codes. We show that many MRD codes cannot be list decoded beyond half the minimum rank distance in polynomial time; a significant difference to Maximum Distance Separable (MDS, e.g., Reed-Solomon codes) in the Hamming metric. Crisscross errors corrupt rows and columns of arrays. Motivated by the negative result for decoding such errors in the rank metric, another metric is considered: the cover metric. The cover of a matrix is a set of rows and columns which contains all non-zero elements of the matrix. For this metric, we can prove that the list size grows only polynomially with the length of the code up to a certain radius. Further, a simple list decoding algorithm for a known optimal code construction is presented which decodes errors in the cover metric up to our upper bound. These results reveal significant differences between the cover metric and the rank metric and show that the cover metric is more suitable for correcting crisscross errors.
----------------------------------
Details on these results can be found in the following references:
[1] Wachter-Zeh, A.: List Decoding of Crisscross Errors. IEEE Trans. Inform. Theory, Vol. 63, No. 1, 2017, pp. 142--149.
[2] Raviv, N.; Wachter-Zeh, A.: Some Gabidulin Codes Cannot be List Decoded Efficiently at any Radius. IEEE Trans. Inform. Theory, Vol. 62, No. 4, 2016, pp. 1605--1615.
[3] Wachter-Zeh, A.: Bounds on List Decoding of Rank-Metric Codes. IEEE Trans. Inform. Theory, Vol. 59, No. 11, 2013, pp. 7268--7277.
