Generalized Skew Reed-Solomon Codes and Other Applications of Skew Polynomial Evaluation

Abstract

This thesis studies the theory of error-correcting codes based on evaluation of skew polynomials. Skew polynomials are a noncommutative generalization of ordinary polynomials that, in recent years, have found applications in coding theory and cryptography. The evaluation of skew polynomials is significantly different from that of ordinary polynomials. Using skew polynomial evaluation, we define a class of codes called Generalized Skew-Evaluation codes. This class contains a special subclass that we call Generalized Skew Reed-Solomon codes. Generalized Skew Reed-Solomon codes are intimately connected to both regular Reed-Solomon codes and Gabidulin codes. These connections allow us to design interesting codes for both the Hamming metric and the rank metric. In addition, we prove a duality theory that exists within a subclass of Generalized Skew Reed-Solomon codes. This duality theory can be viewed as an extension to the well-known duality theory of Generalized Reed-Solomon codes. The decoding of Generalized Skew Reed-Solomon codes can be done using a Berlekamp-Welch style decoder. We design such a decoder by studying the general polynomial interpolation problem for skew polynomials. In particular, we generalize Kötter interpolation to work over skew polynomial rings. In our generalization, we provide a mathematically rigorous framework, as well as two important applications: a Newton interpolation algorithm for skew polynomial evaluation and a Berlekamp-Welch style decoder. In analyzing the connection between Generalized Skew Reed-Solomon codes and Gabidulin codes, we demonstrate the interplay between skew polynomials and linearized polynomials. This is summarized by a Structure Theorem. Using this theorem, we construct a matroid called the Fqm[χ;σ]-matroid. The structure of this matroid is induced by skew polynomial evaluation. We examine numerous properties of this matroid, and show an application of this matroid in the context of network coding.