Meta-ticket: enhancement of the coding theory part of Sage

[sagetrac-dlucas]

This ticket summarizes the work done in the ACTIS project.

The main goal of this project is to enhance the decoding part of Sage, doing the following:

• propose a new API to manage code families
• propose a new API to manage multiple encoders for a given code family (i.e multiple message spaces)
• propose a new API to manage multiple decoding algorithms for a given code family
• implement numerous code families, alongside their encoders and decoders

The following tables gives a quick access to all tickets related to the project:

• The first table contains references to every ticket adding major features, like new code families, decoders...
• The second table contains references to every small ticket: bug fixes, minor quality of life upgrades, etc
• The last table contains references to every ticket which has been positive reviewed and/or closed.

The Nature column gives the "type" of the ticket :

• Structure means it's a structural ticket, which does not require any knowledge in coding theory. It will be for tickets which introduce new mechanisms in the API.
• Cleanup means it's a ticket that refreshes old existing code of the coding library, and/or documentation. It does not require any knowledge in coding theory.
• Content means it adds new mathematical content (code families, decoding algorithms, ...) to Sage. Some knowledge on the topic might be useful for these tickets.
• Documentation means it's a ticket which adds some new documentation in the library. It does not require any particular knowledge in coding library, nor being familiar with our code.
• Enhancement means it's a ticket which makes some existing code better, either in matter of speed or design.

Major features

Topic	Ticket number	Nature
Linear codes and category framework	#18150	Structure
A class for cyclic codes	#20100	Content
Information set decoder	#20138	Content
A class for BCH codes	#20335	Content
Benchmarking tool for codes	#20526	Content
A class for Golay codes	#20787	Content
Some decoders for Reed-Muller codes	#20938	Content
Various cleanup and deprecation in sage.coding.linear_code	#21165	Cleanup

Small tickets

Topic	Ticket number	Nature
Non-guava impl. for covering_radius	#19913	Cleanup
Clean LinearCodeFromCheckMatrix	#19975	Cleanup
Stop and restart features for benchmarks	#20684	Content
Multithread option for benchmarks	#20786	Content
Document decoder types	#20001	Documentation
Improve grs.py's documentation	#20849	Documentation
encode as application to Encoder	#20087	Enhancement
Method for the rate of a linear code	#20342	Enhancement
Rework index and catalogs for sage.coding	#20908	Enhancement
Improve minimum_distance generic method	#20953	Enhancement
Improve coding theory thematic tutorial on writing new structures	#21361	Enhancement
AbstractLinearCode.minimum_distance fails with GAP message for large fields	#20233	Bug
decoder_type only works on class instances	#20443	Bug
GRS polynomial encoder fails if polynomial to encode is not in x	#20744	Bug
dimension fails if _dimension is npt set	#21156	Bug
Deprecate support for finite rings in LinearCode	#20387	Defect
Syndrome decoder for a linear code sometimes sets wrong decoder type	#20898	Defect
AbstractLinearCode should throw sensible error messages on printing	#20899	Defect
LinearCode.basis() should be an immutable Sequence	#19251	Defect
Cached generator/parity check matrices should be immutable	#21159	Defect
Improve the documentation for HammingCode	#21305	Defect

Tickets related to GSoC 2016: Rank metric codes

Topic	Ticket number	Nature
Skew polynomials	#13215	Content
A class for skew polynomials over finite fields	#21088	Content
Interpolation/evaluation methods for skew polynomials	#21131	Content
Karatsuba-based methods for skew polynomials	#21259	Content
Center-related content for skew polynomials	#21262	Content
Factoring/irreducibility methods for skew polynomials	#21264	Content
A class for Gabidulin codes	#20970	Content
An abstract class for rank-metric codes	#21226	Content

Old tickets

Topic	Ticket number	Nature
Structure for code families	#18099	Structure
Encoding structure	#18376	Structure
Decoding structure	#18813	Structure
Better names in coding	#17973	Cleanup
Improve __contains__ method	#18607	Cleanup
Clean imports	#19315	Cleanup
Clean dual_code, __eq__ and removed debug traces	#19492	Cleanup
Generic impl. for __ne__	#19743	Cleanup
Clean-up index of modules	#19907	Cleanup
Clean AbstractLinearCode.zero	#20113	Cleanup
Better checks in GRS decoders	#20177	Cleanup
Remove some deprecation warnings	#20685	Cleanup
Experimenting on codes	#18269	Structure & Content
GRS codes and dedicated encoders	#18928	Content
New decoders for GRS codes	#19653	Content
Guruswami-Sudan list-decoding	#19666	Content
Lee O'Sullivan for Guruswami-Sudan	#19722	Content
Punctured code + dedicated encoder and decoder	#19422	Content
Q-ary symmetric channel	#19511	Content
Syndrome decoder is a nearest neighbor decoder	#19623	Content
A proper class for Hamming codes	#19930	Content
A class for extended codes	#20124	Content
A class for non-prime fields embedding	#20284	Content
Base classes for Reed-Muller codes	#20705	Content
A class for subfield subcodes	#20039	Content
A class for a generic systematic encoder	#20835	Content
API thematic tutorial	#19745	Documentation
Introductory thematic tutorial	#19897	Documentation
LinearCode(C) for some code C should construct a code	#20198	Enhancement
Rewrite module doc of LinearCode	#20232	Enhancement
Improve efficiency of nearest neighbor decoder	#20201	Enhancement
Automatically register generic encoders/decoders in any code family	#20840	Enhancement
Improvements to systematic encoder	#21157	Enhancement
Fix LinearCode.wtdist_gap method	#20565	Defect
Fix some bugs in relative_field_extension.py	#20951	Defect

CC: @johanrosenkilde @jpflori @videlec @defeo @sagetrac-danielaugot @nthiery @jlavauzelle @ppurka @ClementPernet

Component: coding theory

Issue created by migration from https://trac.sagemath.org/ticket/18846

[johanrosenkilde]

comment:63

I've ported the information on this meta-page to a dedicated Trac Wiki roadmap page: https://trac.sagemath.org/wiki/SageCodingRoadMap

[johanrosenkilde]

comment:64

Closing, cf above.