Opened 7 years ago
Closed 6 years ago
#20039 closed enhancement (fixed)
Subfield subcodes
Reported by: | dlucas | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.3 |
Component: | coding theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | David Lucas | Reviewers: | Julien Lavauzelle |
Report Upstream: | N/A | Work issues: | |
Branch: | 0cd4c3d (Commits, GitHub, GitLab) | Commit: | 0cd4c3d358656fdde46881d8e975d74d9e0fc5cd |
Dependencies: | #19930, #19653, #20284 | Stopgaps: |
Description
This ticket proposes an implementation of subfield subcodes.
Change History (22)
comment:1 Changed 7 years ago by
- Branch set to u/dlucas/subfield_subcode
comment:2 Changed 7 years ago by
- Commit set to 6e1531d103dd2da2a3e0b77ade32b017a7d366bf
comment:3 Changed 7 years ago by
This is still a WIP I push here as there's some work done which might be of any interest.
In my branch, one will find:
- a class dedicated to field embeddings which, considering
Fp
a finite field (p
prime),Fq
(q=p^s
) andFq^m
, gives a representation of elements ofFq^m
as vectors ofFp
over a basis ofFq
.
- an implementation of subfield subcodes
Known issues
- Some names are quite bad and need to be reconsidered
- Subfield subcode's parity check matrix computation has not been thoroughly tested
- A decoder for subfield subcodes is not yet implemented
- Some interesting methods could be implemented (e.g. dual code of a subfield subcode)
dimension_lower_bound
seems quite useless...
comment:4 Changed 7 years ago by
- Dependencies set to #19930
comment:5 Changed 7 years ago by
- Commit changed from 6e1531d103dd2da2a3e0b77ade32b017a7d366bf to 296be1ed0e321e5df6f257e61fbdb1bdc1877ebf
Branch pushed to git repo; I updated commit sha1. New commits:
296be1e | Updated to 7.1beta3 and fixed merge conflict
|
comment:6 Changed 6 years ago by
- Commit changed from 296be1ed0e321e5df6f257e61fbdb1bdc1877ebf to 9c5405ffb4101a832e060711e76c15fbacb03b47
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
ffed948 | Merge branch 'u/dlucas/grs_decoders' of git://trac.sagemath.org/sage into grs_decoders
|
616219c | Update to latest beta
|
77f0629 | Merged #19897
|
37bb7ac | Updated introductory thematic tutorial with a paragraph on decoders and message spaces
|
1220403 | Merge branch 'develop' into grs_decoders
|
4340598 | Removed deprecated import
|
b840682 | Updated to 7.1beta3 and fixed conflict
|
d70d6aa | Removed __ne__ methods
|
1808bb1 | Some fixes to the decoder. Merged with GRS decoders branch to have fast examples
|
9c5405f | Fixed a bug because of which it was impossible to build a PC matrix when the subfield was the prime field
|
comment:7 Changed 6 years ago by
- Dependencies changed from #19930 to #19930, #19653
- Status changed from new to needs_review
I implemented a decoder for subfield subcodes, rewrote some documentation and fixed the bugs I found.
I decided to drop the implementation of a specific dual_code
method as it seems to quite difficult, and thus will be done in another ticket.
This ticket now depends on #19653, as I need better decoders than syndrome
and nearest_neighbor
to perform (fast) tests over the decoder implemented here.
This is now open for review.
David
comment:8 Changed 6 years ago by
- Commit changed from 9c5405ffb4101a832e060711e76c15fbacb03b47 to 3b172ad13fd4782b80049897fa046254cecaf01c
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
fca099e | Added new sanity check on the output of BW and Gao decoder
|
57dbfbf | Rewrote random_element method
|
7953d60 | Proper sanity checks for output of decode_to_* methods
|
8673ac5 | Optimized a bit polynomial division in Gao and BW
|
e1b6b09 | Merged now postive reviewed #19666 and fixed conflicts
|
5093dce | Update to 7.1beta5
|
f3b4b11 | Fixed typo in Guruswami-Sudan doc
|
d01d4dd | Merge branch 'grs_decoders' into subfield_subcode
|
b1941af | Added extra arguments management to decoding_radius
|
3b172ad | Decoder now works if the original decoder is a list decoder
|
comment:9 Changed 6 years ago by
I made a few fixes:
decoding_radius
now properly handles extra arguments. This is useful if the original decoder isGRSErrorErasureDecoder
, for instance.- The decoder now succeeds (and returns a list) when it should with an original decoder which is a list decoder.
This is still open for review.
David
comment:10 Changed 6 years ago by
after a very quick look I noticed that you swapped the order of parameters for HammingCode
. This means you would need to deprecate the existing order, etc etc.
Are you really willing to do so?
comment:11 Changed 6 years ago by
Hello,
I did that for consistency with the new code classes I'm designing, in which the base field of the code is the first argument. I'd prefer to do so, as I like when all the classes of a library have the same calling conventions (if possible, of course).
And in that case, it was actually done in #19930... Which is now closed. I deprecated the old convention, of course.
I hope it's not a problem...
Best,
David
comment:12 Changed 6 years ago by
Hi David,
Please split the two items you mention into two different tickets if possible. That is if you really have a nice and general class for finite fields embeddings, please give it its own ticket. Its use will definitely go much further than subfields codes! And hopefully I might have time to review it first.
Best, JP
comment:13 Changed 6 years ago by
comment:14 Changed 6 years ago by
- Dependencies changed from #19930, #19653 to #19930, #19653, #20284
- Milestone changed from sage-7.1 to sage-7.2
comment:15 Changed 6 years ago by
- Branch changed from u/dlucas/subfield_subcode to u/jlavauzelle/subfield_subcode
comment:16 Changed 6 years ago by
- Commit changed from 3b172ad13fd4782b80049897fa046254cecaf01c to 2f87d14f22cc6affe4aedd023898383e50549d26
Hi,
I merged it with the latest beta, and made it work with the new relative_finite_field_extension.py
file. I also removed some piece of code in the list decoder, which didn't return subfield codewords. Thus it remains to fix this and to do the review.
Still needs review then.
Best,
Julien
New commits:
de9a59d | Merge branch 'develop' and fix conflicts.
|
cda5303 | Updated to 7.3.beta5 and fixed conflict.
|
7fa76ab | Update to latest beta.
|
6997b3a | Replaced field_embedding.py by relative_finite_field_extension.py.
|
8bcf728 | Fixed doctests.
|
2f87d14 | Fixed doc typos.
|
comment:17 Changed 6 years ago by
- Commit changed from 2f87d14f22cc6affe4aedd023898383e50549d26 to b4ae212952d859f3e7e01832d4b4010137527821
Branch pushed to git repo; I updated commit sha1. New commits:
7bbf965 | Used the new *_degree() function from relative_finite_field_extension.py. Fixed the list decoder.
|
23e184b | Updated to 7.3.beta8 and fixed conflicts.
|
08f75f0 | Added subfield subcode classes into catalogs.
|
1264e75 | Fixed cast_into_relative_field() and put check=True as default value.
|
73dd54e | The decoder now raise a DecodingError when the output des not lie into the subfield subcode.
|
4cf956e | Fixed __eq__().
|
b4ae212 | Add an __eq__() method.
|
comment:18 Changed 6 years ago by
- Milestone changed from sage-7.2 to sage-7.3
- Reviewers set to Julien Lavauzelle
Hi David,
First, I merged with the latest beta.
I also reviewed your code. Nice piece of code, again. A few remarks:
- I added the classes into the catalogs.
- That's a great feature that you let the user choose the field embedding. But it has consequences. Especially, if you consider two subfield subcodes
C1
andC2
of the same code, with the same subfield but with different embeddings, thenC1 == C2
does not generally hold (they are only isomorphic). So your equality test__eq__
should check the embedding also. See the code below:q = 4 ; Q = q**3 ; k = 8 Fq = GF(q) ; FQ = GF(Q) pts = FQ.list()[:Q//5] C = codes.GeneralizedReedSolomonCode(pts, k) H = Hom(Fq, FQ) SubC1 = codes.SubfieldSubcode(C, Fq, embedding=H[0]) SubC2 = codes.SubfieldSubcode(C, Fq, embedding=H[1]) for c in SubC1: print c in SubC2
I my commits, I proposed to check the embedding instead of the field order (well, in fact, the field will be checked via the embedding).
- I made the decoder raise a
DecodingError
when trying to output a non-subfield word.
- I also modified
cast_into_relative_field()
method fromrelative_finite_field_embedding.py
and added an__eq__()
method.
If you agree with my changes, put it on positive review.
Julien
comment:19 Changed 6 years ago by
- Branch changed from u/jlavauzelle/subfield_subcode to u/dlucas/subfield_subcode
comment:20 Changed 6 years ago by
- Commit changed from b4ae212952d859f3e7e01832d4b4010137527821 to 0cd4c3d358656fdde46881d8e975d74d9e0fc5cd
Hello,
I agree with your changes, thanks for your work!
I made a tiny tweak: since #20840, it's no longer necessary to register manually
generic decoders in every single file, AbstractLinearCode
's constructor now does it.
Thus, I removed the lines related to registration of syndrome and nearest neighbour decoders
in SubfieldSubcode
's list of known decoders.
If this is fine with you, you can set it to positive_review
!
Best,
David
New commits:
0cd4c3d | Removed generic decoders from registration block in subfield_subcode.py
|
comment:21 Changed 6 years ago by
- Status changed from needs_review to positive_review
Hi,
Alright, I didn't know there was such a automatic registration. Great :)
Positive review then.
Julien
comment:22 Changed 6 years ago by
- Branch changed from u/dlucas/subfield_subcode to 0cd4c3d358656fdde46881d8e975d74d9e0fc5cd
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Updated to 7.1beta2 and fixed conflict