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

Priority:  major  Milestone:  sage7.1 
Component:  coding theory  Keywords:  linear code, beginner 
Cc:  David Lucas  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 7 years ago by
Description:  modified (diff) 

comment:2 Changed 7 years ago by
Branch:  → u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code 

comment:3 Changed 7 years ago by
Authors:  → Charles Prior 

Commit:  → 84c1e39a4450f95d2c96ad9d6dbcf6bf80cec089 
Status:  new → needs_review 
comment:4 Changed 7 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 7 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 7 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 7 years ago by
Status:  needs_review → needs_work 

comment:8 Changed 7 years ago by
Commit:  84c1e39a4450f95d2c96ad9d6dbcf6bf80cec089 → b1e49eacc83ca0ac69d042460ee6b65a028dd240 

Branch pushed to git repo; I updated commit sha1. New commits:
b1e49ea  Logic simplified as per jsrn's suggestions.

comment:9 followup: 12 Changed 7 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 7 years ago by
Status:  needs_work → needs_review 

comment:11 Changed 7 years ago by
Branch:  u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code → u/jsrn/_linearcode_c___for_some_code__c__should_construct_a_code 

comment:12 Changed 7 years ago by
Commit:  b1e49eacc83ca0ac69d042460ee6b65a028dd240 → 6162d956dff16a29fa9a57fe28329473a8e1c706 

Reviewers:  → 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 7 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
comment:14 Changed 7 years ago by
Status:  needs_review → positive_review 

comment:15 Changed 7 years ago by
Branch:  u/jsrn/_linearcode_c___for_some_code__c__should_construct_a_code → 6162d956dff16a29fa9a57fe28329473a8e1c706 

Resolution:  → fixed 
Status:  positive_review → 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