ACTIS: Algorithmic Coding Theory in Sage. Sep. 2014--Sep. 2016
ACTIS is over
This repository is kept for reference and history. Don't check out the source code of the repository: the Sage version is now very old.
- ACTIS: Algorithmic Coding Theory in Sage. Sep. 2014--Sep. 2016
- Project roadmap
- Try it out...
- What have we done so far
- Other discussions
- How to contribute
- Tickets and Sage Development
The main thrust of this project is to vastly enhance the coding theory part of Sage. We want to develop a whole range of functionalities for coding theory that may also be useful for other areas: combinatorics, cryptography, computer science, etc. Our intended audience consists of researchers, students, and teachers. We also keep in mind the engineering community.
We follow the Sage development model of genericity and high level programming: the aim is an elegant class system which is comprehensive and flexible yet easy to use. For the algorithmic aspects of encoding and decoding, we aim to rely on the efficient computer algebra routines of Sage and its library dependencies.
To do this, we have a full time software programmer (David Lucas) on the project, until September 2016.
Sage Days 75 on ACTIS
A Sage Days will be held from August 22 to August 26, 2016 at Inria Saclay (Polytechnique Campus, Palaiseau) France.
We will introduce Sage to coding theorists and have presentations about what we did during ACTIS. While tutorial material will be centered on coding theory, we plan to have coding sprints on the afternoons (and evenings)! So every Sage developer is welcomed.
More details and registration on the dedicated page. For any questions, please contact David Lucas (david.lucas[at]inria.fr).
As part of Google Summer of Code 2016, Arpit Merchant is working on the implementation of a framework to support rank-metric codes in Sage. One can see a (short) description of the project here
Reed-Muller codes in Sage
Parthasarathi Panda is working on the implementation of Reed-Muller codes (both binary and q-ary), with their specific decoding algorithms in Sage.
Try it out...
Don't check out the source code of the repository: the Sage version is very old.
Instead, the code of this project is (by now, mostly) integrated into Sage: if you want to try it out, simply download the latest Sage release and run it.
What have we done so far
So far we have focused on preparing the existing code base for the envisioned extensions. This entails:
- Code families as classes
- Representation of multiple encoding and decoding methods, specific to the respective code family.
- Representing communication channels, i.e. "adding errors"
- Some renaming of foundational methods
Some code is now in Sage proper, including structure for encoders and representation of communication channels plus some communications channels. We hope that some code families will be in Sage very soon.
Available code classes
The following code families and constructions are available in the project repository:
ConcatenatedCodeas a class, demonstrating the modularity of class-based families
SubfieldSubcodeclass, which comes with a class to perform fields embedding in Sage, even in the case both fields are non-prime fields.
Available encoders and decoders
The following encoders and decoders are available in the project repository:
- Two encoders for GRS codes, one with a Vector Space as message space, the other one with a polynomial ring as message space
- A decoder based on Berlekamp-Welch algorithm for GRS codes
- A decoder based on Gao algorithm for GRS codes
- Key equation solving by syndrome computation decoder for GRS codes
- A decoder able to decode both errors and erasures for GRS codes
- A list-decoder based on Guruswami-Sudan algorithm, including two different algortihms for the interpolation step for GRS codes
- An encoder with a vector space as message space for Cyclic codes
- A decoder decoding over the surrounding BCH code of a Cyclic code
- An encoder with a vector space as message space for BCH codes
- A decoder decoding over the underlying GRS code of a BCH code
- An encoder with a vector space as message space for extended codes, shortened codes, subfield subcodes and punctured codes
- One decoder using the original code for extended codes, shortened codes, subfield subcodes and punctured codes
- An encoder with a vector space as message space for Concatenated codes
- A decoder using the decoders of inner/outer codes of Concatenated codes
We also propose the following
Channel structures, which emulate real-world communication by adding errors in the provided vectors:
- A channel adding a fixed number of errors, provided by the user
- A channel adding both errors and erasures
- A channel reproducing the behaviour of a q-ary symmetric channel
We've written an extensive page with Examples.
There are some pages in this wiki in which we are discussing other topics, still related to coding theory in Sage. The full list of these pages can be seen here. You might be interested in particular by:
How to contribute
Join and participate! Concretely, we are looking for help on:
- Discussions on design
- Suggestions on what to implement
- Reporting of bugs
- Development of new functionality.
- Review of tickets on trac. See also below.
The main go-to place for discussions is sage-coding-theory.
Install development version of sage and review tickets
To install the latest development version of Sage, follow these steps:
- Get the stable release of Sage:
[user@localhost ~]$ git clone git://github.com/sagemath/sage.git [user@localhost ~]$ cd sage
- Get the latest beta version:
[user@localhost sage]$ git checkout develop
- Compile this version:
[user@localhost sage]$ make
Now, if you run Sage, you should have a red frame atop your terminal window, saying "this is a prerelease version" * Properly set your remotes for trac:
[user@localhost sage]$ git remote add trac git://trac.sagemath.org/sage.git -t master [user@localhost sage]$ git remote set-url --push trac firstname.lastname@example.org:sage.git
- Check everything went smoothly (you should have the same output than below):
[user@localhost sage]$ git remote -v origin git://github.com/sagemath/sage.git (fetch) origin git://github.com/sagemath/sage.git (push) trac git://trac.sagemath.org/sage.git (fetch) trac email@example.com:sage.git (push)
- To get some code from a ticket, no need to set up your id. All you have to do is to copy the name of the branch (usually of the form u/username/desc) and type the following:
[user@localhost sage]$ git fetch trac u/username/desc [user@localhost sage]$ git checkout -b my_branch FETCH_HEAD
Replace "my_branch" by the name you wish for this branch.
Tickets and Sage Development
New code enters Sage using the Trac ticket system: a small patch of code, implementing or fixing a well-defined thing, is explained and reviewed as one "ticket". Everyone can review tickets, even without great insight into how Sage works. See the Sage reviewer check-list.
The following lists of tickets are related to our project:
- ticket list on trac
- coding-theory tickets needing review
- Open coding-theory tickets
- all tickets we have been involved in, including closed tickets containing code now in Sage.
Who we are