Classes for Reed Muller Codes

[sagetrac-panda314]

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

[sagetrac-panda314]

Branch: u/panda314/classes_for_reed_muller_codes

[sagetrac-panda314]

Replying to @sagetrac-panda314:

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

---

New commits:

0ffd780	adding ReedMullerCode.py containing support for encoding of Reed Muller Codes
9fb9b69	Merge branch 'RMCode' into t/20705/classes_for_reed_muller_codes

[sagetrac-panda314]

Commit: 9fb9b69

[sagetrac-git]

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

ba4de76

adding documentation

[sagetrac-git]

Changed commit from 9fb9b69 to ba4de76

[sagetrac-git]

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

262e320

adding documentation for additional functions

[sagetrac-git]

Changed commit from ba4de76 to 262e320

[sagetrac-git]

Changed commit from 262e320 to c5af6d2

[sagetrac-git]

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

3fc4924	minor edits
c5af6d2	Some adjustments to way functions take their inputs and adding the option of giving your own polynomial ring to ReedMullerPolynomialEncoder

[sagetrac-git]

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

ca93a4b

removing ReedMullerCode() of guava.py from the implementation

[sagetrac-git]

Changed commit from c5af6d2 to ca93a4b

[sagetrac-git]

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

23ff289

debugged and ran the doctests

[sagetrac-git]

Changed commit from ca93a4b to 23ff289

[sagetrac-dlucas]

comment:9

Hello,

I started reading your code.
Before giving actual comments on the code itself, here are some general comments:

• there is certain conventions to respect while writing Python code. You can find a summary of these conventions here.

• lines are supposed to be less than 80 characters long. As I think it's an old rule, I'm completely ok if some lines are around 100 characters, especially in the doctests block which might be hard to break. However, some lines in your code are just too long: e.g. l. 58 is 161 characters long, l.92 is 144 characters long...). A general tip: in Python, as long as you are in the same parenthesis block, you can jump to the next line without any special character. For instance, this:

poly=poly+z*multivariatePolynomialInterpolation([evaluation2[i][k] for i in range(nq)], numberOfVariable-1, order-k, q, finiteField, _R)

can be written like this:

poly=poly+z*multivariatePolynomialInterpolation([evaluation2[i][k] for i in range(nq)],
        numberOfVariable-1, order-k, q, finiteField, _R)

• on names: in python, methods and variables names are written like this function_name and variable_name (and not functionName and variableName). Module names should follow the same convention (reed_muller_code.py instead of ReedMullerCode.py).

• You wrote the documentation for a few methods like this:

r"""
DOC
"""
def my_func:
    code

but it should always be like this:

def my_func:
    r"""
    DOC
    """
    code

• More of the same, this DOC block should always be formatted like this:

