Decoder for Reed Muller Codes

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

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.

CC: @sagetrac-dlucas @johanrosenkilde

Component: coding theory

Author: Parthasarathi Panda

Branch/Commit: u/panda314/decoder_for_reed_muller_codes @ b83ade8

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

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

Branch: u/panda314/decoder_for_reed_muller_codes

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

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

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

comment:3

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 be a = 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 any q, even 2, 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 in decode_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 change decoding_radius, which now returns the result of GRS's decoder.decoding_radius(). And it also means decoder_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

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

Commit: 86c1629

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

comment:4

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 @sagetrac-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 be a = 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 any q, even 2, 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 in decode_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 change decoding_radius, which now returns the result of GRS's decoder.decoding_radius(). And it also means decoder_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

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

comment:5

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

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

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

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

comment:7

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

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

Changed commit from 86c1629 to d158aad

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

comment:8

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 write C.ReedSolomonSupercode(). Also, the user will be able to find this method by typing C.<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 both QAry and Binary you add a new method, let's say reed_solomon_supercode(self, p = None) which returns ReedSolomonSupercode(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, for code, you wrote A Reed-Muller code of appropiate order.. What does appropriate order mean?

• And last one on ReedSolomonSupercode: you forgot to add :: at the end of you sentence in the EXAMPLES block.

• In the Supercode decoder, two methods (reed_solomon_supercode and reed_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's decoding_radius. For example, RS error-erasure decoder requires to pass the number of erasures as an argument of decoding_radius, so for now, calling decoding_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 write Return the list of all polynomials of degree etc instead of Lists 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

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

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

b83ade8

moving ReedSolomonSupercode to individual classes and adding to documentation

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

Changed commit from d158aad to b83ade8

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

comment:10

So the canges in this commit includes:

1. Adding reed_solomon_supercode() function to each reed muller code classes rather that making it a global method.

2. Modified documentation for reed_solomon_supercode()

3. Modified reed_solomon_supercode() to give the reed solomon supercode for ALL binary reed muller codes (not useful in decoding though)

4. Modified the constructor of QAryReedMullerRSDecoder to change it's decoder_type.

5. Modifed decoding_radius to allow additional arguments.

6. removed uneccessary registration of syndrome decoders

7. Adding documentation to reed_solomon_supercode() and reed_solomon_decoder()

8. Made _list_polynomial a cached function

9. Modified documentation of _list_polynomial and set_to_mask

Let me know if i missed out something or have further reviews.

[2c00b582-cfe9-43b9-8124-fec470060704]

comment:11

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 as R.<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 liner sum(1<<i for i in s)

• use k in d instead of d.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 over Subsets (or itertools.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