Opened 6 years ago

Closed 6 years ago

#20198 closed enhancement (fixed)

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

Reported by: jsrn Owned by:
Priority: major Milestone: sage-7.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:

Status badges

Description (last modified by jsrn)

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 6 years ago by jsrn

  • Description modified (diff)

comment:2 Changed 6 years ago by cprior

  • Branch set to u/cprior/_linearcode_c___for_some_code__c__should_construct_a_code

comment:3 Changed 6 years ago by cprior

  • Authors set to Charles Prior
  • Commit set to 84c1e39a4450f95d2c96ad9d6dbcf6bf80cec089
  • Status changed from new to needs_review

New commits:

52b22ba20198: 'LinearCode(C)' for some code 'C' should construct a code
5c49bc4Fixed bug (generator.basis()->generator.row_space().basis()) for original usecase; passed all doctests.
84c1e39Fixed doc typo

comment:4 Changed 6 years ago by cprior

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.

Last edited 6 years ago by cprior (previous) (diff)

comment:5 Changed 6 years ago by 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 "superseding decode_to_code" -- that method is not superseded (contrarily, that and decode_to_message both supersede decode).

Best, Johan

comment:6 follow-up: Changed 6 years ago by 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 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 6 years ago by jsrn

  • Status changed from needs_review to needs_work

comment:8 Changed 6 years ago by git

  • Commit changed from 84c1e39a4450f95d2c96ad9d6dbcf6bf80cec089 to b1e49eacc83ca0ac69d042460ee6b65a028dd240

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

b1e49eaLogic simplified as per jsrn's suggestions.

comment:9 in reply to: ↑ 6 ; follow-up: Changed 6 years ago by cprior

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 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 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 "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.

comment:10 Changed 6 years ago by cprior

  • Status changed from needs_work to needs_review

comment:11 Changed 6 years ago by jsrn

  • 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 6 years ago by jsrn

  • 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:

140a743minor doc improvements
48ea66fMerge 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
6162d95Avoid some recomputations. Clarify a comment

comment:13 Changed 6 years ago by cprior

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

Version 0, edited 6 years ago by cprior (next)

comment:14 Changed 6 years ago by cprior

  • Status changed from needs_review to positive_review

comment:15 Changed 6 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.