Opened 4 years ago

Closed 3 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) Commit: 0cd4c3d358656fdde46881d8e975d74d9e0fc5cd
Dependencies: #19930, #19653, #20284 Stopgaps:

Description

This ticket proposes an implementation of subfield subcodes.

Change History (22)

comment:1 Changed 4 years ago by dlucas

  • Branch set to u/dlucas/subfield_subcode

comment:2 Changed 4 years ago by git

  • Commit set to 6e1531d103dd2da2a3e0b77ade32b017a7d366bf

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

6e1531dUpdated to 7.1beta2 and fixed conflict

comment:3 Changed 4 years ago by dlucas

  • Authors set to David Lucas

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) and Fq^m, gives a representation of elements of Fq^m as vectors of Fp over a basis of Fq.
  • 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...
Last edited 4 years ago by dlucas (previous) (diff)

comment:4 Changed 4 years ago by dlucas

  • Dependencies set to #19930

comment:5 Changed 4 years ago by git

  • Commit changed from 6e1531d103dd2da2a3e0b77ade32b017a7d366bf to 296be1ed0e321e5df6f257e61fbdb1bdc1877ebf

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

296be1eUpdated to 7.1beta3 and fixed merge conflict

comment:6 Changed 4 years ago by git

  • Commit changed from 296be1ed0e321e5df6f257e61fbdb1bdc1877ebf to 9c5405ffb4101a832e060711e76c15fbacb03b47

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

ffed948Merge branch 'u/dlucas/grs_decoders' of git://trac.sagemath.org/sage into grs_decoders
616219cUpdate to latest beta
77f0629Merged #19897
37bb7acUpdated introductory thematic tutorial with a paragraph on decoders and message spaces
1220403Merge branch 'develop' into grs_decoders
4340598Removed deprecated import
b840682Updated to 7.1beta3 and fixed conflict
d70d6aaRemoved __ne__ methods
1808bb1Some fixes to the decoder. Merged with GRS decoders branch to have fast examples
9c5405fFixed a bug because of which it was impossible to build a PC matrix when the subfield was the prime field

comment:7 Changed 4 years ago by dlucas

  • 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

Last edited 4 years ago by dlucas (previous) (diff)

comment:8 Changed 4 years ago by git

  • Commit changed from 9c5405ffb4101a832e060711e76c15fbacb03b47 to 3b172ad13fd4782b80049897fa046254cecaf01c

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

fca099eAdded new sanity check on the output of BW and Gao decoder
57dbfbfRewrote random_element method
7953d60Proper sanity checks for output of decode_to_* methods
8673ac5Optimized a bit polynomial division in Gao and BW
e1b6b09Merged now postive reviewed #19666 and fixed conflicts
5093dceUpdate to 7.1beta5
f3b4b11Fixed typo in Guruswami-Sudan doc
d01d4ddMerge branch 'grs_decoders' into subfield_subcode
b1941afAdded extra arguments management to decoding_radius
3b172adDecoder now works if the original decoder is a list decoder

comment:9 Changed 4 years ago by dlucas

I made a few fixes:

  • decoding_radius now properly handles extra arguments. This is useful if the original decoder is GRSErrorErasureDecoder, 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 3 years ago by dimpase

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 3 years ago by dlucas

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 3 years ago by jpflori

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 3 years ago by dlucas

Hello,

I opened a new ticket for my field embeddings class. See it in #20284.

Best,

David

comment:14 Changed 3 years ago by dlucas

  • Dependencies changed from #19930, #19653 to #19930, #19653, #20284
  • Milestone changed from sage-7.1 to sage-7.2

comment:15 Changed 3 years ago by jlavauzelle

  • Branch changed from u/dlucas/subfield_subcode to u/jlavauzelle/subfield_subcode

comment:16 Changed 3 years ago by jlavauzelle

  • 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:

de9a59dMerge branch 'develop' and fix conflicts.
cda5303Updated to 7.3.beta5 and fixed conflict.
7fa76abUpdate to latest beta.
6997b3aReplaced field_embedding.py by relative_finite_field_extension.py.
8bcf728Fixed doctests.
2f87d14Fixed doc typos.
Last edited 3 years ago by jlavauzelle (previous) (diff)

comment:17 Changed 3 years ago by git

  • Commit changed from 2f87d14f22cc6affe4aedd023898383e50549d26 to b4ae212952d859f3e7e01832d4b4010137527821

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

7bbf965Used the new *_degree() function from relative_finite_field_extension.py. Fixed the list decoder.
23e184bUpdated to 7.3.beta8 and fixed conflicts.
08f75f0Added subfield subcode classes into catalogs.
1264e75Fixed cast_into_relative_field() and put check=True as default value.
73dd54eThe decoder now raise a DecodingError when the output des not lie into the subfield subcode.
4cf956eFixed __eq__().
b4ae212Add an __eq__() method.

comment:18 Changed 3 years ago by jlavauzelle

  • 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 and C2 of the same code, with the same subfield but with different embeddings, then C1 == 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 from relative_finite_field_embedding.py and added an __eq__() method.

If you agree with my changes, put it on positive review.

Julien

comment:19 Changed 3 years ago by dlucas

  • Branch changed from u/jlavauzelle/subfield_subcode to u/dlucas/subfield_subcode

comment:20 Changed 3 years ago by dlucas

  • 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:

0cd4c3dRemoved generic decoders from registration block in subfield_subcode.py

comment:21 Changed 3 years ago by jlavauzelle

  • 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 3 years ago by vbraun

  • Branch changed from u/dlucas/subfield_subcode to 0cd4c3d358656fdde46881d8e975d74d9e0fc5cd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.