Opened 3 years ago

Closed 2 years ago

#27634 closed enhancement (fixed)

Clean up the code and the documentation for the coding section

Reported by: klee Owned by:
Priority: minor Milestone: sage-8.9
Component: coding theory Keywords:
Cc: jsrn Merged in:
Authors: Kwankyu Lee Reviewers: Johan Rosenkilde
Report Upstream: N/A Work issues:
Branch: 8b01cc5 (Commits, GitHub, GitLab) Commit: 8b01cc5df9e1508250976b08b4d2212aecb02927
Dependencies: Stopgaps:

Status badges

Description (last modified by klee)

Lots of cleaning up of sage/coding folder:

  • reorganize the section on coding in the documentation
  • PEP8 fixes
  • 100% coverage for doctests
  • pyflakes fixes
  • rename bch.py to bch_code.py and grs.py to grs_code.py
  • cleanups for goppa.py
  • adding random_received_vector method to linear codes

and other small fixes.

Change History (41)

comment:1 Changed 3 years ago by klee

  • Authors set to Kwankyu Lee
  • Branch set to u/klee/27634

comment:2 Changed 3 years ago by git

  • Commit set to e0e2dd8a2817554b3f3802b5b3ade8a14b408a14

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

e0e2dd8Lots of code polishing

comment:3 Changed 3 years ago by klee

  • Description modified (diff)

comment:4 Changed 3 years ago by klee

  • Status changed from new to needs_review

comment:5 Changed 3 years ago by klee

  • Summary changed from Refine coding code and documentation to Refine the code and the documentation for `sage/coding` section

comment:6 Changed 3 years ago by klee

  • Summary changed from Refine the code and the documentation for `sage/coding` section to Refine the code and the documentation for coding section

comment:7 Changed 3 years ago by klee

  • Description modified (diff)

comment:8 Changed 3 years ago by git

  • Commit changed from e0e2dd8a2817554b3f3802b5b3ade8a14b408a14 to 8ca732d64a7f9562de77d990e5764991c5d58946

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

8ca732dRemoved a deprecation notice

comment:9 Changed 3 years ago by git

  • Commit changed from 8ca732d64a7f9562de77d990e5764991c5d58946 to f06f23f8a6e844cdc2c9f08af5794cb1def52a07

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

f06f23fFix a typo

comment:10 Changed 3 years ago by git

  • Commit changed from f06f23f8a6e844cdc2c9f08af5794cb1def52a07 to 9707a5dca4fe6a1c3ecc0da06f6bb6cfca4e503d

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

9707a5dMerge branch 'develop'

comment:11 Changed 2 years ago by klee

  • Description modified (diff)

comment:12 Changed 2 years ago by git

  • Commit changed from 9707a5dca4fe6a1c3ecc0da06f6bb6cfca4e503d to 4dbc2a812913fa1c37c4f0da2904cc3a62b78ef3

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

1458655Merge branch 'develop' into codes-trac27634
4dbc2a8Merge branch 'develop' into codes-trac27634

comment:13 Changed 2 years ago by klee

  • Summary changed from Refine the code and the documentation for coding section to Clean up the code and the documentation for the coding section

comment:14 Changed 2 years ago by klee

  • Description modified (diff)

comment:15 Changed 2 years ago by git

  • Commit changed from 4dbc2a812913fa1c37c4f0da2904cc3a62b78ef3 to dbb26e8a415d661814d9508e1a9005b008b6b807

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

dbb26e8Clean up coding section

comment:16 Changed 2 years ago by git

  • Commit changed from dbb26e8a415d661814d9508e1a9005b008b6b807 to ceb7dac3cd3b3de775315d5725f91eeaf50b5d36

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

ceb7dacMerge branch 'develop' into codes-1-trac27634

comment:17 Changed 2 years ago by git

  • Commit changed from ceb7dac3cd3b3de775315d5725f91eeaf50b5d36 to 870682867c2d45bd29e5920068af0b998493a6d8

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

a1eec5dMerge branch 'develop'
8706828Merge branch 'develop'

