Classes for Reed Muller Codes

[9d23ac82-dd36-4d71-98d4-450a1836d8f4]

This ticket proposes a implementation of Reed Muller Codes. It contains: two new code classes, QAryReedMullerCode and BinaryReedMullerCode, which implements the two classes of reed muller codes two encoder classes, ReedMullerVectorEncoder and ReedMullerPolynomialEncoder which are used by both the code classes some additional functions to assist in computations related to the polynomials.

NOTE: Both the classes are implemented separately since they would have different decoders

I used the following code snippets to test them,

#for q>2
code=ReedMullerCode(3, 2, 2)
print code.dimension()
E1=ReedMullerVectorEncoder(code)
E2=ReedMullerPolynomialEncoder(code)
R=PolynomialRing(code.base_field(),code.numberOfVariable,"x")
x0=R.gen(0)
x1=R.gen(1)
c1=E1.encode(vector(GF(3),[1,1,1,1,1,1]))
print c1
c2=E2.encode(1+x0+x1+x1^2+x1*x0)
print c2
D=LinearCodeSyndromeDecoder(code)
c=D.decode_to_code(vector(GF(3),[1, 2, 0, 0, 2, 0, 1, 1, 1]))
print c
print E2.unencode_nocheck(c)
print D.decode_to_message(vector(GF(3),[1,2,1,0,0,2,1,2,2]))

The output of which was,

6
(1, 0, 1, 0, 0, 2, 1, 2, 2)
(1, 2, 0, 0, 2, 1, 1, 1, 1)
(1, 2, 0, 0, 2, 1, 1, 1, 1)
x0*x1 + x1^2 + x0 + x1 + 1
(1, 1, 1, 1, 1, 1)

#for q=2
code=ReedMullerCode(2, 2, 4)
print code.dimension()
E1=ReedMullerVectorEncoder(code)
E2=ReedMullerPolynomialEncoder(code)
R=PolynomialRing(code.base_field(),code.numberOfVariable,"x")
x0=R.gen(0)
x1=R.gen(1)
x2=R.gen(2)
x3=R.gen(3)
c1=E1.encode(vector(GF(2),[1,1,1,1,1,0,0,0,1,0,0]))
print c1
c2=E2.encode(1+x0+x1+x2+x3*x2)
print c2
D=LinearCodeSyndromeDecoder(code)
c=D.decode_to_code(vector(GF(2),[1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0]))
print c
print E2.unencode_nocheck(c)
print D.decode_to_message(vector(GF(2),[0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0]))

This gave the output as:

11
(1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0)
(1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1)
(1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1)
x2*x3 + x0 + x1 + x2 + 1
(1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0)

CC: @sagetrac-dlucas @johanrosenkilde @jlavauzelle

Component: coding theory

Author: Parthasarathi Panda

Branch: 3cce07f

Reviewer: David Lucas, Johan Sebastian Rosenkilde Nielsen

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

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:39

In '11.' is there any way to hyperlink the reference to ReedMullerCode? in the reference of QAryReedMullerCode and BinaryReedMullerCode?? Or shall i just write somehing like 'refer to documentation of' ?

You can write: :class:<backquote>BinaryReedMullerCode<backquote>, it will create an hyperlink to BinaryReedMullerCode.

If you want to refer a class in another file in coding, you can use: :class:<backquote>sage.coding.file.ClassName<backquote>

And to hyperlink a method, use :meth: instead of :class:.

If you don't want to check manually if the links work, you can use the command ./sage --docbuild --warn-links reference/coding which will rebuild the documentation and tell you if some links are broken.

[johanrosenkilde]

comment:40

Replying to @sagetrac-panda314:

Regarding '17.' Is there any way one can pass a sub ring of a multivariate polynomial ring consisting of polynomials over a subset of the variables? Like F[x_1,x_2,x_3] is to F[x_1,x_2,x_3,x_4]? The num_of_var parameter used in the function sort of does that.

Ah yes, ok that's a good point. You can make such a sub-ring but perhaps that could get inefficient. Instead, you can restructure _multivariate_polynomial_interpolation with a local function:

