Hi Joseph, I would be one of the mentors on that project. Basically, Sage has quite nice support for regular coding theory now, when all you want to do is linear codes over the Hamming metric: there are many algorithms for combinatorial questions (minimum distance, automorphism groups, etc.) and there are Reed-Solomon codes (and other families on the way) with fast decoding algorithms, etc. Rank-metric codes, however, is a hot research topic but requires a different set of base functionality and structure.
Gabidulin codes are by far the most important family of rank metric codes. They are the rank-metric analogue of Reed-Solomon codes: they are MRD, i.e. they have the maximal possible minimum rank distance n-k+1, for a code of length n and dimension k. Like Reed-Solomon codes, they arise as evaluations, but instead of using ordinary polynomials, one use evaluations of "linearised polynomials". Linearised polynomials behave in many ways like ordinary ones, a central difference being that the multiplication rule is not commutative (i.e. a*b != b*a). This means all algorithms have to be carefully designed. "Skew polynomials" are, on the face of it, described differently from linearised polynomials (if you look up the definitions), but in the case we're considering, they are equivalent. I personally prefer the skew polynomial description, but much literature on Gabidulin codes use linearised polynomials, so you become familiar with both. A good reason that we should stick to skew polynomials in our implementation is that a massive ticket was written years ago to support skew polynomials in Sage: http://trac.sagemath.org/ticket/13215 But this has never been reviewed! (and might potentially need rebasing and some polishing). The critical core parts of this project would be something like: - Polish off and review #13215 - Create a rank-metric base class, mirroring LinearCode and the encoder/decoder structure. - Create a Gabidulin code class with encoding, using the skew polynomial ring. - Write a decoding algorithm for Gabidulin codes, which should run in something like O(n^2) operations over the extension field it is defined in. If time permits, one could extend in various ways, e.g. error-erasure decoding of Gabidulin codes. A challenge for this project is that Rank-metric codes are still a very hot research topic, and notation and conventions haven't completely settled yet. This means for one that we should get acquainted with several sources. It also means that there are no polished books, as far as I know, which deals with Rank-metric codes and Gabidulin codes. Two important sources, which we will likely use a lot during the project, are: 1) Koetter, R., and F. R. Kschischang. 2008. “Coding for Errors and Erasures in Random Network Coding.” IEEE Transactions on Information Theory 54 (8): 3579–91. doi:10.1109/TIT.2008.926449. http://arxiv.org/abs/cs/0703061 This renewed the interest in rank metric codes by demonstrating that these are natural codes to consider in random network coding. 2) Wachter-Zeh, Antonia. 2013. “Decoding of Block and Convolutional Codes in Rank Metric.” PhD thesis. Universität Ulm. http://vts.uni-ulm.de/docs/2013/8688/vts_8688_12905.pdf This PhD thesis deals with how to efficiently work with and decode Gabidulin codes. It extensively discusses algorithms, and I think we will refer to this often, though we will probably not have time to consider all the algorithms in it. Neither of them are super-easy to read, I'm afrad. The former spends a lot of time on the application in network coding; the most important part for our use is Section V. The latter is a long PhD thesis and has quite technical notation: begin by browsing it loosely, focusing on the overall ideas described in Section II. The mathematically most challenging, apart from the decoding algoritm would be the jumping between GF(q^m) and GF(q)^m. Sage has only limited support for this right now, though things have improved a lot recently with AlgebraicallyClosedField and the main engine of an (yet unreviewed) ticket by my co-mentor David Lucas: http://trac.sagemath.org/ticket/20039. However, these might not be sufficient, especially considering efficiency: we might like, for instance, to compute only with "normal bases" of GF(q^m)/GF(q). I've started a discussion on sage-coding-theory on pitfalls regarding rank metric codes, and I'm hoping (and expecting one of these days) some input from people I know that have been implementing similar things. Best, Johan Joseph Obiajulu writes: > Hello All, > > My name is Joseph Obiajulu and I'm a junior studying mathematics and > computer science at Princeton University. I was looking through the project > ideas for potential GSoC projects on the Sage page, and I came across a > project idea concerning "Rank-metric codes." I have experience with > coding-theory, core knowledge of abstract algebra, and thought that I might > be able to contribute to the project. I wanted to ask on this mailing list, > especially to those who will mentor this project, where the best place to > start would be (I have a few ideas, but I wanted to ask those who have put > more thought into this question for advice). Also, I was wondering if this > is a high-priority project, or if there is another project that the Sage > community would rather have someone work on for the summer. > > Thanks for the help, > Joseph -- -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/d/optout.
