Abstract Code Class

[emes4]

AbstractLinearCode is at the moment the most abstract representation of codes in Sage. This makes it very difficult to implement non-linear codes and also codes with a metric different than Hamming.

We propose to create AbstractCode class that will contain metric-agnostic methods, as well as the encoder/decoder framework. AbstractLinearCode will derive from this class.

Depends on #27634

CC: @dimpase @johanrosenkilde @xcaruso @Adurand8

Component: coding theory

Keywords: gsoc19

Author: Marketa Slukova

Branch/Commit: 4dbc878

Reviewer: Dima Pasechnik, Durand Amaury

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

[emes4]

Author: Marketa Slukova

[emes4]

Branch: u/emes4/abstract_code

[emes4]

Commit: ba4fc53

[emes4]

New commits:

f4767e0	AbstractCode class created, cut relevant methods from linear_code.py
2cc4c72	Reverted base_field and length to be only in linear_code.py
64f446a	Merge branch 'develop' of git://trac.sagemath.org/sage into abstract_code
53e445b	added base_ring and length parameter to AbstractCode
5e6dffe	Fixed some dependencies. Category still set up wrong.
ba4fc53	Merge branch 'abstract_code' into t/28073/abstract_code

[emes4]

Changed branch from u/emes4/abstract_code to u/gh-emes4/coding/abstract_code

[dimpase]

comment:5

you've checked in uncleanly merged/rebased things, e.g.

+>>>>>>> 4f44acd853... Fixed some dependencies. Category still set up wrong.

please look at >>>>, <<<<, and ==== markers in these files, clean them up.

[sagetrac-git]

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

e8edfeb

Fixed unclean merge.

[sagetrac-git]

Changed commit from ba4fc53 to e8edfeb

[emes4]

comment:7

Replying to @dimpase:

Sorry about that, it showed me the cleaned up file in my editor.

[emes4]

comment:8

I created the class AbstractCode and moved all the relevant methods from AbstractLinearCode.

Originally, I had default_encoder and default_decoder parameters in the initialisation of AbstractCode, however, I ran into an issue with dependencies - if I set a default_encoder for AbstractLinearCode, this would then be the default for all the codes inheriting from this. I am sure that this can be fixed, however maybe it makes sense for classes such as AbstractLinearCode to not have default decoders/encoders?

Finally, one of the doc tests fails. I tried to set up the category stuff (Parent.__init__()), but I don't think I did it correctly.

This is just a rough, first draft.

[sagetrac-git]

Changed commit from e8edfeb to 880aebb

[sagetrac-git]

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

880aebb

Fixed default decoder/encoder dependencies. Set to None by default.

[dimpase]

Changed keywords from none to gsoc19

[johanrosenkilde]

comment:11

Thanks for working on this! I took a quick view over the new class, and it looks good. There are some copy/paste errors in the documentation where it refers to AbstractLinearCode or "this linear code" etc., but that's small stuff.

More importantly, I am worried about how AbstractCode should fit into the category framework. In particular, a non-linear code is not necessarily a module. Also, some objects people call codes are not even inside some free module like R^n for some ring R, e.g. polyalphabetic codes like Chinese Remainder Codes or Polynomial Remainder codes, which are inside A_1 x A_2 x ... x A_n for some rings A_i. Really, the most general notion of a code is just a subset of some set, which isn't saying much.

Perhaps, as we're now talking of a really base class for all codes, AbstractCode should therefore simply omit setting up anything in the category framework, leaving that to more concrete implementations. The task of AbstractCode would then basically only consist of setting up the encoder/decoder framework, as well as providing the metric method, which I like (I guess list() is fine too). It shouldn't even have a length I guess?

In this case, I don't know whether AbstractCode should somehow otherwise be made a parent in the category framework, or whether we should agree that this is a "contract" that sub-classes have to do themselves.

Best,
Johan

[sagetrac-git]

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

d115600

No category set up and base_field in AbstractCode. No encoder/decoder error msgs. Documentation and tests.

[sagetrac-git]

Changed commit from 880aebb to d115600

[emes4]

comment:13

I made all the changes we discussed, namely:

The category framework is no longer set up in AbstractCode. Instead of inheriting from Module, it now inherits from Parent. I tried a few things, e.g. SageObject, Set here and Parent seemed to do the trick. I added some documentation hopefully instructing the user on how to set the category framework up.

I took base_field away from the initiating parameters of AbstractCode. This should be the only change in AbstractLinearCode.

The decoder and encoder methods now instruct the user to add a decoder/encoder for the code if they try to use the encoder/decoder framework without having set these up. I added tests for these. If there are no default encoders/decoders, the methods decoders_available and encoders_available return an empty list. Let me know if all the checks for None are correctly set up.

I extended the documentation and following the example of AbstractLinearCode, added an example of how to use AbstractCode to create a subclass.

A lot of the documentation overlaps with AbstractLinearCode, however I don't think this is an issue.

[dimpase]

comment:14

please push your updates...

[sagetrac-git]

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

