Opened 7 years ago

Closed 7 years ago

#20201 closed enhancement (fixed)

Improving Efficiency of LinearCode.NearestNeighborDecoder method

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

Status badges

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 7 years ago by Arpit Merchant

Type: PLEASE CHANGEenhancement

comment:2 Changed 7 years ago by Arpit Merchant

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 7 years ago by Johan Rosenkilde

Yes, that sounds like a good plan!

comment:4 Changed 7 years ago by Arpit Merchant

Branch: u/arpitdm/improving_efficiency_of_linearcode_nearestneighbordecoder_method

comment:5 Changed 7 years ago by Arpit Merchant

Commit: 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 7 years ago by David Lucas

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 7 years ago by git

Commit: b13f73f6072b5bb52e27e5a0a69cc65e7b265e29170b3fc8ff8e9f7333a06e0c84f552857e911732

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 7 years ago by Arpit Merchant

Status: newneeds_review

comment:9 Changed 7 years ago by David Lucas

Milestone: sage-7.1sage-7.2
Status: needs_reviewneeds_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 7 years ago by Johan Rosenkilde

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 7 years ago by Johan Rosenkilde

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 7 years ago by David Lucas

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 7 years ago by Arpit Merchant

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 7 years ago by Johan Rosenkilde

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 7 years ago by git

Commit: 170b3fc8ff8e9f7333a06e0c84f552857e9117329fcf54ddeae6ce3bf0815390caf4e2c24fcdd0aa

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

9fcf54dupdated the initialization using iter

comment:16 Changed 7 years ago by David Lucas

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 7 years ago by Arpit Merchant

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 7 years ago by David Lucas

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 7 years ago by git

Commit: 9fcf54ddeae6ce3bf0815390caf4e2c24fcdd0aafebfd7f6b8ed021f2be228645b304ed8926509e9

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

febfd7fUse the zero of the code to initialize

comment:20 Changed 7 years ago by Arpit Merchant

Status: needs_workneeds_review

comment:21 Changed 7 years ago by David Lucas

Reviewers: David Lucas
Status: needs_reviewpositive_review

Hello,

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

Best,

David

comment:22 Changed 7 years ago by Volker Braun

Branch: u/arpitdm/improving_efficiency_of_linearcode_nearestneighbordecoder_methodfebfd7f6b8ed021f2be228645b304ed8926509e9
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.