Opened 5 years ago
Last modified 4 years ago
#20938 needs_work enhancement
Decoder for Reed Muller Codes
Reported by: | panda314 | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.3 |
Component: | coding theory | Keywords: | |
Cc: | dlucas, jsrn | Merged in: | |
Authors: | Parthasarathi Panda | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/panda314/decoder_for_reed_muller_codes (Commits, GitHub, GitLab) | Commit: | b83ade8a5dfddda814d68cc1a09a4e2d3ab3997d |
Dependencies: | Stopgaps: |
Description
This ticket proposes a implementation of Reed Muller Codes. It contains:
- A code class, BinaryReedMullerMajorityDecoder?, for decoding binary reed muller codes using majority voting algorithm.
- A code class, QAryReedMullerRSDecoder, for decoding q-ary reed muller codes by embedding it in a reed solomon supercode.
Change History (11)
comment:1 Changed 5 years ago by
- Branch set to u/panda314/decoder_for_reed_muller_codes
comment:2 Changed 5 years ago by
- Branch changed from u/panda314/decoder_for_reed_muller_codes to u/dlucas/decoder_for_reed_muller_codes
comment:3 follow-up: ↓ 4 Changed 5 years ago by
- Commit set to 86c1629afaa869dd2086b6dd569939a66e3e4ad4
- Status changed from new to needs_review
comment:4 in reply to: ↑ 3 Changed 5 years ago by
What are ticket states? Is there a way to automate the merging with latest version?
I will edit and apply the pep8 protocols..
As far as i remember the reed solomon super code method is apllicable only for q-ary reed muller codes with order<field_size. It is applicable for binary reed muller code only if the order<=1. I guess i can allow for such binary reed muller codes.
Yeah i will add the option for using a reed solomon decoder. I had arbitrarily picked Gao.
Replying to dlucas:
Hello,
I pushed a new version of your branched merged with latest version (there was a conflict and I allowed me to fix it myself). I know this ticket was ready for review because you told me so by email, but would you please use ticket states from now on? It makes the process smoother for everyone.
Here are my comments on reviewing your work:
- a lot of lines are not in PEP8-compliance: for instance, you write
a=b
where it should bea = b
. You can check the rules regarding whitespaces and operators here.
- There are some very long lines (95+ characters) in your file. See lines 1212-1215 for instance.
While I'm not adamant that the 80 characters rule should be followed everywhere (I tend to accept 85 characters), I think 95+ is too much.
- In RSDecoder's constructor (line 1241), you copy-pasted the sentence illustrating your
TESTS
block from the class above. It should not mention Binary Reed-Muller code, but RM code, as it works for any RM code.
- While I'm at it, you wrote
if not isinstance(code, QAryReedMullerCode)
, but this works with anyq
, even2
, doesn't it? Because if you try to build a RSDecoder with a binary RM code, it fails...
- Same decoder: is there a reason to enforce the use of Gao decoder? I might be wrong, but I think that as long as you manage to build your GRS code, you can use any decoder over it. Hence, I suggest to use the same kind of mechanism I used with
PuncturedCode
,SubfieldSubcode
,ExtendedCode
etc: allow the user to pass an instance of a decoder over the GRS code as input to RM code's decoder. Then use this decoder to perform decoding. This triggers some changes in your design: first, you have to implement a function to get the GRS code from a RM code, instead of computing it inplace indecode_to_code
. I think it's nice to have such a feature anyway. Then, you have to add some input sanitization checks at construction time (which will ensure the decoder provided by the user is a decoder over the GRS code). You will also have to changedecoding_radius
, which now returns the result ofGRS's decoder.decoding_radius()
. And it also meansdecoder_type
is now{dynamic}
.I still need to read carefully your implementation of the majority vote decoder. Otherwise, it looks quite good. Your documentation, especially, is well written and explains very well to the user how each decoder works.
Best,
David
New commits:
b1642f8 adding decoders for reed muller code
699b2e7 removing some unecessary imports
86c1629 Updated to latest version and fixed conflict
comment:5 Changed 5 years ago by
What are ticket states? Is there a way to automate the merging with latest version?
Oh, no, you have to merge it by hand. What I meant by ticket states is to switch from new
to needs_review
when you finish working on it, etc.
As far as i remember the reed solomon super code method is apllicable only for q-ary reed muller codes with order<field_size. It is applicable for binary reed muller code only if the order<=1. I guess i can allow for such binary reed muller codes.
Yes, that would be great!
Yeah i will add the option for using a reed solomon decoder. I had arbitrarily picked Gao.
Ok, perfect.
David
comment:6 Changed 5 years ago by
- Branch changed from u/dlucas/decoder_for_reed_muller_codes to u/panda314/decoder_for_reed_muller_codes
comment:7 Changed 5 years ago by
- Commit changed from 86c1629afaa869dd2086b6dd569939a66e3e4ad4 to d158aad633a3902c523957dcfa5d0b0b639dc813
Sorry for delay. Internet problems.
So i added the option for taking in decoders by the user. I added a function ReedSolomonSupercode
that computes the super code of a reed muller code which is available to a user. I also added some extra functions to the decoder to access the supercode and its associated decoder.
Took care of formatting. Let me know if i missed few spots.
I have started my full-time employment. So i will not be able to work as quickly.
New commits:
d158aad | converted the QAryReedMullerRSDecoder to dynamic, allowing the user to pass the reed solomon decoder it wants to pass
|
comment:8 Changed 5 years ago by
Hello,
Sorry for delay. Internet problems.
No worries, it's fine :)
I have a few remarks:
- I'd prefer to have
ReedSolomonSupercode
as a class method and not a global method. I think it's a a bit more intuitive to writeC.ReedSolomonSupercode()
. Also, the user will be able to find this method by typingC.<tab>
in a terminal, which is nice. But this raises an issue: as we have *two* classes for Reed-Muller codes, there will be code duplication... Thus I suggest to make the method you wrote a private method for this module only. And then, in bothQAry
andBinary
you add a new method, let's sayreed_solomon_supercode(self, p = None)
which returnsReedSolomonSupercode(self, p)
. You still have some duplication, but it's a bit better as you don't copy-paste the whole method twice.
- Still talking about
ReedSolomonSupercode
, I find its documentation rather uninformative: could you please add a few more lines to explain how this Reed-Solomon code is built, and what it is wrt. the Reed-Muller code? Also, forcode
, you wroteA Reed-Muller code of appropiate order.
. What doesappropriate order
mean?
- And last one on
ReedSolomonSupercode
: you forgot to add::
at the end of you sentence in theEXAMPLES
block.
- In the Supercode decoder, two methods (
reed_solomon_supercode
andreed_solomon_decoder
) are not documented.
- The Supercode decoder should change its types at construction time for the types of the RS decoder.
You can copy-paste lines 347-349 from
extended_code.py
if you want:)
.
decoding_radius
in the Supercode decoder should take both*args
and**kwargs
as input and pass these to the RS decoder'sdecoding_radius
. For example, RS error-erasure decoder requires to pass the number of erasures as an argument ofdecoding_radius
, so for now, callingdecoding_radius
from the supercode decoder with error-erasure as RS decoder fails.
- Since #20840, it's no longer necessary to manually add generic decoders to the list of
_registered_decoders
. So you can remove the registration lines related to Syndrome decoder.
- As it can be long to compute, and it might be called quite often, I suggest to make
_list_polynomial
a cached method.
- Can you write a few more lines of documentation to
_set_to_mask
? I think it's a bit hard to understand what it does just by reading the doc for now.
- In
_list_polynomial
, I'd writeReturn the list of all polynomials of degree etc
instead ofLists all polynomials of degree etc
to be consistent with the usual way of writing these sentences.
I have started my full-time employment. So i will not be able to work as quickly.
Sure, don't worry! Take all the time you need.
David
comment:9 follow-up: ↓ 10 Changed 5 years ago by
- Commit changed from d158aad633a3902c523957dcfa5d0b0b639dc813 to b83ade8a5dfddda814d68cc1a09a4e2d3ab3997d
Branch pushed to git repo; I updated commit sha1. New commits:
b83ade8 | moving ReedSolomonSupercode to individual classes and adding to documentation
|
comment:10 in reply to: ↑ 9 Changed 5 years ago by
So the canges in this commit includes:
- Adding
reed_solomon_supercode()
function to each reed muller code classes rather that making it a global method.
- Modified documentation for
reed_solomon_supercode()
- Modified
reed_solomon_supercode()
to give the reed solomon supercode for ALL binary reed muller codes (not useful in decoding though)
- Modified the constructor of
QAryReedMullerRSDecoder
to change it's decoder_type.
- Modifed
decoding_radius
to allow additional arguments.
- removed uneccessary registration of syndrome decoders
- Adding documentation to
reed_solomon_supercode()
andreed_solomon_decoder()
- Made
_list_polynomial
a cached function
- Modified documentation of
_list_polynomial
andset_to_mask
Let me know if i missed out something or have further reviews.
comment:11 Changed 4 years ago by
- Status changed from needs_review to needs_work
Hi, it seems this ticket is a bit stalled...
Doctest failures against 7.4:
- DeprecationWarning?: codes.RandomLinearCode?(n, k, F) is deprecated. Please use codes.random_linear_code(F, n, k) instead
Other comments:
_list_polynomial(F, x, d)
already exists asR.<x>=F[]; R.polynomials(max_degree=d-1)
_set_to_mask
is used only in one function, I would inline it, eventually as the one linersum(1<<i for i in s)
- use
k in d
instead ofd.has_key(k)
- I wouldn't use
dict
as a variable name: it shadows the built-in type
- Instead of the
while True
loop just iterate overSubsets
(oritertools.combinations
see next point)
- you might be interested by this:
sage: %time len(list(Subsets(range(20), 5))) CPU times: user 1.08 s, sys: 24 ms, total: 1.1 s Wall time: 1.04 s 15504 sage: %time len(list(itertools.combinations(range(20), 5))) CPU times: user 4 ms, sys: 0 ns, total: 4 ms Wall time: 3.35 ms 15504 sage: %timeit s = Set(range(4)).difference([1,3]) 10000 loops, best of 3: 106 µs per loop sage: %timeit s = set(range(4)).difference([1,3]) 100000 loops, best of 3: 1.96 µs per loop
Hello,
I pushed a new version of your branched merged with latest version (there was a conflict and I allowed me to fix it myself). I know this ticket was ready for review because you told me so by email, but would you please use ticket states from now on? It makes the process smoother for everyone.
Here are my comments on reviewing your work:
a=b
where it should bea = b
. You can check the rules regarding whitespaces and operators here.While I'm not adamant that the 80 characters rule should be followed everywhere (I tend to accept 85 characters), I think 95+ is too much.
TESTS
block from the class above. It should not mention Binary Reed-Muller code, but RM code, as it works for any RM code.if not isinstance(code, QAryReedMullerCode)
, but this works with anyq
, even2
, doesn't it? Because if you try to build a RSDecoder with a binary RM code, it fails...PuncturedCode
,SubfieldSubcode
,ExtendedCode
etc: allow the user to pass an instance of a decoder over the GRS code as input to RM code's decoder. Then use this decoder to perform decoding. This triggers some changes in your design: first, you have to implement a function to get the GRS code from a RM code, instead of computing it inplace indecode_to_code
. I think it's nice to have such a feature anyway. Then, you have to add some input sanitization checks at construction time (which will ensure the decoder provided by the user is a decoder over the GRS code). You will also have to changedecoding_radius
, which now returns the result ofGRS's decoder.decoding_radius()
. And it also meansdecoder_type
is now{dynamic}
.I still need to read carefully your implementation of the majority vote decoder. Otherwise, it looks quite good. Your documentation, especially, is well written and explains very well to the user how each decoder works.
Best,
David
New commits:
adding decoders for reed muller code
removing some unecessary imports
Updated to latest version and fixed conflict