Version 8 (modified by 5 years ago) (diff) | ,
---|
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 #20899LinearCode.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 overGF(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).
- Support multilinear codes (i.e. a code over
- 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
- Cyclic codes and BCH codes
- 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
andAffineSpace
/ProjectiveSpace
. - Representation of divisors. Done: see
Curve.divisor
. - Computation of Riemann-Roch space bases. TODO.
- Representation of algebraic curves. Done:
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 #20233dimension
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 methodcanonical_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. Insage.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 overZZ/nZZ
) #6452
Cleanup, Restructuring, Misc bugs
- Clean
LinearCodeFromCheckMatrix
#19975 encode
as function call to anEncoder
#20087decoder_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