Opened 6 years ago
Closed 6 years ago
#19511 closed enhancement (fixed)
qary symmetric channel class for coding theory
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage6.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: 
Description
This ticket proposes an implementation of qary symmetric channels using the structure described in #18269.
Change History (17)
comment:1 Changed 6 years ago by
 Branch set to u/dlucas/qsc
comment:2 Changed 6 years ago by
 Commit set to ebc58a141cef54897c6751dfd0598f29d2c54579
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Commit changed from ebc58a141cef54897c6751dfd0598f29d2c54579 to f3887aabf6b74cd1d8cf4518a5dde6f008dc6173
Branch pushed to git repo; I updated commit sha1. New commits:
f3887aa  Update to latest beta

comment:4 Changed 6 years ago by
 Commit changed from f3887aabf6b74cd1d8cf4518a5dde6f008dc6173 to 1a2c80fc81eb61d31a7dbee989839c2aae3b5cdc
Branch pushed to git repo; I updated commit sha1. New commits:
1a2c80f  Updated to latest beta

comment:5 Changed 6 years ago by
I updated this ticket to latest beta, it is still open for review.
New commits:
1a2c80f  Updated to latest beta

comment:6 Changed 6 years ago by
 Branch changed from u/dlucas/qsc to u/jsrn/qsc
comment:7 Changed 6 years ago by
 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 whileloop for adding errors.
Apart from that I have a few questions/requests:
 Should this channelintro text really be in the qary symmetric channels doc?
 Can you please make a test that input space is of the form Sigma^{n, 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:
ac23bcc  Fixed a nasty bug. Clarified documentation wrt. alphabet.

comment:8 Changed 6 years ago by
 Branch changed from u/jsrn/qsc to u/dlucas/qsc
comment:9 followup: ↓ 11 Changed 6 years ago by
 Commit changed from ac23bcc4387e05e1cdd5d8efd832381f59b7738f to 429b2902c76c94d63e0d9ab748fdbe6a5a100219
Hello,
Thanks for your remarks!
I agree with your clarifications, and of course with your fix.
Should this channelintro text really be in the qary 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 Sigma^{n, 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 Sigma^{n 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:
e52e959  Updated to 7.0

9a22432  Added checks on the input

429b290  Added methods to estimate the number of errors

comment:10 Changed 6 years ago by
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
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 Sigma^{n 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 bulletproofwhileflexible 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 takeepsilon
,t
andinput_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 nonstatic, after construction is
completely fine. Your implementation of at_most_t_errors
should sum over exactly_t_errors
to avoid codereplication. I'm pretty sure you have an offbyone 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
Just a simple question before working on this again:
Your implementation of at_most_t_errors should sum over exactly_t_errors to avoid codereplication.
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
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
 Commit changed from 429b2902c76c94d63e0d9ab748fdbe6a5a100219 to 2a041fb3fc70f562503f1e4dbacfc38a1fa958e9
comment:15 Changed 6 years ago by
I made the changes, it should be better now.
comment:16 Changed 6 years ago by
 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
 Branch changed from u/dlucas/qsc to 2a041fb3fc70f562503f1e4dbacfc38a1fa958e9
 Resolution set to fixed
 Status changed from positive_review to closed
I pushed the branch, this is now ready for review.
New commits:
Added new channel : qary symmetric channel