Tutorial for new structures in coding theory #19745

sagetrac-dlucas · 2015-12-18T14:54:29Z

This year, we reworked the API of Sage's coding theory library and now have an object-oriented structure to manage code families, encoders and decoders.

In this ticket we introduce a thematic tutorial which explains how to use this new API to develop new code families.

This tutorials relies on a step-by-step example, in which we construct a code, a few encoders for it, a decoder for it and a somehow related channel.

Component: coding theory

Author: David Lucas

Branch/Commit: 34019fe

Reviewer: Travis Scrimshaw, Julien Lavauzelle

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

The text was updated successfully, but these errors were encountered:

sagetrac-dlucas · 2015-12-18T14:55:46Z

Branch: u/dlucas/thematic_tutorial

sagetrac-dlucas · 2015-12-18T15:00:53Z

comment:2

I wrote the tutorial and pushed the branch which contains it...
But there's a bug I cannot fix:

anytime I try to compile the documentation, I receive the following error message:

OSError: [thematic_] /home/david/Desktop/sage_coding_project/src/doc/en/thematic_tutorials/structures_in_coding_theory.rst:: WARNING: document isn't included in any toctree

even after running make doc-clean and adding this tutorial to index.rst.
Thing is, my file appears in thematic_tutorials html index page, properly formatted...

If someone knows how to deal with it, I'll be glad!

In the meanwhile, one can still read this tutorial and do some comments ;)

David

New commits:

`2b0adb6`	`First version for the thematic tutorial`
`6a4c283`	`Added a new chapter which contains all the code ready for copy-paste`

sagetrac-dlucas · 2015-12-18T15:00:53Z

Commit: 6a4c283

johanrosenkilde · 2015-12-18T15:13:19Z

comment:3

I remember you mentioned this problem ages ago. Post on sage-devel if someone knows what it is.

sagetrac-git · 2015-12-18T15:31:34Z

Changed commit from 6a4c283 to eb5c686

sagetrac-git · 2015-12-18T15:31:34Z

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

`eb5c686`	`Fixed toctree bug and added a table of contents in the tutorial`

sagetrac-dlucas · 2015-12-18T15:32:52Z

comment:5

Ok, I got it in fine : you also have to add you document in toctree.rst.
Anyway, it works now!

sagetrac-git · 2015-12-18T15:52:27Z

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

`4726f90`	`Fixed inconsistency in names, fixed broken pointers to external methods`

sagetrac-git · 2015-12-18T15:52:27Z

Changed commit from eb5c686 to 4726f90

sagetrac-dlucas · 2015-12-18T15:53:10Z

comment:7

I fixed some bugs I found, this is still open for review.

sagetrac-git · 2016-01-06T13:28:02Z

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

`b5631d4`	`Update to 7.0beta2`
`1795b11`	`Fixed broken tests`

sagetrac-git · 2016-01-06T13:28:02Z

Changed commit from 4726f90 to 1795b11

sagetrac-dlucas · 2016-01-06T13:28:53Z

comment:9

I updated this ticket to latest beta, and fixed some broken tests.
This is still open for review.

tscrim · 2016-01-07T00:24:03Z

comment:10

Some comments:

The second line of
```
  ....: class BinaryRepetitionCode(AbstractLinearCode):
  ....:   _registered_encoders = {}
```
should be indented 4 spaces from the beginning of class to reflect Python coding conventions (similar changes are needed throughout the whole tutorial).
I would put all of these in ``code_format`` or :meth:`reference_them`:

- dimension,
- length,
- base_field and
- ambient space

This is not formatted properly. In particular, I would make these changes:

3. Add this line in the class' constructor::
+
-    super(ClassName, self).__init__(base_field, length, "DefaultEncoder", "DefaultDecoder")
+      super(ClassName, self).__init__(base_field, length, "DefaultEncoder", "DefaultDecoder")

Similar changes in Section VI.

All of those numbered points in the summary are missing periods.

You should make this change because \t is a tab character:

-return "\textnormal{Binary repetition code of length } %s" % self.length()
+return "\\textnormal{Binary repetition code of length } %s" % self.length()

