Opened 2 years ago

Closed 2 years ago

#21328 closed enhancement (fixed)

Create a new class for Parity-Check Codes

Reported by: richmond Owned by:
Priority: major Milestone: sage-7.6
Component: coding theory Keywords: linear code, sd75, rd3
Cc: dlucas, nthiery Merged in:
Authors: Tania Richmond Reviewers: David Lucas, Julien Lavauzelle
Report Upstream: N/A Work issues:
Branch: 1aa4b4e (Commits) Commit: 1aa4b4e7333d96fc39836bee509fee97cfe28dfc
Dependencies: Stopgaps:

Description (last modified by richmond)

A linear parity-check code of length n and dimension k over GF(q), with n = k+1 is the set of all words, formed by the checksum at the last position of all k first symbols modulo q.

This ticket proposes a new class for parity-check codes along with an encoder for it.

Change History (18)

comment:1 Changed 2 years ago by richmond

  • Branch set to u/richmond/parity_codes

comment:2 Changed 2 years ago by richmond

  • Commit set to b77de0ff1050b206b78e8b127f8dce32c0ff6c68

Hello,

I implemented a new class for parity-check codes over GF(q), with generator matrix (identity matrix concatenated with a ones column) and straightforward (minus sum of message symbols added at the end of the message) encoder classes. I also implemented a method for minimum distance.

Setting to needs-review.

Tania.


New commits:

52b8b8aadds relative_distance method
b77de0fAdded new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.

comment:3 Changed 2 years ago by richmond

  • Authors set to Tania Richmond
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from Create a new class for Parity Codes to Create a new class for Parity-Check Codes

comment:4 follow-ups: Changed 2 years ago by dlucas

Hi Tania,

Some remarks on your work:

  • You forgot to add your module (Python file) to the index of documented modules for sage/coding, which means no html/pdf documentation file will be generated for parity_check_code.py. You have to add sage/coding/parity_check_code to sage/doc/en/reference/coding/index.rst.
  • Once done, you'll notice building the documentation fails because there's already a reference named [W] in /sage/schemes/hyperelliptic_curves/invariants.py. So, you have to rename your [W] to something else ([W88]?)
  • I would add a small definition of a parity-check code in the module docstring (where you wrote "A simple way of detecting [...] even."). What about:

" A parity-check code of dimension k over F_q is the set:

\{(m_1, \dots, m_k, -\Sigma_{i=1}^{k}) m_i \mid (m_1, \dots, m_n) \in F_q\}"?

ParityCheckCode

  • __init__: I think you forgot to remove the docstring. Here it does not make a lot of sense to write "An abstract linear code object should never be created.". I usually omit

docstring for __init__ as I consider there's already some doc in the class docstring.

  • __init__: I would add or no base_field.is_field() to the sanity check line 73. Indeed, for now if one passes anything but a field, the error message says AttributeError: 'anything' object has no attribute 'is_finite' which is not the most informative error message. BTW, it's also possible to create a Parity-Check code whose dimension is 0 or less. I know #21326 will fix that soon, but I guess a simple check on dimension can't hurt, right? And in any case, there should be at least something like if not isinstance(dimension, (int, Integer) raise ValueError("dimension has to be a Python int or a Sage Integer"). Otherwise, if the user passes anything but an int/Integer, it will fail with some weird error.

ParityCheckGeneratorMatrixEncoder

  • Doctest lines 179-183 calls the straightforward encoder instead of the generator matrix encoder.
sage: C  = codes.RandomLinearCode(10, 4, GF(11))
sage: codes.encoders.ParityCheckCodeGeneratorMatrixEncoder(C)

works while it should fail.

  • generator_matrix: I'm quite sure l.246 should be G = G.augment(vector([field.order()] * k)). Because for now, the encoding does not work:
   sage: C = codes.ParityCheckCode(GF(5),7)
   sage: E = codes.encoders.ParityCheckCodeGeneratorMatrixEncoder(C)
   sage: m = vector(GF(5), [1, 0, 4, 2, 0, 3, 2])
   sage: sum(E.encode(m))
   4 #should be 0

ParityCheckCodeStraightForwardEncoder

  • I know we already talked about it, but I still think StraightforwardEncoder is not the most straightforward name... What about ParitySymbolEncoder? Note that I am not adamant with this name change though.
  • encode: I think you can do it in one line with return vector(self.code().base_field(), message.list()+[-sum(message)])

Encoders

  • Last one: lines 404/405, you chose "ParityCheckGeneratorMatrixEncoder" and "ParityCheckStraightforwardEncoder" for the encoders string names. I'd choose "GeneratorMatrix" and "Straightforward" instead, as the user has to type those names when they use `C.encoder('str_name'). See the names I chose in grs.py for instance.

Apart from those small remarks, it looks good. Great job for your first code class :)

David

comment:5 in reply to: ↑ 4 ; follow-up: Changed 2 years ago by nthiery

Replying to dlucas:

  • __init__: I think you forgot to remove the docstring. Here it does not make a lot of sense to write "An abstract linear code object should never be created.". I usually omit

docstring for __init__ as I consider there's already some doc in the class docstring.

