Hi sage-devel, An update from our coding theory development project.
On Friday, February 20, 2015 at 6:24:01 PM UTC+1, Johan S. R. Nielsen wrote: > > Hello everyone, > > As we announced previously ( > https://groups.google.com/forum/#!topic/sage-devel/pBmeknQcyZM), we > started October 1. a 2-year project for improving coding theory support in > Sage. This post has two purposes: 1) It's our "going public" post, where we > announce more precisely our plans for our 2-year project; and 2) It puts up > for discussions our new scalable design for doing coding theory in Sage > which comes with a fully working and documented implementation, integrated > into a fork of Sage. > > Our project now has a web page, which is also our project repository: > https://bitbucket.org/lucasdavid/sage_coding_project > > This page contains a description of our project, our development plan, and > a description of what has currently been implemented including examples. It > is also a Git repository containing a fork of the Sage project containing > at any time the newest version of Sage with the newest (unstable) version > of our code integrated. Little by little, our code will be cut up into > tickets and incorporated into Sage using Trac and the review system. While > tickets are being reviewed, new ones will be written, and our Git > repository makes it easy to get a Sage version containing all the newest > functionality. > > What we have done so far and our suggested design: > Our team -- and principally our main developer David Lucas -- has been > hard at work thinking of a scalable design for representing the core > objects of coding theory: it should appeal to people coming from any of the > many approaches to coding theory, and as with all things Sage, it should > appeal to many levels of user competence. This is just the first step of > our project, and later ones will add much more new functionality. > > The result is a base design and a working demo of this that we suggest to > incorporate into Sage. It concerns principally > > - Code families as classes > - Representation of multiple encoding and decoding methods, specific to > the respective code family. > > And secondarily > > - Representing communication channels, i.e. "adding errors" > - Some renaming of foundational methods > > To demonstrate this, we have implemented: > > - Generalized Reed-Solomon codes as a class > - Hamming Codes as a class > - Concatenated codes as a class, demonstrating the modularity of > class-based families > - 2 encoders for GRS codes > - 3 fast decoders for GRS codes, two half-minimum distance decoders, 1 > error-erasure decoder > - A channel for adding errors, and a channel for adding > errors-and-erasures > > It will have deep consequences for the representation, use and further > development of coding theory functionality. Before opening tickets for > these changes, we want to present the design here, so that we can discuss > and possibly improve it. > > Code examples are much better than words at conveying design: we have > written a page going through the new ideas of the design from a user's > point of view: > https://bitbucket.org/lucasdavid/sage_coding_project/wiki/Examples > > In more technical details, the main design features that we propose are: > > 1) Code families are classes. This enables family-specific functionality, > such as minimum distance bounds or fast decoders. > 2) A code is therefore no longer always given by a generator matrix. For > such code families, a generator matrix will only be computed on demand. > 3) Encoders are classes. We support multiple encoders for a code family > allowing different mappings. > 4) The message space for an encoder can be something else than a vector > space. Reed-Solomon codes can e.g. have an encoder which encodes > polynomials directly. > 5) The inverse of encoding is called "unencoding" (as opposed to > "decoding" which we reserve for correcting errors). unencode() is a method > on Encoder. > 6) Decoders are classes. This enables multiple decoders for a code family. > 7) Decoders have an input space which is not necessarily the ambient space > of the code. This supports e.g. soft-decision decoders where reliability > information is part of the input. > 8) Decoders can decode to a codeword or directly to a message space. > 9) There are convenience methods directly on a code for encoding, decoding > and unencode such that users not caring about these choices are not > burdened. > 10) We introduce Channels which embody the concept of communication > channels, both for adding errors and for changing representation. They > provide a modular and convenient structure for user-friendliness and > code-reusability in e.g. benchmarking frameworks. > 11) Renaming of some methods in LinearCode: gen_mat into generator_matrix > and check_mat to parity_check_matrix. > > We invite for discussion on this design and for contributions by everyone > motivated by coding theory. As soon as we agree on this thread, we will > create a ticket on Trac with the first few changes. Reviewers will be more > than welcome! > > David Lucas, Johan S. R. Nielsen, Clément Pernet and Daniel Augot > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
