Opened 5 years ago

Closed 5 years ago

Last modified 4 years ago

#20908 closed enhancement (fixed)

Rework index and catalogs in sage.coding

Reported by: dlucas Owned by:
Priority: major Milestone:
Component: coding theory Keywords: sd75, rd3
Cc: jsrn, cpernet, jlavauzelle, danielaugot, dimpase Merged in:
Authors: David Lucas, Johan Rosenkilde Reviewers: David Lucas, Johan Rosenkilde
Report Upstream: N/A Work issues:
Branch: u/jsrn/consistency_in_coding_catalogs (Commits, GitHub, GitLab) Commit: f64841fa72d117c16ef26a6e5f77f7910734d2ab
Dependencies: #21328 Stopgaps:

Status badges

Description

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.

Change History (39)

comment:1 Changed 5 years ago by dlucas

  • Branch set to u/dlucas/consistency_in_coding_catalogs

comment:2 Changed 5 years ago by dlucas

  • Authors set to David Lucas
  • Cc jsrn cpernet jlavauzelle danielaugot added
  • Commit set to 71655889e2dbb16d4473e49c1bc09eef1a2d2b79
  • Status changed from new to needs_info
  • Type changed from PLEASE CHANGE to enhancement

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:

182130fReworked encoders_catalog.py
91318b7Reworked decoders_catalog.py
66a5381Reworked channels_catalog.py
7165588Reworked codes_catalog.py

comment:3 Changed 5 years ago by jsrn

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 <mymodule>" 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

comment:4 Changed 5 years ago by git

  • Commit changed from 71655889e2dbb16d4473e49c1bc09eef1a2d2b79 to bb13162cca8d7c75f262f353ee718074c54b4123

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

0c944a8Updated to beta6 and fixed conflicts
fac7a9fAdded a link to Guruswami-Sudan decoder in grs.py module documentation
3e64538WIP index.rt
8d41ac3Changed index.rst
bb13162Removed duplicated reference to Huffman and Pless

comment:5 Changed 5 years ago by dlucas

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

comment:6 Changed 5 years ago by jsrn

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

comment:7 Changed 5 years ago by git

  • Commit changed from bb13162cca8d7c75f262f353ee718074c54b4123 to b63ee747dd8f93665500e57a584a488a26705a99

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

8d023c3Fixed conflicts after merge with 7.4b1
b63ee74Added missing copyright statement in codes_catalog.py

comment:8 Changed 5 years ago by dlucas

  • Milestone changed from sage-7.3 to sage-7.4

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

David

comment:9 Changed 5 years ago by dlucas

  • Keywords sd75 added

comment:10 Changed 5 years ago by danielaugot

"Copyright (C) 2009 David Lucas <david.lucas@…>" Hmmm... 2009 ? Daniel

comment:11 Changed 5 years ago by git

  • Commit changed from b63ee747dd8f93665500e57a584a488a26705a99 to d4a92ee4c84818a9edd1ac5b4bdbddc06b9d7cd7

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

d4a92eeFixed wrong date in copyright file

comment:12 Changed 5 years ago by dlucas

Oops. Fixed now.

comment:13 Changed 5 years ago by jsrn

  • Branch changed from u/dlucas/consistency_in_coding_catalogs to u/jsrn/consistency_in_coding_catalogs

comment:14 Changed 5 years ago by git

  • Commit changed from d4a92ee4c84818a9edd1ac5b4bdbddc06b9d7cd7 to d7f16de03523eec99b720c24d72abf6ef1aea7a7

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

b58ee63Merge branch '20908_rework_coding_index' into test
d7f16deSome more polishing

comment:15 Changed 5 years ago by jsrn

  • Status changed from needs_info to needs_review

I've reworked the titles. I couldn't get the "alternative-title <module>" 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.

comment:16 follow-up: Changed 5 years ago by 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.

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

comment:17 in reply to: ↑ 16 Changed 5 years ago by jsrn

Replying to 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.

comment:18 follow-up: Changed 5 years ago by dlucas

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.

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

