1. David Lucas Avatar David Lucas
  2. Untitled project
  3. sage_coding_project

Wiki

Clone wiki

sage_coding_project / Home

View History

#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.

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).

Contributions/Related projects

GSoC 2016

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.

#Project roadmap#

Project roadmap Decoders roadmap

#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:

  • A GeneralizedReedSolomonCode class
  • A HammingCode class
  • A ConcatenatedCode as a class, demonstrating the modularity of class-based families
  • A CyclicCode class
  • A BCHCode class
  • A PuncturedCode class
  • A ShortenedCode class
  • An ExtendedCode class
  • A SubfieldSubcode class, 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

Available channels

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

#Examples#

We've written an extensive page with Examples.

#Other discussions#

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 git@trac.sagemath.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        git@trac.sagemath.org: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:

##Who we are ##

Updated