Coding Theory development project. Request-for-comments: New code family and encoder/decoder structu
36 views
Skip to first unread message
Johan S. R. Nielsen
Feb 20, 2015, 12:24:01 PM2/20/15
to sage-codi...@googlegroups.com
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
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
Nathann Cohen
Feb 20, 2015, 12:42:51 PM2/20/15
to Sage devel, sage-codi...@googlegroups.com
Hello,
It seems that you really implemented a lot of things before creating
any ticket on Sage's trac. Be aware that the reviews may be very
painful as a result, for some fundamental design decisions may have to
be changed in this process.
Nathann
On 20 February 2015 at 18:32, Dima Pasechnik <dim...@gmail.com> wrote:
> --
> You received this message because you are subscribed to the Google Groups
> "sage-coding-theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-coding-the...@googlegroups.com.
> To post to this group, send email to sage-codi...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-coding-theory/1089c130-0283-42ff-a28b-0869776eaed4%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
It seems that you really implemented a lot of things before creating
any ticket on Sage's trac. Be aware that the reviews may be very
painful as a result, for some fundamental design decisions may have to
be changed in this process.
Nathann
On 20 February 2015 at 18:32, Dima Pasechnik <dim...@gmail.com> wrote:
> You received this message because you are subscribed to the Google Groups
> "sage-coding-theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-coding-the...@googlegroups.com.
> To post to this group, send email to sage-codi...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-coding-theory/1089c130-0283-42ff-a28b-0869776eaed4%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
Reply all
Reply to author
Forward
0 new messages