def _multivariate_polynomial_interpolation(evaluations, order, polynomial_ring):
    def _interpolate(evaluations, order, num_of_var):
        ...
        for k in range(d):  # computing the polynomial
            poly = poly + z * _interpolate([multipoint_evaluation_list[i][k] for i in range(n_by_q)],
                                                                 order - k, num_of_var - 1)
            z = z * x
        return poly
    return _interpolate(evaluations, order, len(polynomial_ring.gens()))

[9d23ac82-dd36-4d71-98d4-450a1836d8f4]

Changed branch from u/dlucas/classes_for_reed_muller_codes to u/panda314/classes_for_reed_muller_codes

[9d23ac82-dd36-4d71-98d4-450a1836d8f4]

Changed commit from 13cda90 to 5ec9c6c

[9d23ac82-dd36-4d71-98d4-450a1836d8f4]

comment:42

Hi, So have the changes been reviewed? Is the code fine?

---

New commits:

5ec9c6c

rewriting doumentation, and rehformatting some part of the code

[johanrosenkilde]

comment:43

So have the changes been reviewed? Is the code fine?

Please be patient :-) And for the record: when you push some commits to reply to a reviewer's concerns, please comment on your commit. At the very least, write something like "I fixed all the things you asked for. Ready for review again" or something.

I probably won't have time to go over it today. If David has time and is happy with your modifications to my comments, I'm sure that's fine.

[johanrosenkilde]

Changed reviewer from David Lucas to David Lucas, Johan S. R. Nielsen

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Changed branch from u/panda314/classes_for_reed_muller_codes to u/dlucas/classes_for_reed_muller_codes

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

Changed commit from 5ec9c6c to e3f81ec

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:45

Hello,

It seems that my comment did not appear - sorry about that.

I fixed some small doc issues, rewrote a few docstrings, and removed a duplicated WARNING block.

If you're fine with my changes, you can give a positive review, everything is fine on my side.

Once again, well done with these codes :)

David

---

New commits:

0f1f58e	Merge branch 'u/panda314/classes_for_reed_muller_codes' of git://trac.sagemath.org/sage into classes_for_reed_muller_codes
e3f81ec	Fixed errors in documentation, rewrote some sentences, changed formatting, made some extra changes according to the other reviewer's comments

[9d23ac82-dd36-4d71-98d4-450a1836d8f4]

comment:46

Replying to @sagetrac-dlucas: tests are running fine. Seems cool :)

Hello,

It seems that my comment did not appear - sorry about that.

I fixed some small doc issues, rewrote a few docstrings, and removed a duplicated WARNING block.

If you're fine with my changes, you can give a positive review, everything is fine on my side.

Once again, well done with these codes :)

David

---

New commits:

0f1f58e	Merge branch 'u/panda314/classes_for_reed_muller_codes' of git://trac.sagemath.org/sage into classes_for_reed_muller_codes
e3f81ec	Fixed errors in documentation, rewrote some sentences, changed formatting, made some extra changes according to the other reviewer's comments

[johanrosenkilde]

comment:47

Then set it to positive_review as David coefficient said.

[vbraun]

comment:49

Merge conflict, please merge in next beta.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3cce07f

Updated to latest beta and fixed conflicts

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e3f81ec to 3cce07f

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:51

Merge conflict, please merge in next beta.

Done, ticket open for review.

David

[9d23ac82-dd36-4d71-98d4-450a1836d8f4]

comment:52

Replying to @sagetrac-dlucas:

Merge conflict, please merge in next beta.

Seems fine. Tests passed.

Done, ticket open for review.

David

[1861b8a9-77f0-4f35-8431-8514a75b40d1]

comment:53

Seems fine. Tests passed.

Cool!

Can you please set it to positive_review then?

[vbraun]

Changed branch from u/dlucas/classes_for_reed_muller_codes to 3cce07f

[jdemeyer]

Changed commit from 3cce07f to none

[jdemeyer]

Changed reviewer from David Lucas, Johan S. R. Nielsen to David Lucas, Johan Sebastian Rosenkilde Nielsen