It is considered better to have multiline statements wrapped in parentheses rather than use the line break \. The parentheses have the effect that it groups things together in logical units and the line break is not needed.
Errors should be phrases, and as such, should not start with a capital letter: DecodingFailure("impossible to find a majority")

Otherwise it looks good to me. (Although I'm somewhat torn about using contractions in tutorials/documentation. I leave that decision up to you.)

jlavauzelle · 2016-01-07T16:59:28Z

comment:11

Hi all,

I think most of the corrections have been done; I add a few comments:

The repetition code can correct up to :math: \lceil n-1/2 \rceil errors (you wrote n/2); you should also change the decoding_radius method in the code.
In decode_to_code: maybe you should return vector(GF(2), [GF(2).one()] * n] instead of vector(GF(2), [1] * n]; it's the same for 0.
Some typos: "all we have to do know is to implement", "we can store a lists".
In the channel: maybe change w[i] += 1 into w[i] += GF2.one().
You mixed message and word in:

def encode(self, message):
    return vector(GF(2), [word] * self.code().length())

You didn't repeat some of the previous fixes of your code, in the big scripts of part VII (for example: for i in sample(xrange(V.dimension(), number_err)), so that it doesn't compile. Take care to do it also for the fixes related to my comments.
I don't know if that's a real problem (that's also the case for other chapters): in the .pdf output of the tutorial, some code lines are cropped because they are too long.

Otherwise it looks fine!

Julien

sagetrac-git · 2016-01-08T09:55:08Z

Changed commit from 1795b11 to d2a05c3

sagetrac-git · 2016-01-08T09:55:08Z

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

`f2093e1`	`Integrated Travis' comments`
`48fd520`	`Integrated Julien's comments`
`d2a05c3`	`Removed all contractions`

sagetrac-dlucas · 2016-01-08T09:58:19Z

comment:13

Hello,

Thank you for your comments!

I fixed everything you noticed.
I also fixed a few more bugs I noticed, several syntax errors and inconsistencies (DecodingFailure against DecodingError as discussed in #18376) with the existing coding theory library naming conventions.

David

tscrim · 2016-01-10T00:30:50Z

comment:14

Two other things from me (last things, promise):

\mathbb{F}_{2} can use the standard Sage latex macro \GF{2} (it makes the docs uniform).
Where possible, keep line lengths under 80 characters. (I know this isn't possible for some of the code blocks, but in particular, in the tutorial's text this should be achievable).

@jlavauzelle Could you add your name to the reviewers list? Also, do you have any other comments?

tscrim · 2016-01-10T00:30:50Z

Reviewer: Travis Scrimshaw

jlavauzelle · 2016-01-10T10:16:38Z

comment:15

No more comment, it works for me.

jlavauzelle · 2016-01-10T10:16:38Z

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Julien Lavauzelle

sagetrac-git · 2016-01-11T09:24:34Z

Changed commit from d2a05c3 to 4e3c143

sagetrac-git · 2016-01-11T09:24:34Z

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

`4e3c143`	`All lines are now below 80 characters`

sagetrac-dlucas · 2016-01-11T09:26:06Z

comment:17

Two other things from me (last things, promise):

Done! And don't worry, I prefer this to stay a little longer in review and be perfect.
Especially I wasn't aware of the \GF macro, it will definitely save me some time later.

David

tscrim · 2016-01-12T13:18:38Z

Changed commit from 4e3c143 to 34019fe

tscrim · 2016-01-12T13:18:38Z

Changed branch from u/dlucas/thematic_tutorial to u/tscrim/coding_structures_thematic_tutorial-19745

tscrim · 2016-01-12T13:18:38Z

comment:18

I went through and made some other little tweaks in regards to little grammar and formatting things. If you're happy with my changes, then go ahead and set a positive review.

This is very well done tutorial, can we get you to write more (and for other areas of Sage)?

New commits:

`efcb779`	`Merge branch 'u/dlucas/thematic_tutorial' of trac.sagemath.org:sage into u/dlucas/thematic_tutorial`
`34019fe`	`Some little final tweaks.`

sagetrac-dlucas · 2016-01-12T14:00:59Z

comment:19

I went through and made some other little tweaks in regards to little grammar and formatting things. If you're happy with my changes, then go ahead and set a positive review.

I'm happy with the changes, thanks for the help! I'm giving the green light.

This is very well done tutorial, can we get you to write more (and for other areas of Sage)?

My plans was to rewrite the original thematic tutorial on coding theory, which can be quite improved according to me.

I'm actually working for Inria's ACTIS project which aims to enhance Sage's coding theory library, so I have to admit I barely looked at other tutorials ^^'

If you think I can improve some of these, I'll be happy to help!

David

tscrim · 2016-01-12T15:53:48Z

comment:20

Feel free to cc me on the tickets. I'd be happy to help where I can (although I can't do a mathematical review since I really don't know too much about coding theory).

vbraun · 2016-01-12T22:07:12Z

Changed branch from u/tscrim/coding_structures_thematic_tutorial-19745 to 34019fe

sagetrac-dlucas mannequin added this to the sage-7.0 milestone Dec 18, 2015

sagetrac-dlucas mannequin added c: coding theory labels Dec 18, 2015

sagetrac-dlucas mannequin added the s: needs info label Dec 18, 2015

sagetrac-dlucas mannequin added s: needs review and removed s: needs info labels Dec 18, 2015

sagetrac-dlucas mannequin added s: positive review and removed s: needs review labels Jan 12, 2016

vbraun removed the s: positive review label Jan 12, 2016

vbraun closed this as completed in 453256c Jan 12, 2016

sagetrac-dlucas mannequin mentioned this issue Jan 21, 2017

Meta-ticket: enhancement of the coding theory part of Sage #18846

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Tutorial for new structures in coding theory #19745

Tutorial for new structures in coding theory #19745

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

johanrosenkilde commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Jan 6, 2016

sagetrac-git mannequin commented Jan 6, 2016

sagetrac-dlucas mannequin commented Jan 6, 2016

tscrim commented Jan 7, 2016

jlavauzelle commented Jan 7, 2016

sagetrac-git mannequin commented Jan 8, 2016

sagetrac-git mannequin commented Jan 8, 2016

sagetrac-dlucas mannequin commented Jan 8, 2016

tscrim commented Jan 10, 2016

tscrim commented Jan 10, 2016

jlavauzelle commented Jan 10, 2016

jlavauzelle commented Jan 10, 2016

sagetrac-git mannequin commented Jan 11, 2016

sagetrac-git mannequin commented Jan 11, 2016

sagetrac-dlucas mannequin commented Jan 11, 2016

tscrim commented Jan 12, 2016

tscrim commented Jan 12, 2016

tscrim commented Jan 12, 2016

sagetrac-dlucas mannequin commented Jan 12, 2016

tscrim commented Jan 12, 2016

vbraun commented Jan 12, 2016

Tutorial for new structures in coding theory #19745

Tutorial for new structures in coding theory #19745

Comments

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

johanrosenkilde commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Dec 18, 2015

sagetrac-dlucas mannequin commented Dec 18, 2015

sagetrac-git mannequin commented Jan 6, 2016

sagetrac-git mannequin commented Jan 6, 2016

sagetrac-dlucas mannequin commented Jan 6, 2016

tscrim commented Jan 7, 2016

jlavauzelle commented Jan 7, 2016

sagetrac-git mannequin commented Jan 8, 2016

sagetrac-git mannequin commented Jan 8, 2016

sagetrac-dlucas mannequin commented Jan 8, 2016

tscrim commented Jan 10, 2016

tscrim commented Jan 10, 2016

jlavauzelle commented Jan 10, 2016

jlavauzelle commented Jan 10, 2016

sagetrac-git mannequin commented Jan 11, 2016

sagetrac-git mannequin commented Jan 11, 2016

sagetrac-dlucas mannequin commented Jan 11, 2016

tscrim commented Jan 12, 2016

tscrim commented Jan 12, 2016

tscrim commented Jan 12, 2016

sagetrac-dlucas mannequin commented Jan 12, 2016

tscrim commented Jan 12, 2016

vbraun commented Jan 12, 2016