HTTPS SSH

Codinglib is mostly deprecated

NOTE: I'm deprecating Codinglib. The ACTIS project for improving native coding theory support in Sage has now successfully completed, and many of the base elements of Codinglib are now better supported in the most recent Sage release.

Some elements of Codinglib are not yet ported into Sage, most notably the alternative implementations of Guruswami--Sudan list-decoding and the implementation of Power decoding. Note however that native Sage now supports one reasonably fast implementation of the Guruswami--Sudan algorithm.

Codinglib is kept (mostly frozen) for reference and for compatibility with old implementations. At time of writing (jan 2017) Codinglib still works in the newest release of Sage; it's components are just largely incompatible with the native Sage ones. Several of my past papers have proof-of-concept implementations in separate repositories which use subroutines from Codinglib; I will likely not update these.

I might later start a successor project of Codinglib, building on the native coding theory structure in Sage. If this materialises, I will make this an standard Sage package which should ease installation considerably.

Johan Rosenkilde (né Nielsen)

Previous Introduction

This is Codinglib, a library for experimenting with algebraic coding theory.
Copyright Johan S. H. Rosenkilde
This is free software; every part of this released under the GNU Public License version 3 or later (at your option).

The library is an extension to the Open Source computer algebra system Sage. I have developed and maintain Codinglib for my own research on algebraic coding theory. Most of the code is quite specific for this area.

Codinglib is partially self-documenting by the use doc-strings for every function; however, it probably takes some effort to properly get to know it. It is also quite idiosyncratic to my specific needs and workflow. Finally, in any new version, I might change the name, semantics or calling convention of any existing functions.

However, if you find some of its functionality interesting, I will gladly answer specific questions to its usage and source code. You are also highly encouraged to continue working on and improve any of the code; if you do, I would very much like to know of your work. Also, I would be more than happy if any of my code ended in the actual Sage distribution; I would work on this myself if I had more time.

Overview

The following is a short description of each of the modules in Codinglib:

  • bma: The Berlekamp-Massey algorithm.

  • channel: Abstract class for representing channels

  • chinese_remainder: Chinese remainder codes: poly-alphabetic codes over ZZ/pZZ for different primes p, which are the ZZ-equivalent of Reed-Solomon codes. Note that this code implementation does not inherit from BlockCodeAbstract since it is poly-alphabetic. Also implementation of InterleavedChineseRemainderCode

  • code: Abstract and concrete class for representing linear block codes

  • codeTesting: Helper functions for testing error correcting code functions

  • counting: Wrapper-algebra for counting no. of operations in fields

  • cyclic: Cyclic linear codes.

  • ea: The Extended Euclidean algorithm with stopping conditions. Note that using modules over F[x] and weak Popov form is a more flexible approach.

  • generate_readme: Generates the package overview in the readme

  • goppa: Class for representing Goppa codes with corresponding utility functions

  • graphcode: Class for representing bipartite graph codes with corresponding utility functions

  • gs: The Guruswami-Sudan algorithm for Reed-Solomon codes: implementation and utilities

  • gsKV: Utilities for the variant of the Guruswami-Sudan algorithm using the small field Kotter-Vardy multiplicity assignment.

  • hermitian_code: Class for representing and decoding Hermitian codes.

    The codes follow the definition of [jsrn], which is a slightly larger class of codes than in [Dec]. The decoding algorithms are described in [Dec].

    • [jsrn]: Johan S. R. Nielsen, List decoding of algebraic codes, 2013 PhD thesis at Technical University of Denmark.
    • [Dec]: Johan S. R. Nielsen, Peter Beelen, Sub-quadratic Decoding of One-Point Hermitian Codes, in review for IEEE Transactions of Information Theory
  • key2d: 2D key equations and solving them.

    The name 2D Key Equations was introduced in [jsrn]. They are in Computer Algebra sometimes known as Simultaneous Hermitian Pade approximations.

    The notation here follows mainly that of [jsrn], but uses an improved handling of weights described in [Dec].

    • [jsrn]: Johan S. R. Nielsen, List decoding of algebraic codes, 2013 PhD thesis at Technical University of Denmark.
    • [Dec]: Johan S. R. Nielsen, Peter Beelen, Sub-quadratic Decoding of One-Point Hermitian Codes, in review for IEEE Transactions of Information Theory
  • listdecoding: Utility functions related to list decoding

  • module: Functionality for free F[x]-modules, in particular for calculating bases in weak Popov form. The weak Popov form is slightly stronger than row reduced form, and it is also a type of reduced Groebner bases over some simple module monomial orderings.

    • [Dec]: Johan S. R. Nielsen, Peter Beelen, Sub-quadratic Decoding of One-Point Hermitian Codes, in review for IEEE Transactions of Information Theory
  • parallel: Module for a simple thread pool, along with invoking workers over SSH.

  • plot_util: Utility functions for plotting. Contains an (now old) copy of the implementation of points for plotting, in order to allow custom marker symbols in list plots.

    Ideally, this should be reported and fixed upstream in Sage rather than be here.

  • polynomial_util: Generally usable polynomial functions

  • ratinter: Rational interpolation using the Wu algorithm

  • remote: Functions for importing Codinglib remotely, loaded on-the-fly directly from the repository. This is useful for loading Codinglib on a public Sage server.

  • rootfinding: F[x] Root-finding in polynomials over F[x,y].

  • rs: Class for representing GRS codes with corresponding utility functions

  • rs_mindist: Implementation of decoding algorithms Reed-Solomon up to half the minimum distance

  • rs_power: Functionality for Power decoding of Reed-Solomon codes. Power decoding was called "Decoding by virtual extension to an interleaved code" in the initial description of [SSB].

    In the initial algorithm of [SSB], the decoding radius is bounded by (roughly) the Sudan radius. In [N15], it was shown how to incorporate multiplicities to decode up to the Johnson radius. The implementation here supports that.

    REFERENCES: - Schmidt, G., V.R. Sidorenko, and M. Bossert. "Syndrome Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis." IEEE Transactions on Information Theory 56, no. 10 (2010): 5245-52. doi:10.1109/TIT.2010.2060130.

    • Nielsen, Johan S. R. "Power Decoding Reed-Solomon Up to the Johnson Radius.". Submitted to IEEE Transactions of Information Theory, 2015.
  • subcode: Direct construction of subfield subcodes by expansion of parity check matrices

  • util: Various utility functions used in codinglib

  • wu: Wu list decoder for Reed-Solomon and Binary Goppa codes. Parameter choices. See also ratinter for the core rational interpolation functionality.

