Rework index and catalogs in sage.coding

[sagetrac-dlucas]

Catalogs of codes/encoders/decoders and index.rst file in sage.coding contains several problems:

• some references are missing, some other are duplicated,
• classes are listed without any specific order, and
• catalogs randomly use import and lazy_import.

This ticket fixes these problems.

Depends on #21328

CC: @johanrosenkilde @ClementPernet @jlavauzelle @sagetrac-danielaugot @dimpase

Component: coding theory

Keywords: sd75, rd3

Author: David Lucas, Johan Rosenkilde

Branch/Commit: u/jsrn/consistency_in_coding_catalogs @ f64841f

Reviewer: David Lucas, Johan Rosenkilde

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

[sagetrac-dlucas]

Branch: u/dlucas/consistency_in_coding_catalogs

[sagetrac-dlucas]

comment:2

I pushed some fixes.

A few remarks:

• I did not change index.rst... Yet. In this file, I introduced a set of headlines in Clean-up index of modules for coding theory #19907, and some of them might not the best. What do you think should be changed?
• Everything is now alphabetically sorted in *_catalog.py.
• Everything is now lazy imported in *_catalog.py...
• But Guruswami-Sudan decoder, because lazy importing it creates some errors in the decoder registration framework. It's possible to work around by moving the registration from gs_decoder.py to grs.py, but in that case, because of the lazy import being triggered by a call to codes.<tab>, it's not possible to write from guruswami_sudan.gs_decoder import n_k_params which creates errors in the doctesting framework...
  If you have an idea to fix this, I'm interested.

Best,

David

---

New commits:

182130f	Reworked encoders_catalog.py
91318b7	Reworked decoders_catalog.py
66a5381	Reworked channels_catalog.py
7165588	Reworked codes_catalog.py

[sagetrac-dlucas]

Commit: 7165588

[sagetrac-dlucas]

Author: David Lucas

[johanrosenkilde]

comment:3

Suggestion for headlines in index.rst. Note that I'm not including every single module; I'm not sure that makes sense.

You can change the title a module gets in a toc by writing "This is my title " instead of simply "mymodule".

# Coding Theory objects

- Linear Code and its abstract base class
- Decoder
- Encoder
- Channel

# Catalogs

- Index of channels
- Index of codes
- Index of decoders
- Index of encoders

# Code Constructions

- Constructing a linear code given a generator matrix <linear_code>

The named code families below are represented in Sage by their own classes, allowing specialised implementations of e.g. decoding or computation of properties. 

- Generalized Reed-Solomon code
- Hamming code

In contrast, for some code families Sage can only construct their generator matrix and has no other a priori knowledge on them.

- Code families whose generator matrix can be constructed
- Generator matrices construced using GAP-Guava
- Database of two-weight codes
- Self-dual binary codes
- Binary codes, fast implementation


# Methods and Operations related to Linear Codes

- Bounds on linear codes <index of bounds>
- Delsarte upper bounds, a.k.a. Linear Programming upper bounds
- Canonical forms and automorphisms for linear codes over finite fields


# Source coding

- Huffman Encoding


# Indices and Tables
- Bla bla

Other notes:

• It's a pity that Guruswami--Sudan is not easily seen when browsing Reed--Solomon codes. It could be added with a note to the top of the doc of grs.py.
• The module code_bounds is just a messy version of the index of bounds. So do we want a link to it? Further, I didn't put this index under "Catalogs" since its more of a module than a catalogue. Also, it's semi-deprecated so we don't want to give it too much attention ;-)

Best,
Johan

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0c944a8	Updated to beta6 and fixed conflicts
fac7a9f	Added a link to Guruswami-Sudan decoder in grs.py module documentation
3e64538	WIP index.rt
8d41ac3	Changed index.rst
bb13162	Removed duplicated reference to Huffman and Pless

[sagetrac-git]

Changed commit from 7165588 to bb13162

[sagetrac-dlucas]

