#20705: Classes for Reed Muller Codes
-------------------------------------+-------------------------------------
Reporter: panda314 | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.3
Component: coding theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/panda314/classes_for_reed_muller_codes|
23ff289a86e2d4266512e631f50ee75c6338ccd8
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by dlucas):
* status: needs_review => needs_work
Comment:
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 `0`s and `1`s: 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
--
Ticket URL: <http://trac.sagemath.org/ticket/20705#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