Just to clarify: __init__ methods, like all other methods, should have a docstring. But it can be made into a bare minimal, with a single doctest constructing an object and running generic tests on it; typically:

def init(self, ...):

""" Initialize this parity code

TESTS

sage: C = ParityCode?(...) sage: TestSuite?(C).run()

"""

Great job for your first code class :)

+1!

Cheers,

Nicolas

comment:6 in reply to: ↑ 5 ; follow-up: Changed 2 years ago by dlucas

Replying to nthiery:

Replying to dlucas:

  • __init__: I think you forgot to remove the docstring. Here it does not make a lot of sense to write "An abstract linear code object should never be created.". I usually omit

docstring for __init__ as I consider there's already some doc in the class docstring.

Just to clarify: __init__ methods, like all other methods, should have a docstring. But it can be made into a bare minimal, with a single doctest constructing an object and running generic tests on it; typically:

def init(self, ...):

""" Initialize this parity code

TESTS

sage: C = ParityCode?(...) sage: TestSuite?(C).run()

"""

Oops. Well, I guess I should open a ticket to fix my __init__ then, because all my classes look like:

class ClassName:
    r"""
    Short description

    Long description

    EXAMPLES::
    
        ....
    """

    def __init__(self, ...):
    r"""
    TESTS::

        ....
    """

BTW, doctest line 383 in parity_check_code.py should run unencode_nocheck, not unencode. sage --coverage complains about this... But not about missing docstrings in my __init__ blocks.

David

comment:7 follow-up: Changed 2 years ago by dlucas

  • Reviewers set to David Lucas

Hi,

I just noticed something: according to the diff, you also implement relative_distance in this ticket. I'm quite sure it's because you were working on #21315 at the same time. Could you please remove the related lines from linear_code.py?

David

comment:8 Changed 2 years ago by git

  • Commit changed from b77de0ff1050b206b78e8b127f8dce32c0ff6c68 to 0b0d2f82b033532d2084219b1ee1d6f0c63f45e0

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

0b0d2f8Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__

comment:9 in reply to: ↑ 7 Changed 2 years ago by richmond

Replying to dlucas:

Hi,

I just noticed something: according to the diff, you also implement relative_distance in this ticket. I'm quite sure it's because you were working on #21315 at the same time. Could you please remove the related lines from linear_code.py?

David

Hi,

True! I removed this method.

Tania.

comment:10 in reply to: ↑ 6 Changed 2 years ago by richmond

Replying to dlucas:

Replying to nthiery:

Replying to dlucas:

  • __init__: I think you forgot to remove the docstring. Here it does not make a lot of sense to write "An abstract linear code object should never be created.". I usually omit

docstring for __init__ as I consider there's already some doc in the class docstring.

Just to clarify: __init__ methods, like all other methods, should have a docstring. But it can be made into a bare minimal, with a single doctest constructing an object and running generic tests on it; typically:

def init(self, ...):

""" Initialize this parity code

TESTS

sage: C = ParityCode?(...) sage: TestSuite?(C).run()

"""

Oops. Well, I guess I should open a ticket to fix my __init__ then, because all my classes look like:

class ClassName:
    r"""
    Short description

    Long description

    EXAMPLES::
    
        ....
    """

    def __init__(self, ...):
    r"""
    TESTS::

        ....
    """

BTW, doctest line 383 in parity_check_code.py should run unencode_nocheck, not unencode. sage --coverage complains about this... But not about missing docstrings in my __init__ blocks.

David

Hi,

I changed unencode by unencode_nocheck, but it gives me an error in tests. I do not understand exactly where does it come from, so if you can take a look on it please...

For description and test, I just followed the toturial: http://doc.sagemath.org/html/en/thematic_tutorials/structures_in_coding_theory.html I also took inspiration from others classes in coding theory (like Hamming code or GRS code). I hope it is correct like that.

Tania.

Last edited 2 years ago by richmond (previous) (diff)

comment:11 in reply to: ↑ 4 Changed 2 years ago by richmond

Replying to dlucas:

Hi Tania,

Some remarks on your work:

  • You forgot to add your module (Python file) to the index of documented modules for sage/coding, which means no html/pdf documentation file will be generated for parity_check_code.py. You have to add sage/coding/parity_check_code to sage/doc/en/reference/coding/index.rst.
  • Once done, you'll notice building the documentation fails because there's already a reference named [W] in /sage/schemes/hyperelliptic_curves/invariants.py. So, you have to rename your [W] to something else ([W88]?)
  • I would add a small definition of a parity-check code in the module docstring (where you wrote "A simple way of detecting [...] even."). What about:

" A parity-check code of dimension k over F_q is the set:

\{(m_1, \dots, m_k, -\Sigma_{i=1}^{k}) m_i \mid (m_1, \dots, m_n) \in F_q\}"?

ParityCheckCode

  • __init__: I think you forgot to remove the docstring. Here it does not make a lot of sense to write "An abstract linear code object should never be created.". I usually omit