comment:18 Changed 2 years ago by git

  • Commit changed from 870682867c2d45bd29e5920068af0b998493a6d8 to 1223c53378d66b6e0e7984888a163e26d3a0b948

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

4fd1b78Merge fixes
1223c53Merge branch 'develop'

comment:19 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

comment:20 Changed 2 years ago by git

  • Commit changed from 1223c53378d66b6e0e7984888a163e26d3a0b948 to 835b5b5cc27447d6d36102e226c24b254ddf1666

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

8f81da2Merge branch 'develop'
171365fpyflakes fixes on goppa.py
835b5b5Docstring fixes for goppa.py

comment:21 Changed 2 years ago by klee

  • Description modified (diff)

comment:22 Changed 2 years ago by git

  • Commit changed from 835b5b5cc27447d6d36102e226c24b254ddf1666 to df55fbddeb9fc63c304dafc049f14b410d0891ef

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

df55fbdMore docstring fixes for goppa.py

comment:23 Changed 2 years ago by git

  • Commit changed from df55fbddeb9fc63c304dafc049f14b410d0891ef to 891e189dcf3fedb4ebc3c980520a393b2d601484

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

891e189Add AUTHORS section to goppa.py

comment:24 Changed 2 years ago by gh-927589452

removed was fixed in the latest of the commits

Last edited 2 years ago by gh-927589452 (previous) (diff)

comment:25 Changed 2 years ago by klee

  • Cc jsrn added

comment:26 Changed 2 years ago by git

  • Commit changed from 891e189dcf3fedb4ebc3c980520a393b2d601484 to c8706ee65c325376811df57fed19e9ed5851b9c2

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

902b750Merge branch 'develop'
c8706eeMerge branch 'develop'

comment:27 follow-up: Changed 2 years ago by jsrn

This is very nice and thorough cleanup. Here are some comments from glancing through the code (I'm currently compiling):

  • You've added forwarding of arguments to Decoder.connected_encoder(). But this is semantically not what was intended with the method. For decode_to_message, the decoder must have a specific type of encoder in mind (which is, in many cases, the same as having a specific generator matrix in mind), and this method enables the user to get exactly that encoder. So the user should not be required, indeed allowed, to supply any arguments to that encoder. How would he know which ones to give? If a sub-class of Decoder uses an encoder with specific arguments forwarded to it, then that decoder class must override connected_encoder and return the correct encoder. The _connected_encoder_name is simply a shorthand which covers most cases.

In short, I recommend you roll back this particular change.

  • Since we're already modifying _repr_ for Goppa code, let's add their field, i.e. change their representation to e.g. [8, 2] Goppa code over GF(2).
  • The documentation for __eq__ is unhelpful. Let's change it into something like
Test whether ``other`` defines the same Goppa code in the sense that defining
set and generating polynomial is the same.

And then under EXAMPLES document this surprising behaviour of equality:

Note that this check will be false if e.g. ``other`` represents the same
linear code as ``self`` but not constructed as a Goppa code:

sage: E = LinearCode(C.generator_matrix())
sage C == E
False

A similar caveat should be placed on several other code classes, actually. If you feel motivated to put those in, I'd be happy, but I'm not insisting ;-)

  • I disagree with your abbreviation in the first line of the module doc of grs_code.py. Writing out "Generalized Reed-Solomon codes" in full is more helpful.
  • The first line of the module doc of hamming_code.py should say "Hamming codes", plural.
  • Module doc of linear_code.py second paragraph
   (...) `n-k`-dimensional (...)  ->>  `(n-k)`-dimensional
  • In linear_code.py, I disagree with your abbreviation of the error message when using not registered encoders/decoders (around line 506). Your shorter error messages are much less helpful.
  • I'm not sure I like random_received_vector and its friend. It is a very specific use case to add exactly t errors to a codeword, and for this I don't mind the user typing out a few extra lines by using the StaticErrorRateChannel, which also introduces him/her to the much broader concept of channels. Rather, I'm in favour of adding to the class/module documentation how to use the channels (though it is also in the coding theory tutorial)

