Version 8 (modified by 4 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 #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).

- 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`

and`AffineSpace`

/`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 #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