#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|
260d8da2f65c87ecf0f3bb703608148684823d37
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by panda314):
Replying to [comment:23 dlucas]:
the error with order 0 was because '.next()' function was not computing in
the last element of the subsets (a problem if the dimension becomes equal
to the total number of possible exponents) anyways replaced with iterator
so that problem is gone.
I was under the impression that .next() works like iterator. Anyways i
used the python's iterator hopefully it will speed it up.
Speed does seem to be a big issue with this implementation. I am unable to
lay a finger on the exact problem causing that.
Well i found reed solomon pretty advanced :D . Feels good to see
'Copyright (C) 2016 Parthasarathi Panda <[email protected]>'
:) . Thanks for all the help. Next stop decoding
> Hello,
>
> Some other remarks (the last ones from me):
>
> - in the input sanitization, you test integer parameters using this
statement: `if not isinstance(param, Integer)`. Actually, as in Sage you
can have both Sage Integers and Python ints, you need to write `if not
isinstance(param, (int, Integer))` otherwise if the user passes a Python
int for `param` it will be rejected by the check.
>
> - in your `minimum_distance` method for `QAryReedMullerCode`, you should
use integer division `//` instead of `/`. I agree the result will always
be an integer because of the parameters, but using `/` returns a Rational
while `//` returns an Integer, and I think it's better to return an
Integer.
>
> - method `generator_matrix` does not work if order is 0:
>
> {{{
> sage: sage: F = GF(3)
> sage: C = codes.[wiki:ReedMullerCode](F, 0, 2)
> sage: sage: E = codes.encoders.[wiki:ReedMullerVectorEncoder](C)
> sage: sage: E.generator_matrix()
>
> BOOM (StopIteration)
> }}}
>
> In case of order 0, just return a matrix which has only one line of `1`
(it is a repetition code in that case).
>
> - Still on generator matrix, you're using `exponents.first()` and
`exponents.next()`. Why not using a "true" iterator instead? As you take
the elements in `Subsets` one by one following the order they've been
sorted, an Iterator has a better complexity in that case, because
`next(obj)`'s complexity is `O(r)` where `r` is the rank of `obj`.
>
> - Also, `generator_matrix` method is quite slow: with a RM code over
`GF(16)`, order 14, 3 variables, it takes around 30s to compute its
generator matrix (while with a GRS code over GF(4096), dimension 680, it
takes around 3 seconds). It's just a remark so we keep it in mind, and I
do not request any changes for this ticket. I'm completely fine with your
implementation as is for a first ticket, and we can work on efficiency
later on if we want to!
>
> - Same with `encode` in `PolynomialEncoder`: some algorithms for fast
multipoint evaluation exist, and we can use them to speed up this
encoding. But once again, your implementation is definitely good enough
for a first ticket!
>
> Otherwise, it sounds good. It's quite an impressive work for your first
ticket, well done!
> You will be the first one to have his implementation of an "advanced"
linear code family in Sage. I'm jealous `;)`
>
> David
>
--
Ticket URL: <http://trac.sagemath.org/ticket/20705#comment:25>
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.
