Opened 5 years ago

Last modified 5 years ago

#21062 new task

How to store information on codes built from other ones

Reported by: jlavauzelle Owned by:
Priority: major Milestone: sage-7.3
Component: coding theory Keywords:
Cc: dlucas, jsrn, cpernet Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jlavauzelle)

This ticket is about discussing the way to store the information on the structure of codes built from other ones.

Change History (3)

comment:1 Changed 5 years ago by jlavauzelle

  • Cc dlucas jsrn cpernet added

If I understand it well, the new coding theory framework aims at keeping as much information as possible on the (algebraic) structure of the manipulated codes. I also noticed that this structure is memorized even after building a new code from older ones (I'll call this a "code derivation"). For instance, puncturing (resp. extension) is made in a way that the punctured (resp. extended) code keeps a pointer to the original code (and this is useful for decoding, or getting bounds on the parameters).

It's natural to think that in the future, Sage intents to have many other linear code derivations (dual code, sum, product or intersection of two codes, concatenation, trace code, subfield subcode, etc.). But I find a bit messy to define a class for each kind of derivation, especially for the sum and the dual code (I can't imagine a DualCode? or a SumCode? class).

If you agree with my feeling (of course it's arguable), maybe it would be better to instanciate these derivations in a different way.

I propose the following. Let C be a derived code (e.g. the dual of the intersection of two codes). When the user does this derivation, C won't be a DualCode object, but an instance of the LinearCode class. Now, to memorize where the derived code comes from, we could add to the (Abstract)LinearCode class:

  • an attribute _derivation_tree which stores the tree of operations (the internal nodes of the tree) made on original codes (the leaves of the tree) in order to get the derived code.
  • a method reduce(), or get_structured_representation(), which flattens the tree, that is, which builds an instance of a specific family of code (e.g. GRS code) corresponding to the derivation.

For instance, if C is the dual code of the intersection of two codes, then the attribute _derivation_tree will store the following tree :

        Dual
          |
     intersection
      |        |
     C_1      C_2

and the reduce() method will recursively try to give a structure to the intersection of the two codes and to the dual of the resulting code (if there is nothing to say, it outputs a LinearCode without specific structure, that is, with an empty tree).

Well, maybe these considerations come a bit early in the development, but I'll be glad to read your ideas about them.

Julien

comment:2 Changed 5 years ago by dlucas

Hello Julien,

Thanks for writing this! I think it's indeed a good idea to think about this, and I can't either imagine a DualCode class.

Elaborating a bit on your structure, -well, that's what we discussed a few hours ago ;)- I think we could implement a new decorator whose purpose would be to store the operations you describe in the _derivation_tree. With such a decorator, it will be extremely easy to set a new "transformation" method in the framework: just decorate this method, and every time it's called, the decorator takes care of building the tree from the input of your new "transformation" method.

It's the first idea that came to my mind, and is of course open to discussion!

David

comment:3 Changed 5 years ago by jlavauzelle

  • Description modified (diff)
  • Summary changed from How to store information on codes build from other ones to How to store information on codes built from other ones
Note: See TracTickets for help on using tickets.