Opened 6 years ago

Closed 6 years ago

#19511 closed enhancement (fixed)

q-ary symmetric channel class for coding theory

Reported by: dlucas Owned by:
Priority: major Milestone: sage-6.10
Component: coding theory Keywords:
Cc: Merged in:
Authors: David Lucas Reviewers: Johan Sebastian Rosenkilde Nielsen
Report Upstream: N/A Work issues:
Branch: 2a041fb (Commits, GitHub, GitLab) Commit: 2a041fb3fc70f562503f1e4dbacfc38a1fa958e9
Dependencies: Stopgaps:

Status badges

Description

This ticket proposes an implementation of q-ary symmetric channels using the structure described in #18269.

Change History (17)

comment:1 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/qsc

comment:2 Changed 6 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to ebc58a141cef54897c6751dfd0598f29d2c54579
  • Status changed from new to needs_review

I pushed the branch, this is now ready for review.


New commits:

ebc58a1Added new channel : q-ary symmetric channel

comment:3 Changed 6 years ago by git

  • Commit changed from ebc58a141cef54897c6751dfd0598f29d2c54579 to f3887aabf6b74cd1d8cf4518a5dde6f008dc6173

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

f3887aaUpdate to latest beta

comment:4 Changed 6 years ago by git

  • Commit changed from f3887aabf6b74cd1d8cf4518a5dde6f008dc6173 to 1a2c80fc81eb61d31a7dbee989839c2aae3b5cdc

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

1a2c80fUpdated to latest beta

comment:5 Changed 6 years ago by dlucas

I updated this ticket to latest beta, it is still open for review.


New commits:

1a2c80fUpdated to latest beta

comment:6 Changed 6 years ago by jsrn

  • Branch changed from u/dlucas/qsc to u/jsrn/qsc

comment:7 Changed 6 years ago by jsrn

  • Commit changed from 1a2c80fc81eb61d31a7dbee989839c2aae3b5cdc to ac23bcc4387e05e1cdd5d8efd832381f59b7738f

Hi, I had a look at the code. It looks fine :-) I clarified some documentation wrt. alphabets and spaces, please look at that. I also fixed a bug in the while-loop for adding errors.

Apart from that I have a few questions/requests:

  • Should this channel-intro text really be in the q-ary symmetric channels doc?
  • Can you please make a test that input space is of the form Sigman, and that Sigma has random_element
  • It would be nice with a "probability_of_exactly_t_errors" and a "probability_of_at_most_t_errors" method :-) But I don't insist for now, the channel is functioning as it is.

Best, Johan


New commits:

ac23bccFixed a nasty bug. Clarified documentation wrt. alphabet.

comment:8 Changed 6 years ago by dlucas

  • Branch changed from u/jsrn/qsc to u/dlucas/qsc

comment:9 follow-up: Changed 6 years ago by dlucas

  • Commit changed from ac23bcc4387e05e1cdd5d8efd832381f59b7738f to 429b2902c76c94d63e0d9ab748fdbe6a5a100219

Hello,

Thanks for your remarks!

I agree with your clarifications, and of course with your fix.

Should this channel-intro text really be in the q-ary symmetric channels doc?

Well, I did that in the case one reads only the documentation for a channel class, and not the abstract class one. If you think it's useless, I'm ok to remove it.

Can you please make a test that input space is of the form Sigman, and that Sigma has random_element

Done. Note that I wasn't able to find an example of a Sigma which can be of the form Sigman but can not have a random_element method...

It would be nice with a "probability_of_exactly_t_errors" and a "probability_of_at_most_t_errors" method :-) But I don't insist for now, the channel is functioning as it is.

No need to insist, it's done ;) These two methods can be called on any instance of the class, with t as parameter. Maybe it can be better to propose generic methods, which take epsilon, t and input_space.dimension() as parameters, so the user can actually look for the best epsilon without having to construct the channel... As you prefer.

Best,

David


New commits:

e52e959Updated to 7.0
9a22432Added checks on the input
429b290Added methods to estimate the number of errors

comment:10 Changed 6 years ago by jsrn

The following doesn't work

sage: V = (ZZ.quo(12))^5
sage: Chan = channels.QarySymmetricChannel(V, .2)

comment:11 in reply to: ↑ 9 Changed 6 years ago by jsrn

Hi,

Well, I did that in the case one reads only the documentation for a channel class, and not the abstract class one. If you think it's useless, I'm ok to remove it.

I don't think it belongs there. But the text is nice, so perhaps it can be moved/merged somewhere else?

Done. Note that I wasn't able to find an example of a Sigma which can be of the form Sigman but can not have a random_element method...

Hmm, I'm worried that the check for the "dimension" method is not the right thing to do. For instance, the following structure has a "dimension":

   X = CombinatorialFreeModule(QQ, [1,2])

But I think that the last line of your transmit_unsafe is going to blow up on this structure. I don't think there is a bullet-proof-while-flexible way of checking for what we want. So perhaps your check at construction time could be a dummy transmit_unsafe call, and if that throws an exception, catch it and throw another exception telling the user that apparently his input space is not satisfactory.

Another thing: you added some text saying "the input space has to be a vector space", but if \Sigma is not a field, then \Sigma^3 is not a vector space: it is a free module with a basis. Just write something like I did in the docstring that we check input space has the form \Sigma^n.

No need to insist, it's done ;) These two methods can be called on any instance of the class, with t as parameter. Maybe it can be better to propose generic methods, which take epsilon, t and input_space.dimension() as parameters, so the user can actually look for the best epsilon without having to construct the channel... As you prefer.

Cool! I think having them available only non-static, after construction is completely fine. Your implementation of at_most_t_errors should sum over exactly_t_errors to avoid code-replication. I'm pretty sure you have an off-by-one error in the exactly_t_errors as well, since you're not summing the t'th error.

Best, Johan

comment:12 Changed 6 years ago by dlucas

Just a simple question before working on this again:

Your implementation of at_most_t_errors should sum over exactly_t_errors to avoid code-replication.

That was actually my first idea , but then I thought it's basically calling a method inside a loop. Well, I know it's not much of an optimization, but calling a method is slower than evaluating of an expression, isn't it?

comment:13 Changed 6 years ago by jsrn

True, but the loop is run t < n times, so it's not too bad. Better than code replication, I would say. Try to time it if you're worried.

comment:14 Changed 6 years ago by git

  • Commit changed from 429b2902c76c94d63e0d9ab748fdbe6a5a100219 to 2a041fb3fc70f562503f1e4dbacfc38a1fa958e9

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

eb3349eMoved text related to the shortcut for Chan.transmit()
35fa1fdRemoved code replication and fixed error in probability_of_at_most_t_errors
2a041fbFixed check on the input space

comment:15 Changed 6 years ago by dlucas

I made the changes, it should be better now.

comment:16 Changed 6 years ago by jsrn

  • Reviewers set to Johan Sebastian Rosenkilde Nielsen
  • Status changed from needs_review to positive_review

OK. I'm giving this the green light. I'm pretty psyked about the following "just working":

   sage: MS = MatrixSpace(GF(3), 4, 4)
   sage: Ch = channels.QarySymmetricChannel(MS, .3)
   sage: Ch(MS.zero())
   [0 0 0 1]
   [1 0 0 0]
   [0 2 1 2]
   [0 0 0 0]

comment:17 Changed 6 years ago by vbraun

  • Branch changed from u/dlucas/qsc to 2a041fb3fc70f562503f1e4dbacfc38a1fa958e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.