= 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
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
* Decoding algorithm for low-order q-ary or binary Reed-Muller codes #20938
* 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 #22982
== Other Code Families ==
* Open a ticket for your favourite code family and add it here.
== Algorithms for generic codes ==
* Information set decoder #20138
* Non-guava implementation for `covering_radius` #19913
* 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 ==
* 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]`).
* 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
== GSoC 2016: Rank metric codes ==
Arpit Merchant was the student for this project, with David Lucas and Johan Rosenkilde as mentors.
* 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