Furthermore, the library contains a number of sheet files: these are similar to the notebook sheets, in that they contain snippets of code demonstrating or testing the core functionality of Codinglib. Most of these sheets are indeed intended as tests.

For instance, rs_decoding.sheet demonstrates all decoding algorithms for Reed-Solomon codes included in Codinglib.

For Emacs users, sheet files can elegantly be handled when using sage-mode by using the sage-blocks functionality.

Usage

Sage does not currently work well with non-spkg library code, so the importing of Codinglib is a bit peculiar.

Codinglib is written using the Sage language extensions to Python but at the same time is highly dependent on itself. To make this work in Sage currently, one needs to preprocess Codinglib's .sage files and load all the generated .py files at once as a Python package. In particular, using load/attach on the .sage files from a Sage prompt will usually not work.

Method 1: Downloading to personal computer

  • Download the whole source (mirror git repo) and put in a folder codinglib. Add the parent folder to the SAGE_PATH environment variable.

    For example, you have created a folder

    \home\foo\bar\codinglib
    

    on your system, which contains the .sage files and the rest of Codinglib. You then add

    \home\foo\bar
    

    to your SAGE_PATH.

  • Navigate to the codinglib folder and type the command

       make
    

    This will preprocess all the .sage files to reduce Sage syntax to standard Python.

  • From the Sage prompt, the library can be loaded with the command

    import codinglib
    
  • From the Sage Notebook, if running on a local Sage server, add the following to one of the first cells of each sheet in which you intend to use the library:

    #auto
    import codinglib 
    all = __builtins__.all
    

    The last line is to restore the Python standard library function all.

    In either of the above, you can of course replace import codinglib with the following to include commands directly in the namespace

    from codinglib import *
    

Method 2: On SageMathCloud

The SageMathCloud has excellent support for making modules within a project which can be run from any worksheet in that project.

To add Codinglib to a project, you should make a copy of Codinglib's source in a folder codinglib within your project. The most direct way to do this is:

  • Create a folder codinglib in the project on SageMathCloud and go to it's Add Files page.

  • Download Codinglib's source to your own machine.

  • Open a file explorer and drag-and-drop all the downloaded files onto the Drop Files-area. files into the SageMathCloud's add-page.

  • In SageMathCloud, go to the codinglib-folder's page. In the upper right-hand corner is a "Terminal command" text area. Enter

    make build
    

    This will create .py files for each of the .sage files.

    SageMathCloud sometimes complains that the command timed out after 15 seconds and was halted. This might mean nothing, or it might mean that some of the .py-files were not properly generated. In that case, simply run make build again.

  • You should now be able to run

    from codinglib import *
    

    from any worksheet in this project.

If you later need to update Codinglib, you simply need to overwrite the .sage. files with the new ones and rerun the make command.

Method 3: On a shared Sage Notebook sheet without write-access to its server

This is much more difficult as the Sage Notebook is not really geared to support non-spkg add-on Sage libraries. The following method basically dynamically downloads, preprocesses and imports Codinglib whenever one starts the Notebook sheet. Thus, it is very slow to start up and a bit tedious. However, it works without assuming any special rights on the Sage server. Once loaded, it will of course run in the usual speed of the server.

In one of the first cells of the Notebook sheet, add the following code

changeset = "ddd6636b2da0"
baseurl ="https://bitbucket.org/jsrn/codinglib/raw/" + changeset + "/"

# Manually load the remote functionality
import imp
from sage.misc.remote_file import get_remote_file
remoteFile = get_remote_file(baseurl + "remote.py", verbose=False)
remote = imp.new_module("remote")
exec open(remoteFile).read() in remote.__dict__

# Load the Sage library files and import them into the global namespace
imports = remote.retrieve_codinglib(baseurl)
for stm in imports:
    exec(stm)

Replace the string in changeset with the Git revision no. of the wanted version of Codinglib, as provided by BitBucket. For the most recent version, visit

https://bitbucket.org/jsrn/codinglib

and copy the revision no. of the top commit.

Executing this cell takes 10-20 seconds depending on your server's internet connection.

Regards,
Johan S. H. Rosenkilde__ jsrn@jsrn.dk
jsrn.dk