Opened 6 years ago
Closed 6 years ago
#20039 closed enhancement (fixed)
Subfield subcodes
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.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 6 years ago by
 Branch set to u/dlucas/subfield_subcode
comment:2 Changed 6 years ago by
 Commit set to 6e1531d103dd2da2a3e0b77ade32b017a7d366bf
comment:3 Changed 6 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 6 years ago by
 Dependencies set to #19930
comment:5 Changed 6 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 GuruswamiSudan 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 sage7.1 to sage7.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 sage7.2 to sage7.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 nonsubfield 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