LinearCode(C) for some code C should construct a code

[johanrosenkilde]

With the recent sub-classing framework for linear codes, it is now often useful to recast a code from some family as a generic linear code, thus forgetting its structure, e.g.

sage: C = codes.GeneralizedReedSolomonCode(GF(23).list(), 12)
sage: Chan = channels.StaticErrorRateChannel(GF(23)^7, 2)
sage: %timeit C.decode(Chan(C.random_element()))
<some short time>
sage: C_dumb = LinearCode(C)
sage: %timeit C_dumb.decode(Chan(C_dumb.random_element()))
<loong time>

Except the above code doesn't work, since LinearCode expects a matrix, and can't understand a code as input.

CC: @sagetrac-dlucas

Component: coding theory

Keywords: linear code

Author: Charles Prior

Branch/Commit: 6162d95

Reviewer: Johan Sebastian Rosenkilde Nielsen

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

[sagetrac-cprior]

Branch: u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code

[sagetrac-cprior]

Author: Charles Prior

[sagetrac-cprior]

Commit: 84c1e39

[sagetrac-cprior]

New commits:

52b22ba	20198: 'LinearCode(C)' for some code 'C' should construct a code
5c49bc4	Fixed bug (generator.basis()->generator.row_space().basis()) for original usecase; passed all doctests.
84c1e39	Fixed doc typo

[sagetrac-cprior]

comment:4

Note that the provided example (ignoring the part relating to the requested functionality) never worked. We have:

sage: C = codes.GeneralizedReedSolomonCode(GF(23).list(), 12)
sage: Chan = channels.StaticErrorRateChannel(GF(23)^7, 2)
sage: C.decode(Chan(C.random_element()))
Traceback (most recent call last)
...
TypeError: Message must be an element of the input space for the given channel

Perhaps you meant something more like this?

sage: C = codes.GeneralizedReedSolomonCode(GF(23).list(), 12)
sage: Chan = channels.StaticErrorRateChannel(GF(23)^23, 2)
sage: C.decode_to_code(Chan(C.random_element())) # using the superseding decode_to_code function
(10, 17, 5, 20, 9, 1, 3, 18, 8, 20, 13, 5, 20, 16, 12, 22, 18, 3, 13, 17, 11, 11, 4) # random

This doesn't affect my patch, unless you were to use this example to test it.

[johanrosenkilde]

comment:5

Awesome, thanks for the patch! I'll look at it momentarily.

You're right about my typo: it should have been ^23 and not ^7. What do you mean "superseding decode_to_code" -- that method is not superseded (contrarily, that and decode_to_message both supersede decode).

Best,
Johan

[johanrosenkilde]

comment:6

I think your logic can be simplified somewhat: In the code case, you should use something like generator = generator.generator_matrix() instead. You are promised that this is a full rank matrix (that's part of the contract of that method). So the check that basis is as long as the rank of generator is not necessary here and can be moved into the try block for the generator matrix case. And now the computation of basis does not have to be done twice.

Best,
Johan

[sagetrac-git]

Changed commit from 84c1e39 to b1e49ea

[sagetrac-git]

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

b1e49ea

Logic simplified as per jsrn's suggestions.

[sagetrac-cprior]

comment:9

Replying to @johanrosenkilde:

I think your logic can be simplified somewhat: In the code case, you should use something like generator = generator.generator_matrix() instead. You are promised that this is a full rank matrix (that's part of the contract of that method). So the check that basis is as long as the rank of generator is not necessary here and can be moved into the try block for the generator matrix case. And now the computation of basis does not have to be done twice.

Best,
Johan

I implemented your suggestions, let me know what you think.

Replying to @johanrosenkilde:

Awesome, thanks for the patch! I'll look at it momentarily.

You're right about my typo: it should have been ^23 and not ^7. What do you mean "superseding decode_to_code" -- that method is not superseded (contrarily, that and decode_to_message both supersede decode).

Best,
Johan

Sorry I was unclear. I meant that decode_to_code supersedes decode.

[johanrosenkilde]

Changed branch from u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code to u/jsrn/_linearcode_c___for_some_code__c__should_construct_a_code

[johanrosenkilde]

Changed commit from b1e49ea to 6162d95

[johanrosenkilde]

comment:12

I implemented your suggestions, let me know what you think.

You still needlessly recomputed basis so I removed that, and also removed some other minor recomputations (which are probably cached anyway, but still). Other than that your code looks good and I accept it. I've run tests on src/sage/coding and it's currently testing the rest of the Sage lib, but I'm not expecting any problems. If you can accept my changes, just set to positive_review :-)

Best,
Johan

---

New commits:

140a743	minor doc improvements
48ea66f	Merge branch 'u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code' of git://trac.sagemath.org/sage into 20198_linear_code_from_code
6162d95	Avoid some recomputations. Clarify a comment

[johanrosenkilde]

Reviewer: Johan Sebastian Rosenkilde Nielsen

[sagetrac-cprior]

comment:13

Ah sorry that slipped my mind! I looked over the changes you made and they're fine, I also re-ran the doctests on the updated file just to make sure everything's okay as a third-party. I'll set the ticket to positive_review :)

Thanks,
Charlie

P.S. Do we need to change the milestone to sage-7.2? I branched from sage-7.2.beta1 so we shouldn't need to merge anything in.

[vbraun]

Changed branch from u/jsrn/_linearcode_c___for_some_code__c__should_construct_a_code to 6162d95