Tutorial for new structures in coding theory

[David Lucas]

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.

[David Lucas]

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

[Johan Rosenkilde]

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

[git]

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

​eb5c686

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

[David Lucas]

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

[git]

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

​4726f90

Fixed inconsistency in names, fixed broken pointers to external methods

[David Lucas]

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

[git]

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

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

[David Lucas]

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

[Travis Scrimshaw]

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

[Julien Lavauzelle]

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

[git]

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

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

[David Lucas]

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

[Travis Scrimshaw]

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?

[Julien Lavauzelle]

No more comment, it works for me.

[git]

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

​4e3c143

All lines are now below 80 characters

[David Lucas]

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

[Travis Scrimshaw]

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.

[David Lucas]

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

[Travis Scrimshaw]

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