Opened 6 years ago
Closed 5 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, GitHub, GitLab) | Commit: | 1aa4b4e7333d96fc39836bee509fee97cfe28dfc |
Dependencies: | Stopgaps: |
Description (last modified by )
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 6 years ago by
- Branch set to u/richmond/parity_codes
comment:2 Changed 6 years ago by
- Commit set to b77de0ff1050b206b78e8b127f8dce32c0ff6c68
comment:3 Changed 6 years ago by
- 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: ↓ 5 ↓ 11 Changed 6 years ago by
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 forparity_check_code.py
. You have to addsage/coding/parity_check_code
tosage/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
overF_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 addor no base_field.is_field()
to the sanity check line 73. Indeed, for now if one passes anything but a field, the error message saysAttributeError: '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 is0
or less. I know #21326 will fix that soon, but I guess a simple check ondimension
can't hurt, right? And in any case, there should be at least something likeif 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 beG = 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 aboutParitySymbolEncoder
? Note that I am not adamant with this name change though.
encode
: I think you can do it in one line withreturn 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 ingrs.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: ↓ 6 Changed 6 years ago by
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 omitdocstring 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: ↓ 10 Changed 6 years ago by
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 omitdocstring 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: ↓ 9 Changed 6 years ago by
- 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 6 years ago by
- Commit changed from b77de0ff1050b206b78e8b127f8dce32c0ff6c68 to 0b0d2f82b033532d2084219b1ee1d6f0c63f45e0
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__
|
comment:9 in reply to: ↑ 7 Changed 6 years ago by
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 fromlinear_code.py
?David
Hi,
True! I removed this method.
Tania.
comment:10 in reply to: ↑ 6 Changed 6 years ago by
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 omitdocstring 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 rununencode_nocheck
, notunencode
.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.
comment:11 in reply to: ↑ 4 Changed 6 years ago by
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 forparity_check_code.py
. You have to addsage/coding/parity_check_code
tosage/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
overF_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 omitdocstring for
__init__
as I consider there's already some doc in the class docstring.
__init__
: I would addor no base_field.is_field()
to the sanity check line 73. Indeed, for now if one passes anything but a field, the error message saysAttributeError: '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 is0
or less. I know #21326 will fix that soon, but I guess a simple check ondimension
can't hurt, right? And in any case, there should be at least something likeif 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 beG = 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 aboutParitySymbolEncoder
? Note that I am not adamant with this name change though.
encode
: I think you can do it in one line withreturn 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 ingrs.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.
comment:12 Changed 6 years ago by
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 inlinear_code.py
. Now, this method is on the latest release, so you need to keep it. - l.9 :
m_k
instead ofm_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. Usecodes.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 inParityCheckCodeStraightforwardEncoder
.
Best,
Julien
comment:13 Changed 5 years ago by
- Branch changed from u/richmond/parity_codes to u/jlavauzelle/parity_codes
comment:14 Changed 5 years ago by
- 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:
62abcd7 | Fixed merge conflict.
|
1aa4b4e | Fixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.
|
comment:15 Changed 5 years ago by
- 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 5 years ago by
- Status changed from positive_review to needs_work
Codes should no longer print in the way the current implementation here does.
comment:17 Changed 5 years ago by
- Status changed from needs_work to positive_review
Sorry, I was being too fast. Everything is allright here.
comment:18 Changed 5 years ago by
- Branch changed from u/jlavauzelle/parity_codes to 1aa4b4e7333d96fc39836bee509fee97cfe28dfc
- Resolution set to fixed
- Status changed from positive_review to closed
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:
adds relative_distance method
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.