Rework index and catalogs in sage.coding

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Branch: u/dlucas/consistency_in_coding_catalogs

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Commit: 7165588

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7165588 to bb13162

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bb13162 to b63ee74

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:8

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

David

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Changed keywords from none to sd75

[0606207b-931f-4eb8-aaff-b4a0f8d02780]

comment:10

"Copyright (C) 2009 David Lucas david.lucas@inria.fr" Hmmm... 2009 ? Daniel

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b63ee74 to d4a92ee

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d4a92ee

Fixed wrong date in copyright file

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:12

Oops. Fixed now.

[johanrosenkilde]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:16

Hello,

codes.LinearCode is not available anymore, which breaks several doctests in linear_code.py.

Which makes me wonder: as we're cleaning up some import mess here, should we remove the last codes families from the global namespace at the same time? Before your changes, it was possible to build a linear code by using LinearCode or codes.LinearCode. I propose to deprecate LinearCode from the global namespace and keep only codes.LinearCode, and do the same with LinearCodeFromVectorSpace.

Another one: there are some other things available in the global namespace (Krawtchouk, Kravchuk,delsarte_bound_hamming_space,delsarte_bound_additive_hamming_space`). Should we clean that as well?

Another remark: it's probably not necessary to move guruswami_sudan/rootfinding, as #21331 simply deletes this module (actually, it moves it from coding to polynomials). By the way, I guess we should manually merge #21331 with this ticket, as I'm afraid they will conflict.

Otherwise, it looks good. Thanks for taking care of the rephrasing.

David

[johanrosenkilde]

comment:17

Replying to @sagetrac-dlucas:

Hello,

codes.LinearCode is not available anymore, which breaks several doctests in linear_code.py.

Which makes me wonder: as we're cleaning up some import mess here, should we remove the last codes families from the global namespace at the same time? Before your changes, it was possible to build a linear code by using LinearCode or codes.LinearCode. I propose to deprecate LinearCode from the global namespace and keep only codes.LinearCode, and do the same with LinearCodeFromVectorSpace.

Hmm, comparing with Graph and graphs.<tab>, then LinearCode should be in the global namespace but not the catalog. I think this makes sense. I'm OK with putting LinearCode in codes if you insist, but I would prefer LinearCode to stay in the global namespace.

Another one: there are some other things available in the global namespace (Krawtchouk, Kravchuk,delsarte_bound_hamming_space,delsarte_bound_additive_hamming_space`). Should we clean that as well?

I agree, let's fix this now.

Another remark: it's probably not necessary to move guruswami_sudan/rootfinding, as #21331 simply deletes this module (actually, it moves it from coding to polynomials). By the way, I guess we should manually merge #21331 with this ticket, as I'm afraid they will conflict.

Good point, we should do that.

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:18

Hmm, comparing with Graph andgraphs., thenLinearCodeshould be in the global namespace > but not the catalog. I think this makes sense. I'm OK with puttingLinearCodein codes if you > insist, but I would preferLinearCode` to stay in the global namespace.

Ok, if Graphs does the same, let's be consistent with it and keep LinearCode in the global namespace.

Will you take of the other changes, or do you prefer me to do it?

David

[johanrosenkilde]

comment:19

Will you take of the other changes, or do you prefer me to do it?

I have no problem doing it, but I won't have time today. If you want to, please go ahead, and I'll review your changes.

Best, Johan

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

68032d4	Merge branch 'u/jsrn/consistency_in_coding_catalogs' of trac.sagemath.org:sage into 20908_rework_coding_index
cb0b2b7	Deprecate delsarte_bound funs from global name space. Lower-case Krouwchouk.
488a70e	LinearCode should be in codes.
97326d6	Some light polishing to reference manual index file
37cedbe	Better deprecation of Krawtchouk. Phasing out alternative spelling Kravchuk.
7db921f	Missing HP reference
8111caf	Fix a reference problem
a557a22	Changed to local reference syntax in hamming_code to stop Sphinx from complaining

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d7f16de to a557a22

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6a38b4a	fixed broken refs
0425188	replacing - by .. and more reformatting and cleanup
c802c81	Merge ticket 21418 into 20908_rework_coding_index

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a557a22 to c802c81

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ac2dd76

Improved some more module doc strings. Fixed a merge bug. Added a ref to Feulner.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c802c81 to ac2dd76

[johanrosenkilde]

comment:24

I've done the updates suggested by David: restore LinearCode into codes.<tab>, deprecated Krawtchouk etc. from global namespace, and merged in #21331. I've also merged in #21418 which touched many of the same things as this ticket. I've also further polished some module doc strings etc.

Back to needs review.

[johanrosenkilde]

Changed author from David Lucas to David Lucas, Johan Rosenkilde

[2c00b582-cfe9-43b9-8124-fec470060704]

comment:26

needs rebase

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Changed commit from ac2dd76 to 19e299e

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Changed keywords from sd75 to sd75, rd3

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

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 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b on the #20787 branch.

[jdemeyer]

comment:37

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