2bf73f8	Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
487e9e2	Category related methods added. Encoder/decoder documentation specified for linear codes.

[sagetrac-git]

Changed commit from d115600 to 487e9e2

[emes4]

comment:16

Added methods __iter__ and __contains__ to AbstractCode instructing the user to override them.

Changed Encoder and Decoder class documentation to instruct the user to inherit from these when working with linear codes (over any metric).

[sagetrac-git]

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

40df01e

Finished up documentation.

[sagetrac-git]

Changed commit from 487e9e2 to 40df01e

[johanrosenkilde]

comment:45

Replying to @dimpase:

endomorphism ring provides maps onto subcodes, which does not look as totally useless to me.

Quite true. I have never seen people study it, but probably some people have. And it does have the same type of meaning as automorphism_group_gens. It's just inconsistent and unfortunate that that method is not called automorphism_ring and wraps the returned generators in some appropriate algebraic object.

changing the ring (taking a bigger ring) produces an additive code.

OK, I'm not familiar with those. But of course you can take a linear code over some field F_q and then consider its generator matrix as part of F_{q^m} and look at the code there. That would even be trivial to implement (but does not belong in this ticket).

[johanrosenkilde]

comment:46

Replying to @emes4:

I did all the changes, namely added Module to inheritance of AbstractLinearCode, merged #27634, added ambient_space method to AbstractCode with a recommendation to implement it, and moved __call__ from AbstractLinearCode to AbstractCode.

Awesome! I'm happy now :-) Dima, your turn ;-)

[dimpase]

comment:47

I am getting (on the branch of the ticket)

sage -t --warn-long 47.5 src/doc/en/thematic_tutorials/structures_in_coding_theory.rst
**********************************************************************
File "src/doc/en/thematic_tutorials/structures_in_coding_theory.rst", line 450, in doc.en.thematic_tutorials.structures_in_coding_theory
Failed example:
    from sage.coding.channel_constructions import Channel
Exception raised:
    Traceback (most recent call last):
      File "/home/dimpase/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/dimpase/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1105, in compile_and_execute
        exec(compiled, globs)
      File "<doctest doc.en.thematic_tutorials.structures_in_coding_theory[0]>", line 1, in <module>
        from sage.coding.channel_constructions import Channel
    ImportError: No module named channel_constructions
**********************************************************************
File "src/doc/en/thematic_tutorials/structures_in_coding_theory.rst", line 451, in doc.en.thematic_tutorials.structures_in_coding_theory
Failed example:
    class BinaryStaticErrorRateChannel(Channel):
        def __init__(self, space, number_errors):
            if space.base_ring() is not GF(2):
                raise ValueError("Provided space must be a vector space over GF(2)")
            if number_errors > space.dimension():
                raise ValueErrors("number_errors cannot be bigger than input space's dimension")
            super(BinaryStaticErrorRateChannel, self).__init__(space, space)
            self._number_errors = number_errors
Exception raised:
    Traceback (most recent call last):
      File "/home/dimpase/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/dimpase/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1105, in compile_and_execute
        exec(compiled, globs)
      File "<doctest doc.en.thematic_tutorials.structures_in_coding_theory[1]>", line 1, in <module>
        class BinaryStaticErrorRateChannel(Channel):
    NameError: name 'Channel' is not defined
**********************************************************************
1 item had failures:
   2 of  45 in doc.en.thematic_tutorials.structures_in_coding_theory
    [28 tests, 2 failures, 0.11 s]

[dimpase]

comment:48

there is also a typo, please apply the following:

--- a/src/sage/coding/abstract_code.py
+++ b/src/sage/coding/abstract_code.py
@@ -353,7 +353,7 @@ class AbstractCode(Parent):
         r"""
         Return an error stating ``ambient_space`` of ``self`` is not implemented.
 
-        This method is required by the :method:`__call__`.
+        This method is required by the :meth:`__call__`.
 
         EXAMPLES::
 

[sagetrac-git]

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

3996761	Merge commit '8b01cc5df9e1508250976b08b4d2212aecb02927' of git://trac.sagemath.org/sage into t/28073/abstract_code
a4582a3	Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
4dbc878	documentation fix

[sagetrac-git]

Changed commit from 318b444 to 4dbc878

[emes4]

comment:50

Replying to @dimpase:

I am getting (on the branch of the ticket)

This was an error coming from #27634, #27634 comment:40. It was fixed on the ticket, I merged the updated branch.

I fixed the small documentation mistake.

I ran the whole test suite make ptestlong and there were no errors.

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:52

looks good

[Adurand8]

Changed reviewer from Dima Pasechnik to Dima Pasechnik, gh-Adurand8

[dimpase]

comment:56

reviewer names should be real names.

[Adurand8]

comment:57

Sorry, I missed this information. It's corrected !

[Adurand8]

Changed reviewer from Dima Pasechnik, gh-Adurand8 to Dima Pasechnik, Durand Amaury

[fchapoton]

comment:58

moving milestone to 9.0 (after release of 8.9)

[vbraun]

Changed branch from u/gh-emes4/coding/abstract_code to 4dbc878