Create a new class for Parity-Check Codes

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

[richmond]

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:

​52b8b8a	adds relative_distance method
​b77de0f	Added new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.

[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

[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

[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

[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

[git]

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

​0b0d2f8

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

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

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

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

[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

[jlavauzelle]

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:

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

[dlucas]

Hello,

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

David

[jsrn]

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

[jsrn]

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