Opened 6 years ago
Closed 5 years ago
#20198 closed enhancement (fixed)
`LinearCode(C)` for some code `C` should construct a code
Reported by:  jsrn  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  coding theory  Keywords:  linear code, beginner 
Cc:  dlucas  Merged in:  
Authors:  Charles Prior  Reviewers:  Johan Sebastian Rosenkilde Nielsen 
Report Upstream:  N/A  Work issues:  
Branch:  6162d95 (Commits, GitHub, GitLab)  Commit:  6162d956dff16a29fa9a57fe28329473a8e1c706 
Dependencies:  Stopgaps: 
Description (last modified by )
With the recent subclassing 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.
Change History (15)
comment:1 Changed 6 years ago by
 Description modified (diff)
comment:2 Changed 5 years ago by
 Branch set to u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code
comment:3 Changed 5 years ago by
 Commit set to 84c1e39a4450f95d2c96ad9d6dbcf6bf80cec089
 Status changed from new to needs_review
comment:4 Changed 5 years ago by
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.
comment:5 Changed 5 years ago by
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
comment:6 followup: ↓ 9 Changed 5 years ago by
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
comment:7 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:8 Changed 5 years ago by
 Commit changed from 84c1e39a4450f95d2c96ad9d6dbcf6bf80cec089 to b1e49eacc83ca0ac69d042460ee6b65a028dd240
Branch pushed to git repo; I updated commit sha1. New commits:
b1e49ea  Logic simplified as per jsrn's suggestions.

comment:9 in reply to: ↑ 6 ; followup: ↓ 12 Changed 5 years ago by
Replying to jsrn:
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 thatbasis
is as long as the rank ofgenerator
is not necessary here and can be moved into thetry
block for the generator matrix case. And now the computation ofbasis
does not have to be done twice.Best, Johan
I implemented your suggestions, let me know what you think.
Replying to jsrn:
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 "supersedingdecode_to_code
"  that method is not superseded (contrarily, that anddecode_to_message
both supersededecode
).Best, Johan
Sorry I was unclear. I meant that decode_to_code
supersedes
decode
.
comment:10 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:11 Changed 5 years ago by
 Branch changed 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
comment:12 in reply to: ↑ 9 Changed 5 years ago by
 Commit changed from b1e49eacc83ca0ac69d042460ee6b65a028dd240 to 6162d956dff16a29fa9a57fe28329473a8e1c706
 Reviewers set to Johan Sebastian Rosenkilde Nielsen
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

comment:13 Changed 5 years ago by
Ah sorry that slipped my mind! I looked over the changes you made and they're fine, I also reran the doctests on the updated file just to make sure everything's okay as a thirdparty. I'll set the ticket to positive_review :)
Thanks, Charlie
P.S. Do we need to change the milestone to sage7.2? I branched from sage7.2.beta1 so we shouldn't need to merge anything in.
comment:14 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:15 Changed 5 years ago by
 Branch changed from u/jsrn/_linearcode_c___for_some_code__c__should_construct_a_code to 6162d956dff16a29fa9a57fe28329473a8e1c706
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
20198: 'LinearCode(C)' for some code 'C' should construct a code
Fixed bug (generator.basis()>generator.row_space().basis()) for original usecase; passed all doctests.
Fixed doc typo