= 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 [https://github.com/miguelmarco/bleachermark 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