comment:19 in reply to: ↑ 18 Changed 5 years ago by jsrn

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

comment:20 Changed 5 years ago by jsrn

  • Status changed from needs_review to needs_work

comment:21 Changed 5 years ago by git

  • Commit changed from d7f16de03523eec99b720c24d72abf6ef1aea7a7 to a557a22eda0224b481d1dbf6e5c204de076f6e6b

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

68032d4Merge branch 'u/jsrn/consistency_in_coding_catalogs' of trac.sagemath.org:sage into 20908_rework_coding_index
cb0b2b7Deprecate delsarte_bound funs from global name space. Lower-case Krouwchouk.
488a70eLinearCode should be in codes.<tab>
97326d6Some light polishing to reference manual index file
37cedbeBetter deprecation of Krawtchouk. Phasing out alternative spelling Kravchuk.
7db921fMissing HP reference
8111cafFix a reference problem
a557a22Changed to local reference syntax in hamming_code to stop Sphinx from complaining

comment:22 Changed 5 years ago by git

  • Commit changed from a557a22eda0224b481d1dbf6e5c204de076f6e6b to c802c817ec11fa895f5c0346e85a085a63cde2d5

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

6a38b4afixed broken refs
0425188replacing - by .. and more reformatting and cleanup
c802c81Merge ticket 21418 into 20908_rework_coding_index

comment:23 Changed 5 years ago by git

  • Commit changed from c802c817ec11fa895f5c0346e85a085a63cde2d5 to ac2dd765dade9ef19082563ab8ae558882c842b3

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

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

comment:24 Changed 5 years ago by jsrn

  • Status changed from needs_work to needs_review

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.

comment:25 Changed 5 years ago by jsrn

  • Authors changed from David Lucas to David Lucas, Johan Rosenkilde
  • Cc dimpase added

comment:26 Changed 5 years ago by ylchapuy

  • Status changed from needs_review to needs_work

needs rebase

comment:27 Changed 5 years ago by dlucas

  • Branch changed from u/jsrn/consistency_in_coding_catalogs to u/dlucas/consistency_in_coding_catalogs

comment:28 Changed 5 years ago by dlucas

  • Commit changed from ac2dd765dade9ef19082563ab8ae558882c842b3 to 19e299e308af3faa4101d63e8bd3ee84ccab1b06
  • Status changed from needs_work to needs_review

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:

8185e87Updated to latest beta and fixed conflicts
b77de0fAdded new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.
0b0d2f8Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__
62abcd7Fixed merge conflict.
1aa4b4eFixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.
19e299eMerged 21328 and fixed broken doctests

comment:29 Changed 5 years ago by dlucas

  • Keywords rd3 added

comment:30 Changed 5 years ago by dlucas

  • Dependencies set to #21328

comment:31 Changed 5 years ago by jsrn

  • Reviewers set to David Lucas, Johan Rosenkilde

comment:32 Changed 5 years ago by jsrn

  • Branch changed from u/dlucas/consistency_in_coding_catalogs to u/jsrn/consistency_in_coding_catalogs

comment:33 Changed 5 years ago by jsrn

  • Commit changed from 19e299e308af3faa4101d63e8bd3ee84ccab1b06 to f64841fa72d117c16ef26a6e5f77f7910734d2ab
  • Status changed from needs_review to positive_review

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


New commits:

f64841fMove cyclic code heading

comment:34 Changed 5 years ago by dimpase

  • Milestone changed from sage-7.4 to sage-7.6
  • Status changed from positive_review to needs_work

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.

comment:35 Changed 5 years ago by dimpase

  • Status changed from needs_work to positive_review

fixed by commit 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b on the #20787 branch.

comment:36 Changed 5 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:37 Changed 4 years ago by jdemeyer

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

comment:38 Changed 4 years ago by dimpase

  • Milestone changed from sage-7.6 to sage-8.0

comment:39 Changed 4 years ago by dimpase

  • Milestone sage-8.0 deleted
Note: See TracTickets for help on using tickets.