docstring for __init__ as I consider there's already some doc in the class docstring.

  • __init__: I would add or no base_field.is_field() to the sanity check line 73. Indeed, for now if one passes anything but a field, the error message says AttributeError: 'anything' object has no attribute 'is_finite' which is not the most informative error message. BTW, it's also possible to create a Parity-Check code whose dimension is 0 or less. I know #21326 will fix that soon, but I guess a simple check on dimension can't hurt, right? And in any case, there should be at least something like if not isinstance(dimension, (int, Integer) raise ValueError("dimension has to be a Python int or a Sage Integer"). Otherwise, if the user passes anything but an int/Integer, it will fail with some weird error.

ParityCheckGeneratorMatrixEncoder

  • Doctest lines 179-183 calls the straightforward encoder instead of the generator matrix encoder.
sage: C  = codes.RandomLinearCode(10, 4, GF(11))
sage: codes.encoders.ParityCheckCodeGeneratorMatrixEncoder(C)

works while it should fail.

  • generator_matrix: I'm quite sure l.246 should be G = G.augment(vector([field.order()] * k)). Because for now, the encoding does not work:
   sage: C = codes.ParityCheckCode(GF(5),7)
   sage: E = codes.encoders.ParityCheckCodeGeneratorMatrixEncoder(C)
   sage: m = vector(GF(5), [1, 0, 4, 2, 0, 3, 2])
   sage: sum(E.encode(m))
   4 #should be 0

ParityCheckCodeStraightForwardEncoder

  • I know we already talked about it, but I still think StraightforwardEncoder is not the most straightforward name... What about ParitySymbolEncoder? Note that I am not adamant with this name change though.
  • encode: I think you can do it in one line with return vector(self.code().base_field(), message.list()+[-sum(message)])

Encoders

  • Last one: lines 404/405, you chose "ParityCheckGeneratorMatrixEncoder" and "ParityCheckStraightforwardEncoder" for the encoders string names. I'd choose "GeneratorMatrix" and "Straightforward" instead, as the user has to type those names when they use `C.encoder('str_name'). See the names I chose in grs.py for instance.

Apart from those small remarks, it looks good. Great job for your first code class :)

David

Hi,

Thank you for this long but useful comment. I made changes you asked except in ParityCheckGeneratorMatrixEncoder. Indeed, if we suppose that a word is a codeword only when the sum of all its coodinates, then G = G.augment(vector(field,[- field.one()] * k)). It was my mistake because I use to work with binary codes so there is no -.

Tania.

Last edited 2 years ago by richmond (previous) (diff)

comment:12 Changed 2 years ago by jlavauzelle

Hi Tania,

A first general comment. When you push a new version of your code, you must take care if a new release has been done. For instance, your code is written under release 7.4.beta1, but we're now under 7.4.beta5. So you need to merge your version with the latest beta. New releases are announced here: https://groups.google.com/forum/#!forum/sage-release

Now about your code, a few more comments:

  • Your push seems to remove relative_distance() method in linear_code.py. Now, this method is on the latest release, so you need to keep it.
  • l.9 : m_k instead of m_n
  • In ParityCheckCodeGeneratorMatrixEncoder, the constructor won't raise any error as it is claimed in the doctest. Generically, you can run sage tests (./sage -t --long src/sage/coding/parity_check_code.py) to see if your doctests are well written.
  • Then you'll also see that codes.RandomLinearCode(n, k, F) is deprecated. Use codes.random_linear_code(F, n, k)instead.
  • l.199 to 210 : it seems that you only copy paste the _latex_ function of the code, whithout replacing the code by the encoder.
  • This is the same for the _repr_ method (only the doctest).
  • The two previous remarks also hold for ParityCheckCodeStraightforwardEncoder (lines 297 to 320).
  • You need a unencode_nocheck() method in ParityCheckCodeStraightforwardEncoder.

Best,

Julien

comment:13 Changed 2 years ago by jlavauzelle

  • Branch changed from u/richmond/parity_codes to u/jlavauzelle/parity_codes

comment:14 Changed 2 years ago by jlavauzelle

  • Commit changed from 0b0d2f82b033532d2084219b1ee1d6f0c63f45e0 to 1aa4b4e7333d96fc39836bee509fee97cfe28dfc
  • Milestone changed from sage-7.4 to sage-7.6
  • Reviewers changed from David Lucas to David Lucas, Julien Lavauzelle

Hi,

I fixed what I proposed and solved the merge conflict. Maybe it still need a quick review because I did many (minor) changes.

Julien


New commits:

62abcd7Fixed merge conflict.
1aa4b4eFixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.

comment:15 Changed 2 years ago by dlucas

  • Keywords rd3 added
  • Status changed from needs_review to positive_review

Hello,

Tests pass, doc compiles, I agree with your changes, giving the green light.

David

comment:16 Changed 2 years ago by jsrn

  • Status changed from positive_review to needs_work

Codes should no longer print in the way the current implementation here does.

comment:17 Changed 2 years ago by jsrn

  • Status changed from needs_work to positive_review

Sorry, I was being too fast. Everything is allright here.

comment:18 Changed 2 years ago by vbraun

  • Branch changed from u/jlavauzelle/parity_codes to 1aa4b4e7333d96fc39836bee509fee97cfe28dfc
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.