Opened 4 years ago

Closed 3 years ago

#18846 closed task (invalid)

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

Reported by: dlucas Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: coding theory Keywords:
Cc: jsrn, jpflori, vdelecroix, defeo, danielaugot, nthiery, jlavauzelle, ppurka, cpernet Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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

Change History (65)

comment:1 Changed 4 years ago by dlucas

  • Cc jsrn jpflori vdelecroix defeo danielaugot nthiery added

comment:2 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:3 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:4 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:5 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:6 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:7 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:8 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:9 Changed 4 years ago by dlucas

  • Description modified (diff)
  • Milestone changed from sage-6.8 to sage-6.10

comment:10 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:11 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:12 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:13 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:14 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:15 Changed 4 years ago by dlucas

  • Description modified (diff)
  • Milestone changed from sage-6.10 to sage-7.1

comment:16 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:17 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:18 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:19 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:20 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:21 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:22 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:23 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:24 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:25 Changed 4 years ago by dlucas

  • Cc jlavauzelle added
  • Description modified (diff)

comment:26 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:27 Changed 4 years ago by ppurka

  • Cc ppurka added

comment:28 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:29 Changed 4 years ago by cpernet

  • Cc cpernet added

comment:30 Changed 4 years ago by jsrn

  • Description modified (diff)

comment:31 Changed 4 years ago by jsrn

  • Description modified (diff)

comment:32 Changed 4 years ago by dlucas

  • Description modified (diff)
  • Milestone changed from sage-7.1 to sage-7.2

comment:33 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:34 Changed 4 years ago by jsrn

  • Description modified (diff)

comment:35 Changed 4 years ago by jsrn

  • Description modified (diff)

comment:36 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:37 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:38 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:39 Changed 4 years ago by jsrn

  • Description modified (diff)

comment:40 Changed 4 years ago by dlucas

  • Description modified (diff)
  • Milestone changed from sage-7.2 to sage-7.3

comment:41 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:42 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:43 Changed 4 years ago by dlucas

  • Description modified (diff)

comment:44 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:45 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:46 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:47 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:48 Changed 3 years ago by jsrn

  • Description modified (diff)

comment:49 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:50 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:51 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:52 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:53 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:54 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:55 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:56 Changed 3 years ago by jsrn

  • Description modified (diff)

comment:57 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:58 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:59 Changed 3 years ago by dlucas

  • Description modified (diff)
  • Milestone changed from sage-7.3 to sage-7.4

comment:60 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:61 Changed 3 years ago by jsrn

  • Description modified (diff)

comment:62 Changed 3 years ago by dlucas

  • Description modified (diff)

comment:63 Changed 3 years ago by jsrn

  • Milestone changed from sage-7.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

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

comment:64 Changed 3 years ago by jsrn

  • Status changed from needs_review to positive_review

Closing, cf above.

comment:65 Changed 3 years ago by vbraun

  • Resolution set to invalid
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.