Opened 5 years ago

Closed 5 years ago

#19745 closed enhancement (fixed)

Tutorial for new structures in coding theory

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.0
Component: coding theory Keywords:
Cc: Merged in:
Authors: David Lucas Reviewers: Travis Scrimshaw, Julien Lavauzelle
Report Upstream: N/A Work issues:
Branch: 34019fe (Commits) Commit: 34019fe7b7ebdfc0ed796b758a6404761fe20654
Dependencies: Stopgaps:

Description

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.

Change History (21)

comment:1 Changed 5 years ago by dlucas

  • Branch set to u/dlucas/thematic_tutorial

comment:2 Changed 5 years ago by dlucas

  • Commit set to 6a4c28335fa767ace816704257de054b258c09e5
  • Status changed from new to needs_info

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:

2b0adb6First version for the thematic tutorial
6a4c283Added a new chapter which contains all the code ready for copy-paste

comment:3 Changed 5 years ago by jsrn

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

comment:4 Changed 5 years ago by git

  • Commit changed from 6a4c28335fa767ace816704257de054b258c09e5 to eb5c686b289b7a8661444d54ea6767e080468ef5

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

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

comment:5 Changed 5 years ago by dlucas

  • Status changed from needs_info to needs_review

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

comment:6 Changed 5 years ago by git

  • Commit changed from eb5c686b289b7a8661444d54ea6767e080468ef5 to 4726f90b55e1a937fd51b4800c38e63f3bba76e3

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

4726f90Fixed inconsistency in names, fixed broken pointers to external methods

comment:7 Changed 5 years ago by dlucas

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

comment:8 Changed 5 years ago by git

  • Commit changed from 4726f90b55e1a937fd51b4800c38e63f3bba76e3 to 1795b117852cfb20eebeb637eba0d55b4bb4e995

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

b5631d4Update to 7.0beta2
1795b11Fixed broken tests

comment:9 Changed 5 years ago by dlucas

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

comment:10 Changed 5 years ago by tscrim

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

comment:11 Changed 5 years ago by jlavauzelle

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

comment:12 Changed 5 years ago by git

  • Commit changed from 1795b117852cfb20eebeb637eba0d55b4bb4e995 to d2a05c3e2e5d7ac540dcd6de0bacbe388074bcd9

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

f2093e1Integrated Travis' comments
48fd520Integrated Julien's comments
d2a05c3Removed all contractions

comment:13 Changed 5 years ago by dlucas

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

comment:14 Changed 5 years ago by tscrim

  • Reviewers set to 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?

comment:15 Changed 5 years ago by jlavauzelle

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Julien Lavauzelle

No more comment, it works for me.

comment:16 Changed 5 years ago by git

  • Commit changed from d2a05c3e2e5d7ac540dcd6de0bacbe388074bcd9 to 4e3c143e2f39c81da287fd768245c18e6838d09c

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

4e3c143All lines are now below 80 characters

comment:17 Changed 5 years ago by dlucas

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

comment:18 Changed 5 years ago by tscrim

  • Branch changed from u/dlucas/thematic_tutorial to u/tscrim/coding_structures_thematic_tutorial-19745
  • Commit changed from 4e3c143e2f39c81da287fd768245c18e6838d09c to 34019fe7b7ebdfc0ed796b758a6404761fe20654

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:

efcb779Merge branch 'u/dlucas/thematic_tutorial' of trac.sagemath.org:sage into u/dlucas/thematic_tutorial
34019feSome little final tweaks.

comment:19 Changed 5 years ago by dlucas

  • Status changed from needs_review to positive_review

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

comment:20 Changed 5 years ago by tscrim

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

comment:21 Changed 5 years ago by vbraun

  • Branch changed from u/tscrim/coding_structures_thematic_tutorial-19745 to 34019fe7b7ebdfc0ed796b758a6404761fe20654
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.