If you insist on those methods, random_received_vector_and_codeword could (should) be compactly implemented by using the StaticErrorRateChannel channel.

The documentation of the random_received_vector functions should perhaps be clarified by adding something like the following paragraph:

Note that even though the returned vector is assured to be distance exactly
``distance`` from some codeword in ``self``, it might still be closer than
``distance`` to another codeword if ``distance`` is more than `d/2`, where `d`
is the minimum distance of ``self``.

Perhaps random_received_vector_and_codeword should be obtained by an optional argument to random_received_vector called `return_codeword = False. Note that then the doc should have an OUTPUT` block to describe the output semantics.

The doc states that distance should be positive, but it should say "non-negative".

Best, Johan

comment:28 Changed 2 years ago by jsrn

  • Branch changed from u/klee/27634 to u/jsrn/27634

comment:29 follow-up: Changed 2 years ago by jsrn

  • Commit changed from c8706ee65c325376811df57fed19e9ed5851b9c2 to 0b95c1dfc649c6be392ce37499d28d386843b11a
  • I'm now browsing through the compiled doc of linear_code.py, and "self" (with only one back-tick) appears quite often. Please do a search-replace for this.
  • I disagree with your renaming "Derived code constructions" to "Code constructions" in the main doc for the coding module. The latter is very confusable with e.g. "the quadratic residue code construction", amplified by the file code_constructions.py containing exactly such constructions. I suggest using Derived codes or keeping Derived code constructions.
  • I discovered that the documentation for codes_catalog is completely broken (see under the main documentation of Coding, under "Index of code constructions"). The reason is that the introspective magic function that should generate the table doesn't really work with imported non-local classes. I've manually written the entire table in full and pushed that to the branch.

New commits:

0b95c1dManual table for codes_catalog.py

comment:30 in reply to: ↑ 27 Changed 2 years ago by klee

  • You've added forwarding of arguments to Decoder.connected_encoder(). But this is semantically not what was intended with the method. For decode_to_message, the decoder must have a specific type of encoder in mind (which is, in many cases, the same as having a specific generator matrix in mind), and this method enables the user to get exactly that encoder. So the user should not be required, indeed allowed, to supply any arguments to that encoder. How would he know which ones to give? If a sub-class of Decoder uses an encoder with specific arguments forwarded to it, then that decoder class must override connected_encoder and return the correct encoder. The _connected_encoder_name is simply a shorthand which covers most cases.

In short, I recommend you roll back this particular change.

I agree. Done rolling back.

  • Since we're already modifying _repr_ for Goppa code, let's add their field, i.e. change their representation to e.g. [8, 2] Goppa code over GF(2).

Done.

  • The documentation for __eq__ is unhelpful. Let's change it into something like
Test whether ``other`` defines the same Goppa code in the sense that defining
set and generating polynomial is the same.

I added your text after the original.

And then under EXAMPLES document this surprising behaviour of equality:

Note that this check will be false if e.g. ``other`` represents the same
linear code as ``self`` but not constructed as a Goppa code:

sage: E = LinearCode(C.generator_matrix())
sage C == E
False

Done.

A similar caveat should be placed on several other code classes, actually. If you feel motivated to put those in, I'd be happy, but I'm not insisting ;-)

This behavior of equality check is common in Sage. I don't worry much. But I will add more examples if I feel motivated :-)

  • I disagree with your abbreviation in the first line of the module doc of grs_code.py. Writing out "Generalized Reed-Solomon codes" in full is more helpful.

Right. Done.

  • The first line of the module doc of hamming_code.py should say "Hamming codes", plural.

Done.

  • Module doc of linear_code.py second paragraph
   (...) `n-k`-dimensional (...)  ->>  `(n-k)`-dimensional
  • In linear_code.py, I disagree with your abbreviation of the error message when using not registered encoders/decoders (around line 506). Your shorter error messages are much less helpful.

I felt that it was too much verbose. The user should learn what the message says from the documentation.

