# Roadmap and status report for Coding Theory in Sage

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.
- A-G codes
To support Algebraic Geometric 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

Last modified 3 weeks ago
Last modified on 01/05/17 01:55:56