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: | sage-7.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 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.
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 follow-up: 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 follow-up: 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 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.
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