#20201 closed enhancement (fixed)

Improving Efficiency of LinearCode.NearestNeighborDecoder method

Reported by: arpitdm Owned by:
Priority: major Milestone: sage-7.2
Component: coding theory Keywords: beginner
Cc: dlucas, jsrn Merged in:
Authors: Arpit Merchant Reviewers: David Lucas
Report Upstream: N/A Work issues:
Branch: febfd7f (Commits) Commit: febfd7f6b8ed021f2be228645b304ed8926509e9
Dependencies: Stopgaps:

Description

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.

Change History (22)

comment:1 Changed 16 months ago by arpitdm

  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 16 months ago by arpitdm

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(qk).

comment:3 Changed 16 months ago by jsrn

Yes, that sounds like a good plan!

comment:4 Changed 15 months ago by arpitdm

  • Branch set to u/arpitdm/improving_efficiency_of_linearcode_nearestneighbordecoder_method

comment:5 Changed 15 months ago by arpitdm

  • Commit set to b13f73f6072b5bb52e27e5a0a69cc65e7b265e29

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:

b13f73fimproved efficiency of the decode_to_code method of the Nearest Neighbor Decoder

comment:6 Changed 15 months ago by dlucas

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

comment:7 Changed 15 months ago by git

  • Commit changed from b13f73f6072b5bb52e27e5a0a69cc65e7b265e29 to 170b3fc8ff8e9f7333a06e0c84f552857e911732

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

170b3fcRemoved 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.

comment:8 Changed 15 months ago by arpitdm

  • Status changed from new to needs_review

comment:9 follow-up: Changed 15 months ago by dlucas

  • Milestone changed from sage-7.1 to sage-7.2
  • Status changed from needs_review to needs_work

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

comment:10 in reply to: ↑ 9 Changed 15 months ago by jsrn

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.

comment:11 Changed 15 months ago by jsrn

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().

comment:12 Changed 15 months ago by dlucas

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.

comment:13 Changed 15 months ago by arpitdm

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

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

comment:14 Changed 15 months ago by jsrn

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).

comment:15 Changed 15 months ago by git

  • Commit changed from 170b3fc8ff8e9f7333a06e0c84f552857e911732 to 9fcf54ddeae6ce3bf0815390caf4e2c24fcdd0aa

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

9fcf54dupdated the initialization using iter

comment:16 Changed 15 months ago by dlucas

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

comment:17 Changed 15 months ago by arpitdm

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.

comment:18 Changed 15 months ago by dlucas

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

comment:19 Changed 14 months ago by git

  • Commit changed from 9fcf54ddeae6ce3bf0815390caf4e2c24fcdd0aa to febfd7f6b8ed021f2be228645b304ed8926509e9

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

febfd7fUse the zero of the code to initialize

comment:20 Changed 14 months ago by arpitdm

  • Status changed from needs_work to needs_review

comment:21 Changed 14 months ago by dlucas

  • Reviewers set to David Lucas
  • Status changed from needs_review to positive_review

Hello,

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

Best,

David

comment:22 Changed 14 months ago by vbraun

  • Branch changed from u/arpitdm/improving_efficiency_of_linearcode_nearestneighbordecoder_method to febfd7f6b8ed021f2be228645b304ed8926509e9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.