q-ary symmetric channel class for coding theory

[sagetrac-dlucas]

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

Component: coding theory

Author: David Lucas

Branch/Commit: 2a041fb

Reviewer: Johan Sebastian Rosenkilde Nielsen

Issue created by migration from https://trac.sagemath.org/ticket/19511

[sagetrac-dlucas]

Branch: u/dlucas/qsc

[sagetrac-dlucas]

Commit: ebc58a1

[sagetrac-dlucas]

comment:2

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

---

New commits:

ebc58a1

Added new channel : q-ary symmetric channel

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-git]

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

f3887aa

Update to latest beta

[sagetrac-git]

Changed commit from ebc58a1 to f3887aa

[sagetrac-git]

Changed commit from f3887aa to 1a2c80f

[sagetrac-git]

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

1a2c80f

Updated to latest beta

[sagetrac-dlucas]

comment:5

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

---

New commits:

1a2c80f

Updated to latest beta

[johanrosenkilde]

Changed branch from u/dlucas/qsc to u/jsrn/qsc

[johanrosenkilde]

comment:7

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

[johanrosenkilde]

Changed commit from 1a2c80f to ac23bcc

[sagetrac-dlucas]

Changed branch from u/jsrn/qsc to u/dlucas/qsc

[sagetrac-dlucas]

Changed commit from ac23bcc to 429b290

[sagetrac-dlucas]

comment:9

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

[johanrosenkilde]

comment:10

The following doesn't work

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

[johanrosenkilde]

comment:11

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

[sagetrac-dlucas]

comment:12

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?

[johanrosenkilde]

comment:13

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.

[sagetrac-git]

Changed commit from 429b290 to 2a041fb

[sagetrac-git]

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

eb3349e	Moved text related to the shortcut for Chan.transmit()
35fa1fd	Removed code replication and fixed error in probability_of_at_most_t_errors
2a041fb	Fixed check on the input space

[sagetrac-dlucas]

comment:15

I made the changes, it should be better now.

[johanrosenkilde]

comment:16

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]

[johanrosenkilde]

Reviewer: Johan Sebastian Rosenkilde Nielsen

[vbraun]

Changed branch from u/dlucas/qsc to 2a041fb