Roadmap and status report for Coding Theory in Sage

See also the page on ​https://wiki.sagemath.org/Coding_Theory.

This page is meant to provide an overview of developments for Coding Theory in Sage. This includes existing trac tickets, with or without code, as well as wish-lists or long-term goals from interested developers.

Feel free to edit this page by adding trac tickets, more wish-lists, and add your names for topics you contributed to or would be interested in contributing to (this helps knowing who does what and who to contact for further collaborations).

Topics

Representing Codes

• Linear codes and category framework #18150
• Deprecate support for finite rings in LinearCode #20387
• AbstractLinearCode should throw sensible error messages on printing #20899
• LinearCode.basis() should be an immutable Sequence #19251

The following is some wishes:

• Non-linear codes
  • Support multilinear codes (i.e. a code over GF(q^m) which is linear over GF(q)). Examples include Interleaved linear codes, Folded RS codes and Multiplicity codes.
  • Support codes over rings (see #20387 for admitting that we currently don't support this).
• Explicit class for binary codes, possibly building on the current Cython implementation. Remove all binary code-specific methods from AbstractLinearCode.

Algebraic Code Families

• Reed--Muller codes
  • Base classes for Reed-Muller codes #20705
  • Decoding algorithm for low-order q-ary or binary Reed-Muller codes #20938
• Cyclic codes and BCH codes
  • A class for cyclic codes #20100
  • A class for BCH codes #20335
• Goppa codes would be extremely nice to have.
• AG codes To support Algebraic Geomety codes in Sage, we need the following building blocks:
  • Representation of algebraic curves. Done: Curve and AffineSpace/ProjectiveSpace.
  • Representation of divisors. Done: see Curve.divisor.
  • Computation of Riemann-Roch space bases. TODO.

Other Code Families

• Golay codes #20787.

Algorithms for generic codes

• Information set decoder #20138
• Non-guava implementation for covering_radius #19913
• Rate of a linear code #20342
• Improve minimum_distance generic method #20953
• AbstractLinearCode.minimum_distance fails with GAP message for large fields #20233
• dimension fails if _dimension is not set #21156 Bug
• Bounds and optimal codes: Not very easy, no support yet. What to do with ​http://codetables.de?
• Representing automorphisms of codes Sage is reasonably good at computing automorphisms of codes with the methods automorphisms_group_gens, permutation_automorphism_group, and the related method canonical_representative. These use an efficient C implementation written by Thomas Feuler, based on his PhD thesis. However, the representations of such automorphisms is very lacking. For instance, the "groups" returned by the above methods are simply a list of generators, with no group methods attached to them. And one cannot take an element of this group and apply it to e.g. a codeword or a whole code. Using a nice, Sage-wide algebraic representation would also make it much easier to implement the automorphism groups of special families for which it is known, e.g. Reed-Solomon codes. In sage.schemes there has been some recent development in automorphism groups of curves. Perhaps this can serve as a base?
• TestSet? decoding algorithm #21339

Code Testing, Plotting and Benchmarking

• Benchmarking tool for codes #20526, #20684, #20786. After discussions at SageDays75, Miguel Marco and Johan Rosenkilde started the stand-alone Python project ​Bleachermark directly inspired by the work in these tickets. That project is meant to supersede these tickets.

Documentation

• Document decoder types #20001
• Improve grs.py's documentation #20849
• Rework index and catalogs for sage.coding #20908
• Improve coding theory thematic tutorial on writing new structures #21361
• Improve the documentation for HammingCode #21305

General algebra in Sage that is important for coding theory

• Link to advanced fast polynomial arithmetic library functions such as multi-point evaluation and Lagrange interpolation.
• Link to fast GF(2)[x] library (currently used is NTL generic GF(p)[x]).
• Asymptotically fast (GF(q)[x])[y] root-finding #21333.
• Faster k[x] matrix reduction #21024, #16742.
• Ring extension support (related to e.g. subfield subcodes) #21413
• Submodules of (ZZ/nZZ)^r (prerequisite for codes over ZZ/nZZ) #6452

Cleanup, Restructuring, Misc bugs

• Clean LinearCodeFromCheckMatrix #19975
• encode as function call to an Encoder #20087
• decoder_type only works on class instances #20443
• GRS polynomial encoder fails if polynomial to encode is not in x #20744
• Syndrome decoder for a linear code sometimes sets wrong decoder type #20898
• Cached generator/parity check matrices should be immutable #21159

GSoC 2016: Rank metric codes

Arpit Merchant was the student for this project, with David Lucas and Johan Rosenkilde as mentors.

• Skew polynomials #13215
• Interpolation/evaluation methods for skew polynomials #21131
• Advanced skew polynomial methods and optimised implementation for finite field base rings #21088, #21259, #21262, #21264. Perhaps these should be closed as wont-fix: Xavier Caruso has expressed a wish to rewrite all this.
• Gabidulin codes #20970
• Abstract class for rank-metric codes #21226