But ok as I respect your wisdom. I recovered the original message.

  • I'm not sure I like random_received_vector and its friend. It is a very specific use case to add exactly t errors to a codeword, and for this I don't mind the user typing out a few extra lines by using the StaticErrorRateChannel, which also introduces him/her to the much broader concept of channels. Rather, I'm in favour of adding to the class/module documentation how to use the channels (though it is also in the coding theory tutorial)

I added that when I was moving my code in Magma to Sage, without much appreciation of the channel concept myself. Now I see that random_received_vector does not fit well with the overall design of the coding module.

I decided to remove it.

comment:31 in reply to: ↑ 29 Changed 2 years ago by klee

Replying to jsrn:

  • I'm now browsing through the compiled doc of linear_code.py, and "self" (with only one back-tick) appears quite often. Please do a search-replace for this.

Done.

  • I disagree with your renaming "Derived code constructions" to "Code constructions" in the main doc for the coding module. The latter is very confusable with e.g. "the quadratic residue code construction", amplified by the file code_constructions.py containing exactly such constructions. I suggest using Derived codes or keeping Derived code constructions.

It seems a typo... I will keep Derived code constructions.

  • I discovered that the documentation for codes_catalog is completely broken (see under the main documentation of Coding, under "Index of code constructions"). The reason is that the introspective magic function that should generate the table doesn't really work with imported non-local classes. I've manually written the entire table in full and pushed that to the branch.

Merged. Fixed a doctest failure along with it.

comment:32 Changed 2 years ago by klee

  • Branch changed from u/jsrn/27634 to public/27634
  • Commit changed from 0b95c1dfc649c6be392ce37499d28d386843b11a to 24df329139c541b80a31b58bf6da8f4d1ea1cdc3

New commits:

fb35c2fFixes responding to reviewer comments
1bca13cMerge branch 'u/jsrn/27634'
6bf9f1eRemove unwanted names under codes
24df329A minor fix in the main document

comment:33 Changed 2 years ago by git

  • Commit changed from 24df329139c541b80a31b58bf6da8f4d1ea1cdc3 to 6c7012bcbb524f86d43ddf5e30b8cf8718032254

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

6c7012bA pyflakes fix in linear_code.py

comment:34 Changed 2 years ago by jsrn

  • Reviewers set to Johan Rosenkilde
  • Status changed from needs_review to positive_review

Great, thanks for reacting so fast! Let's get this into Sage :-) Positive review.

comment:35 Changed 2 years ago by git

  • Commit changed from 6c7012bcbb524f86d43ddf5e30b8cf8718032254 to c650b8aed9f43bc59fc2734ed70b11315490cb0f
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

c650b8aRename channel_constructions.py and goppa.py

comment:36 Changed 2 years ago by klee

Ah... I could not resist rushing these final changes to this ticket. Sorry.

I renamed "channel_constructions.py" to "channel.py" and "goppa.py" to "goppa_code.py". This seems to me more conforming to other file names.

I worry that you may object to the former change. If so, let me know.

comment:37 Changed 2 years ago by jsrn

  • Status changed from needs_review to positive_review

I'm OK with those changes, it's more conforming. Positive review.

comment:38 Changed 2 years ago by vbraun

  • Status changed from positive_review to needs_work

See patchbot: {{{sage -t --long src/doc/en/thematic_tutorials/structures_in_coding_theory.rst # 2 doc tests failed }}}

comment:39 Changed 2 years ago by git

  • Commit changed from c650b8aed9f43bc59fc2734ed70b11315490cb0f to 8b01cc5df9e1508250976b08b4d2212aecb02927

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

8b01cc5Rename coding theory module names in thematic tutorials

comment:40 Changed 2 years ago by klee

  • Status changed from needs_work to positive_review

Doctest failures in thematic tutorials were fixed by simple string replacements for changed module names.

comment:41 Changed 2 years ago by vbraun

  • Branch changed from public/27634 to 8b01cc5df9e1508250976b08b4d2212aecb02927
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.