comment:5

Hello,

I fixed some of the things you mentioned:

• I added a proper link to Guruswami-Sudan decoder in grs.py
• I reformatted index.rst as advised (I agree with you about not including every module BTW)

There's still some minor things to change (e.g. change headlines in linear_code.py), which
I would have done easily if I was not facing the weirdest of errors: when I rebuilt documentation after the changes in commit 8d41ac4, everything went fine. Then, I switched branches and when I came back to this branch, some errors appeared when running make:

[dochtml] OSError: [coding   ] /home/david/Desktop/sage/src/doc/en/reference/coding/index.rst:10:
WARNING: toctree contains reference to nonexisting document u'sage/coding/linear_code'

I moved this block, and it went fine. To be sure, I ran again make doc-clean and make and got the same error I just fixed?!

I pushed the changes anyway... Can one of you run it on your machine and let me know what happens?

David

[johanrosenkilde]

comment:6

Unfortunately building the Sage doc (and severala other things) currently doesn't work at all on my machine, so I can't really try to replicate your problem.
Best,
Johan

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8d023c3	Fixed conflicts after merge with 7.4b1
b63ee74	Added missing copyright statement in codes_catalog.py

[sagetrac-git]

Changed commit from bb13162 to b63ee74

[sagetrac-dlucas]

comment:8

I just fixed merge conflicts with latest beta and pushed that fix.

David

[sagetrac-dlucas]

Changed keywords from none to sd75

[sagetrac-danielaugot]

comment:10

"Copyright (C) 2009 David Lucas [email protected]" Hmmm... 2009 ? Daniel

[sagetrac-git]

Changed commit from b63ee74 to d4a92ee

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d4a92ee

Fixed wrong date in copyright file

[sagetrac-dlucas]

comment:12

Oops.
Fixed now.

[johanrosenkilde]

Changed branch from u/dlucas/consistency_in_coding_catalogs to u/jsrn/consistency_in_coding_catalogs

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b58ee63	Merge branch '20908_rework_coding_index' into test
d7f16de	Some more polishing

[sagetrac-git]

Changed commit from d4a92ee to d7f16de

[johanrosenkilde]

comment:15

I've reworked the titles. I couldn't get the "alternative-title " syntax to work either, so I instead rephrased the name of many modules in the first line of their doc-strings. I also moved some more around with the categories etc. since Sphinx was complaining if a module was not present at all.

[sagetrac-dlucas]

Changed commit from ac2dd76 to 19e299e

[sagetrac-dlucas]

comment:28

I updated this ticket to the latest branch, merged #21328 in to avoid further conflicts, and fixed a couple of broken doctests.
I agree with Johan's changes from 5 months ago.

---

New commits:

8185e87	Updated to latest beta and fixed conflicts
b77de0f	Added new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.
0b0d2f8	Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__
62abcd7	Fixed merge conflict.
1aa4b4e	Fixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.
19e299e	Merged 21328 and fixed broken doctests

[sagetrac-dlucas]

Changed keywords from sd75 to sd75, rd3

[sagetrac-dlucas]

Dependencies: #21328

[johanrosenkilde]

Reviewer: David Lucas, Johan Rosenkilde

[johanrosenkilde]

Changed branch from u/dlucas/consistency_in_coding_catalogs to u/jsrn/consistency_in_coding_catalogs

[johanrosenkilde]

comment:33

Small last-minute fix due to hasty merge. All else seems good.

---

New commits:

f64841f

Move cyclic code heading

[johanrosenkilde]

Changed commit from 19e299e to f64841f

[dimpase]

comment:34

please have a look at the 2nd part of comment 35, and at comment 37 of #20787.
Well, I can fix it there, but by right it should be done here.

[dimpase]

comment:35

fixed by commit 801dc10 on the #20787 branch.

[jdemeyer]

comment:37

In #22796, I will change the deprecated_callable_import here to a lazy import with deprecation.