def my_func(i1, i2):
    r"""
    Short description of my_func return value 
    (Should be something like "Returns ....")

    [optional] more details

    INPUT:

    - ``i1`` -- description of i1

    - ``i2`` -- description of i2

    [optional] OUTPUT

    EXAMPLES::

        sage: ...

    [optional] TESTS::

        sage: ...

• you should always put one whitespace before and after operators (exception: precedence), e.g:

  • a = b + c
  • a = (b+c) * (b-c)

• you used full names for variables everywhere but for _R. I think it would be better to rename it polynomial_ring or something like that.

I'll run tests this afternoon and probably come back with more comments on the code itself.
Don't worry about all my comments in formatting, it's your first big ticket for Sage, so it's perfectly normal to use wrong coding conventions. It takes some time to get used to it ;)

Best,

David

[sagetrac-dlucas]

comment:10

Disclaimer: the following remarks are only related to the code in itsef. I did not run (yet) extensive tests on border cases and larger cases than the ones covered by doctests.

General remark on exceptions: don't need to write "Incorrect data-type ..." every time, as ValueError will be printed on the screen and it means there is something wrong with the input.

Another remark on documentation: you have to add this module to src/doc/en/reference/coding/index.rst to make it appear in the online documentation. For now, this module is never considered when compiling documentation - which means, even if you run sage --docbuild reference/coding, you won't be able to know if there are some bugs in your doc.

binomial_sum

I think it might be better to make it a private method (which can be done by calling it _binomial_sum).

You could have used already implemented methods, ending up with something like:

return sum(binomial(n, i) for i in range(k+1)) or for i in range(k+1): s += binomial(n, i)

BUT it's much slower than you implementation (up to a factor of 10 according to timeit). So, we should just keep what you did :)

multivariate_polynomial_interpolation

I'd make it a private method as it's only used internally as a helper.
I would also change the name _R to polynomial_ring. It's probably something
you copied from my poor naming choice in grs.py... I changed it in #20744 in the meanwhile ;)

I'd also rename some variables: evaluation2 might be multipoint_evaluation_list or something like that. I would also change the name nq, but I don't have any idea here. I would also rename finiteField as base_field for consistency.
You should be careful with 0s and 1s: the 0 l. 87 is not the same as the one on line 89: the former is the zero of the base field while the latter is the zero of the multivariate polynomial ring where poly lives.
I recommend using specific variables for these zeroes/ones, which you can define as follows: base_field_zero = base_field.zero().

ReedMullerCode

• you need to add :: in the end of your second example's descriptive sentence.

General remark on classes

• Most of your class parameters are public variables that one has to call directly (e.g. C.numberOfVariable) to access. I would change this: make all these variables private (prefix them by an underscore) and write getter methods.
  One should call C.number_of_variables() to the number of variables used.

QAry/BinaryReedMullerCode

• You could add a method to compute the minimum distance, as we know a closed formula to compute it, it's quite a shame to call the exhaustive search algortihm if one types My_rm_code.minimum_distance().
  If q is 2, D = 2^(m-d), otherwise it's q^m - d*q^(m-1), with m the number of variables and d the order.
  ''
  QAryReedMullerCode''

• I would add a WARNING:: block which states that the order has to be less than q to be sure users know about it. Of course, it will be removed later on, but the more informative the better.

Vectorial encoder

• I noticed you compute the generator matrix at construction time. I strongly disagree with this behaviour: as the generator matrix computation can be heavy, I advise you to only compute it when the needed (i.e. in the method generator_matrix). The method generator_matrix should also be cached (use the decorator @cached_method).

• On the generator matrix computation. I think you should use iterators when possible. Especially, the lines

baseFieldTuple=Tuples(baseField.list(),numberOfVariable)
[...] for x in baseFieldTuple.list()

will kill you. For example, over GF(31), with only 4 variables, it takes more than 3 minutes to compute the list of all tuples on my laptop (16 GB RAM).
Using an iterator will not compute the full list of tuples, which saves time and memory for larger codes.

Same for exponents: over GF(23), 4 variables and dimension 6, it takes circa 30 seconds to execute this on my laptop:

exponents=Subsets(range(numberOfVariable)*(q-1), submultiset=True)[0:code.dimension()]

Best,

David

[sagetrac-panda314]

comment:11

Thanks. I have started implementing some of the changes you have suggested.
Regarding formatting, is there any format code or something that i can plug in a ide interface and automatically implement them? It will be tedious to go through the code and manually do them.

Regarding private functions. I had not added examples for them because doctest would not be able to execute them since i had not listed them anywhere. Will writing them as _ solve that?

Replying to @sagetrac-dlucas:

Disclaimer: the following remarks are only related to the code in itsef. I did not run (yet) extensive tests on border cases and larger cases than the ones covered by doctests.

General remark on exceptions: don't need to write "Incorrect data-type ..." every time, as ValueError will be printed on the screen and it means there is something wrong with the input.

Another remark on documentation: you have to add this module to src/doc/en/reference/coding/index.rst to make it appear in the online documentation. For now, this module is never considered when compiling documentation - which means, even if you run sage --docbuild reference/coding, you won't be able to know if there are some bugs in your doc.

binomial_sum

I think it might be better to make it a private method (which can be done by calling it _binomial_sum).

You could have used already implemented methods, ending up with something like:

return sum(binomial(n, i) for i in range(k+1)) or for i in range(k+1): s += binomial(n, i)

BUT it's much slower than you implementation (up to a factor of 10 according to timeit). So, we should just keep what you did :)

multivariate_polynomial_interpolation

I'd make it a private method as it's only used internally as a helper.
I would also change the name _R to polynomial_ring. It's probably something
you copied from my poor naming choice in grs.py... I changed it in #20744 in the meanwhile ;)

I'd also rename some variables: evaluation2 might be multipoint_evaluation_list or something like that. I would also change the name nq, but I don't have any idea here. I would also rename finiteField as base_field for consistency.
You should be careful with 0s and 1s: the 0 l. 87 is not the same as the one on line 89: the former is the zero of the base field while the latter is the zero of the multivariate polynomial ring where poly lives.
I recommend using specific variables for these zeroes/ones, which you can define as follows: base_field_zero = base_field.zero().

ReedMullerCode

• you need to add :: in the end of your second example's descriptive sentence.

General remark on classes

• Most of your class parameters are public variables that one has to call directly (e.g. C.numberOfVariable) to access. I would change this: make all these variables private (prefix them by an underscore) and write getter methods.
  One should call C.number_of_variables() to the number of variables used.

QAry/BinaryReedMullerCode

• You could add a method to compute the minimum distance, as we know a closed formula to compute it, it's quite a shame to call the exhaustive search algortihm if one types My_rm_code.minimum_distance().
  If q is 2, D = 2^(m-d), otherwise it's q^m - d*q^(m-1), with m the number of variables and d the order.
  ''
  QAryReedMullerCode''

• I would add a WARNING:: block which states that the order has to be less than q to be sure users know about it. Of course, it will be removed later on, but the more informative the better.

Vectorial encoder

• I noticed you compute the generator matrix at construction time. I strongly disagree with this behaviour: as the generator matrix computation can be heavy, I advise you to only compute it when the needed (i.e. in the method generator_matrix). The method generator_matrix should also be cached (use the decorator @cached_method).

• On the generator matrix computation. I think you should use iterators when possible. Especially, the lines

baseFieldTuple=Tuples(baseField.list(),numberOfVariable)
[...] for x in baseFieldTuple.list()

will kill you. For example, over GF(31), with only 4 variables, it takes more than 3 minutes to compute the list of all tuples on my laptop (16 GB RAM).
Using an iterator will not compute the full list of tuples, which saves time and memory for larger codes.

Same for exponents: over GF(23), 4 variables and dimension 6, it takes circa 30 seconds to execute this on my laptop:

exponents=Subsets(range(numberOfVariable)*(q-1), submultiset=True)[0:code.dimension()]

Best,

David

[sagetrac-dlucas]

comment:12

Thanks. I have started implementing some of the changes you have suggested.

Cool!

Regarding formatting, is there any format code or something that i can plug in a ide interface and automatically implement them? It will be tedious to go through the code and manually do them.

Not that I know, I'm afraid. I'm not using any IDE but vim, so I can't be sure though.
But if it's just to change MyVariable to my_variable, any text editor has a search and replace feature which will do the job. Of course, you will have to feed it with the target name everytime...

Regarding private functions. I had not added examples for them because doctest would not be able to execute them since i had not listed them anywhere. Will writing them as _ solve that?

Actually, doctests will be executed. Making these methods private with _name will make them disappear from the online doc, but the doctesting framework will run them as well. See _punctured_form in grs.py for an example.

Best,

David

[sagetrac-panda314]

comment:13

Hey, so correct me if i am wrong, [x for x in base_field_tuple] is implicitly implemented using iterator. If that's so i think the following implementation should get rid all the redundant iterations through the sets.

exponent=exponents.first()
for i in range(dimension):

matrix_list.append([reduce(mul, [x[i] for i in exponent],1) for x in base_field_tuple])
exponent=exponents.next(exponent)

Replying to @sagetrac-dlucas:

Disclaimer: the following remarks are only related to the code in itsef. I did not run (yet) extensive tests on border cases and larger cases than the ones covered by doctests.

General remark on exceptions: don't need to write "Incorrect data-type ..." every time, as ValueError will be printed on the screen and it means there is something wrong with the input.

Another remark on documentation: you have to add this module to src/doc/en/reference/coding/index.rst to make it appear in the online documentation. For now, this module is never considered when compiling documentation - which means, even if you run sage --docbuild reference/coding, you won't be able to know if there are some bugs in your doc.

binomial_sum

I think it might be better to make it a private method (which can be done by calling it _binomial_sum).

You could have used already implemented methods, ending up with something like:

return sum(binomial(n, i) for i in range(k+1)) or for i in range(k+1): s += binomial(n, i)

BUT it's much slower than you implementation (up to a factor of 10 according to timeit). So, we should just keep what you did :)

multivariate_polynomial_interpolation

I'd make it a private method as it's only used internally as a helper.
I would also change the name _R to polynomial_ring. It's probably something
you copied from my poor naming choice in grs.py... I changed it in #20744 in the meanwhile ;)

I'd also rename some variables: evaluation2 might be multipoint_evaluation_list or something like that. I would also change the name nq, but I don't have any idea here. I would also rename finiteField as base_field for consistency.
You should be careful with 0s and 1s: the 0 l. 87 is not the same as the one on line 89: the former is the zero of the base field while the latter is the zero of the multivariate polynomial ring where poly lives.
I recommend using specific variables for these zeroes/ones, which you can define as follows: base_field_zero = base_field.zero().

ReedMullerCode

• you need to add :: in the end of your second example's descriptive sentence.

General remark on classes

• Most of your class parameters are public variables that one has to call directly (e.g. C.numberOfVariable) to access. I would change this: make all these variables private (prefix them by an underscore) and write getter methods.
  One should call C.number_of_variables() to the number of variables used.

QAry/BinaryReedMullerCode

• You could add a method to compute the minimum distance, as we know a closed formula to compute it, it's quite a shame to call the exhaustive search algortihm if one types My_rm_code.minimum_distance().
  If q is 2, D = 2^(m-d), otherwise it's q^m - d*q^(m-1), with m the number of variables and d the order.
  ''
  QAryReedMullerCode''

• I would add a WARNING:: block which states that the order has to be less than q to be sure users know about it. Of course, it will be removed later on, but the more informative the better.

Vectorial encoder

• I noticed you compute the generator matrix at construction time. I strongly disagree with this behaviour: as the generator matrix computation can be heavy, I advise you to only compute it when the needed (i.e. in the method generator_matrix). The method generator_matrix should also be cached (use the decorator @cached_method).

• On the generator matrix computation. I think you should use iterators when possible. Especially, the lines

baseFieldTuple=Tuples(baseField.list(),numberOfVariable)
[... ...] for x in baseFieldTuple.list()

will kill you. For example, over GF(31), with only 4 variables, it takes more than 3 minutes to compute the list of all tuples on my laptop (16 GB RAM).
Using an iterator will not compute the full list of tuples, which saves time and memory for larger codes.

Same for exponents: over GF(23), 4 variables and dimension 6, it takes circa 30 seconds to execute this on my laptop:

exponents=Subsets(range(numberOfVariable)*(q-1), submultiset=True)[0:code.dimension()]

Best,

David

[sagetrac-git]

Changed commit from 23ff289 to 5129c91

[sagetrac-git]

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

5129c91

reformatting the file according to standards and rewriting the code to optimise computation time

[sagetrac-dlucas]

comment:15

Hey, so correct me if i am wrong, [x for x in base_field_tuple] is implicitly implemented using iterator. If that's so i think the following implementation should get rid all the redundant iterations through the sets.

Yes, absolutely.

I'm reading your modified code, I'll come back with more comments later on.

[sagetrac-dlucas]

comment:16

Hello,

Some more comments:

• I noticed you add both ReedMullerCode, BinaryReedMullerCode and QAryReedMullerCode to codes_catalog.py. But with our design, only ReedMullerCode should be in this file, as the user should never access the classes themselves.

_multivariate_polynomial_interpolation

• You left a reference to _R in the docstring while it no longer exists
• Is the base field (and the cardinality) really needed? I would rather remove them from the list of inputs and recover them from evaluation. This way, one has to provide evaluation as a vector over a finite field, you get this finite field by doing F = evaluation.base_ring(), you check that F is the base ring of polynomial_ring and that's it. You can get q with the appropriate call on F.
• As my previous comment implies, I would only allow evaluation to be a vector (and not a list). After all, it's a private method you only use to recover the original message as a polynomial from a codeword, and the latter is necessarily a vector, isn't it?
• l. 105: is there a way to avoid a call to base_field.list()? I know that in most cases, this list will be rather small, but it's not really efficient to build a full list (especially in a recursive pattern, because you will build it a lot of times...). This time again, I'd suggest an iterator over the finite field.

ReedMullerCode

• the WARNING block should be added in the module documentation as well. The syntax on this block is the following

.. WARNING:: 
    body of the block

See linear_code.py, line 682 for an example.
I would also change the message. I propose For now, this implementation only supports Reed-Muller codes whose order is less than q. Such a message implies it will be extended later, I think it's more positive this way ;)

Q-ary and Binary classes

• I think it's not necessary to save q as a class parameter. The user can access it by typing C.base_field().cardinality(), it's not something specific to the class (or something hard to "compute"), so it should not be saved.

• I prefer full names for user-accessed methods. I'm okay with num_var as an internal variable, but its getter should be called number_of_variables instead.

Vectorial encoder

• In generator_matrix, you're calling self.code() a lot of times. I think you should store it in a local variable which will reduce the amount of calls to this method.

Best,

David

[sagetrac-panda314]

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

[sagetrac-panda314]

Changed commit from 13cda90 to 5ec9c6c

[sagetrac-panda314]

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

[sagetrac-dlucas]

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

[sagetrac-dlucas]

Changed commit from 5ec9c6c to e3f81ec

[sagetrac-dlucas]

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

[sagetrac-panda314]

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.

[sagetrac-git]

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

3cce07f

Updated to latest beta and fixed conflicts

[sagetrac-git]

Changed commit from e3f81ec to 3cce07f

[sagetrac-dlucas]

comment:51

Merge conflict, please merge in next beta.

Done, ticket open for review.

David

[sagetrac-panda314]

comment:52

Replying to @sagetrac-dlucas:

Merge conflict, please merge in next beta.

Seems fine. Tests passed.

Done, ticket open for review.

David

[sagetrac-dlucas]

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