Subfield subcodes

[sagetrac-dlucas]

This ticket proposes an implementation of subfield subcodes.

Depends on #19930
Depends on #19653
Depends on #20284

Component: coding theory

Author: David Lucas

Branch/Commit: 0cd4c3d

Reviewer: Julien Lavauzelle

Issue created by migration from https://trac.sagemath.org/ticket/20039

[sagetrac-dlucas]

Branch: u/dlucas/subfield_subcode

[sagetrac-git]

Commit: 6e1531d

[sagetrac-git]

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

6e1531d

Updated to 7.1beta2 and fixed conflict

[sagetrac-dlucas]

comment:3

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

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

Dependencies: #19930

[sagetrac-git]

Changed commit from 6e1531d to 296be1e

[sagetrac-git]

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

296be1e

Updated to 7.1beta3 and fixed merge conflict

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 296be1e to 9c5405f

[sagetrac-dlucas]

comment:7

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

[sagetrac-dlucas]

Changed dependencies from #19930 to #19930, #19653

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 9c5405f to 3b172ad

[sagetrac-dlucas]

comment:9

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

[dimpase]

comment:10

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?

[sagetrac-dlucas]

comment:11

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

[jpflori]

comment:12

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

[sagetrac-dlucas]

comment:13

Hello,

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

Best,

David

[sagetrac-dlucas]

Changed dependencies from #19930, #19653 to #19930, #19653, #20284

[jlavauzelle]

Changed branch from u/dlucas/subfield_subcode to u/jlavauzelle/subfield_subcode

[jlavauzelle]

comment:16

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.

[jlavauzelle]

Changed commit from 3b172ad to 2f87d14

[sagetrac-git]

Changed commit from 2f87d14 to b4ae212

[sagetrac-git]

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.

[jlavauzelle]

comment:18

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

[jlavauzelle]

Reviewer: Julien Lavauzelle

[sagetrac-dlucas]

Changed branch from u/jlavauzelle/subfield_subcode to u/dlucas/subfield_subcode

[sagetrac-dlucas]

Changed commit from b4ae212 to 0cd4c3d

[sagetrac-dlucas]

comment:20

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

[jlavauzelle]

comment:21

Hi,

Alright, I didn't know there was such a automatic registration. Great :)

Positive review then.

Julien

[vbraun]

Changed branch from u/dlucas/subfield_subcode to 0cd4c3d