Johan, Thanks for all of the great information. This definitely gives me a better sense of the project. I think my plan is to work my way through these papers and the work already on the project to date over the next few days. I hope to make my project proposal for this project, and have a draft by Saturday or Sunday. Would you mind if I email it to you then and to get your feedback? Also, I may be posting questions that come up during my research over the next few days.
One last question. Are there any open issues in code related to this project, that you think I might be able to look into and fix? Thanks again for all the help! Best, Joseph On Tuesday, March 15, 2016 at 1:10:05 PM UTC-4, Johan S. R. Nielsen wrote: > > 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.
