Improving Efficiency of LinearCode.NearestNeighborDecoder method

[arpitdm]

The decode_to_code method of the current implementation of the NearestNeighborDecoder creates and stores the distances between the received word and every codeword. It then sorts the entire list in order to find the closest codeword. This takes asymptotic memory and time in the size of the code which can be very inefficient for large input.
This should be improved.

CC: @sagetrac-dlucas @johanrosenkilde

Component: coding theory

Author: Arpit Merchant

Branch/Commit: febfd7f

Reviewer: David Lucas

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

[arpitdm]

comment:2

Solution idea: If r is the received codeword, we compute the Hamming weight for the first codeword c in code C and store that as minimum. We then iterate over the rest of the codewords. If a codeword of lesser Hamming weight is found, the minimum is updated accordingly, else it remains the same. That way, the memory requirement will be that of a single codeword and the time would be the O(q^k).

[johanrosenkilde]

comment:3

Yes, that sounds like a good plan!

[arpitdm]

Branch: u/arpitdm/improving_efficiency_of_linearcode_nearestneighbordecoder_method

[arpitdm]

comment:5

I ran some tests, as far as I understood them. It cleared them all. But this is not be ready to merge yet. I thought I would put up a "changes until now" commit. Have I made mistake(s)?
Also, in the documentation of the current version, the example gives "word" as input to the method. Is that correct or should it be "w_err"?

---

New commits:

b13f73f

improved efficiency of the decode_to_code method of the Nearest Neighbor Decoder

[arpitdm]

Commit: b13f73f

[sagetrac-dlucas]

comment:6

Hello,

I finally looked at the code, my remarks follow:

• You're absolutely right, it should be w_err and not word as input to decode_to_code in the doctest.

• I'm not a huge fan of the check depending on flag which will always fail except on the first time it is performed.
  I suggest you use an iterator over the codewords instead: you perform this initialization step outside the loop and then the loop only contains the comparison test on hamming weights.
  By the way, a linear code always contains the zero word, and, according to the way Sage sorts the elements of a code, C[0] will always be the zero vector of the ambient space of C.
  So you can directly set h_min to the hamming weight of r.

Something like:

It = iter(C.list())
c_min = It.next()
h_min = r.hamming_weight()
try:
    #loop
except StopIteration:
    pass
c_min.set_immutable()
return c_min

Oh, and when you finish your work on a ticket, don't forget to set it to needs_review (under "modify ticket button".

Apart from that, I'm fine with your code!

David

[sagetrac-git]

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

170b3fc

Removed the use of a flag variable and used iterator to initialize the loop over the code. Edited the documentation to match that of the decode_to_code method of the Syndrom Decoding algorithm.

[sagetrac-git]

Changed commit from b13f73f to 170b3fc

[sagetrac-dlucas]

comment:9

Hello,

You made a mistake when declaring the iterator: It = iter(self.code.list()) won't work (and does not) as code is a method over self. So it should be: It = iter(self.code().list()).

You should always run the doctests after changing something, as they help you to catch errors of this kind.
Use these commands:

sage -b #this rebuilds sage, necessary to include modifications made
sage -t <path to file> #here it will be sage -t linear_code.py

This does not cause any trouble here, but I like being specific with exceptions, so I'd rather say

try:
    #blah
except StopIteration:
    pass

This way, you only pass when a StopIteration occurs, and any other exception still returns the appropriate error message. Well, I don't see how any other exception could occur here, but the most accurate the better, doesn't it?

Best,

David

[johanrosenkilde]

comment:10

You made a mistake when declaring the iterator: It = iter(self.code.list()) won't work (and does not) as code is a method over self. So it should be: It = iter(self.code().list()).

Actually, that's bad too: self.code().list() is going to instantiate an explicit list of all codewords in memory, so you're back to using exponential memory. You could write It = iter(self.code()): that would make an explicit iterator without requiring exponential memory. However, that's C++ style coding. It is much more pythonic to write something like:

for c in self.code():
    #blah

It is nothing but syntactic sugar for instantiating the iterator, but it is much more readable and less prone to programming errors.

I have ever only created explicit iterators in very rare cases in Python.

[johanrosenkilde]

comment:11

Ah, I see now what you used the iterator for: picking out a first element. However, c_min should go with h_min, in which case c_min should just be initialised to the zero codeword, e.g. c_min = self.code().zero().

[sagetrac-dlucas]

comment:12

Ah, I see now what you used the iterator for: picking out a first element.

Yes, that's what I had in mind when I suggested this.

[arpitdm]

comment:13

I'm getting some weird errors when I use those commands you specified.

./sage -br -> This is the problem I'm facing.

[johanrosenkilde]

comment:14

It seems to be a problem with compilation in general. Did you try make distclean && make? Whenever you're stuck because Sage compilation misbehaves in strange ways, that's what you should try (unfortunately, it takes a few hours to recompile everything).

[sagetrac-git]

Changed commit from 170b3fc to 9fcf54d

[sagetrac-git]

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

9fcf54d

updated the initialization using iter

[sagetrac-dlucas]

comment:16

Hello,

You have two choices here:

1. You rollback to the previous implementation using a for loop, but in that case you get rid of anything related to iterators.
2. You stick to the idea using iterator, and in that case, you actually use an iterator.

In your latest push, you removed the line creating the iterator, but kept the try/except block which attempts to catch a StopIteration exception... Which cannot occur, because there is no longer an iterator available!

Pick the one you prefer, and change the rest of the code accordingly.

Another remark: if you think your push is ready for review, please set the ticket to needs_review :)

Best,

David

[arpitdm]

comment:17

I was thinking that the first idea is more convenient. The following should suffice, right?

c_min = self.code().zero()
h_min = r.hamming_weight()
for c in self.code():
if (c-r).hamming_weight() < h_min:
h_min = (c-r).hamming_weight()
c_min = c
c_min.set_immutable()
return c_min

Also, I was just testing commits after I fixed that pkgconfig error and in that confusion, I forgot to remove the try-except catch. Sorry.

[sagetrac-dlucas]

comment:18

Also, I was just testing commits after I fixed that pkgconfig error and in that confusion, I forgot to remove the try-except catch. Sorry.

That's fine :)

Otherwise, I think the code you suggest is good.

Best,

David

[sagetrac-git]

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

febfd7f

Use the zero of the code to initialize

[sagetrac-git]

Changed commit from 9fcf54d to febfd7f

[sagetrac-dlucas]

Reviewer: David Lucas

[sagetrac-dlucas]

comment:21

Hello,

Tests passes, the code and documentation are good, giving positive review.

Best,

David

[vbraun]

Changed branch from u/arpitdm/improving_efficiency_of_linearcode_nearestneighbordecoder_method to febfd7f