search

veeresht / CommPy

Digital Communication with Python
http://veeresht.github.com/CommPy
BSD 3-Clause "New" or "Revised" License
538 stars 176 forks source link

PR #74 introduce a bug in viterbi_decode #76

Closed BastienTr closed 3 years ago

BastienTr commented 3 years ago

I just checked the merged PR #74 and it comes out that it introduces a bug. You can reproduce the issue by running test_conv_encode_viterbi_decode in test_convcode.py.

This bug is undetected by Travis due to the flag -a '!slow' in the configuration file. I'm about to open a PR to remove this flag and we could discuss about this change there (see #77). https://github.com/veeresht/CommPy/blob/b104c99ee52df10b3e37571741d1460ac24b60cd/.travis.yml#L34

Let's now discuss on the bug introduced in #74. The new _compute_branch_metric with LRU caching is called as follow: https://github.com/veeresht/CommPy/blob/b104c99ee52df10b3e37571741d1460ac24b60cd/commpy/channelcoding/convcode.py#L623

However, with a hard decoding type, the function calls .astype on the arguments. This is obviously not possible on tuples. https://github.com/veeresht/CommPy/blob/b104c99ee52df10b3e37571741d1460ac24b60cd/commpy/channelcoding/convcode.py#L575-L578

It is not possible to just keep the tuples provided since hamming_dist relies on numpy capabilities. https://github.com/veeresht/CommPy/blob/b104c99ee52df10b3e37571741d1460ac24b60cd/commpy/utilities.py#L112-L132

I don't have time now to explore if this change should be reverted or if there is a better solution. Indeed, converting back and forth from numpy arrays to tuples may lead to a overhead greater than the gain obtained with the LRU cache. I'll try to have a look in the next days but I can't be sure on when it will be possible. @eSoares do you have any suggestions ?

eSoares commented 3 years ago

Well spotted! I always try to also run all the tests in my IDE before PR, but this one was not caught...

I was departing from work when the email hit, so I didn't look to much, but from a couple of quick tests (similar to the one in the PR #74 ) with vs without the caching was something like:

With caching+bugfix: 0:02:52.711836 Without caching: 0:06:06.118742

The bugfix that I made was the following chance:

@functools.lru_cache(maxsize=128, typed=False)
def _compute_branch_metrics(decoding_type, _r_codeword: tuple, _i_codeword_array: tuple):
    r_codeword = np.array(list(_r_codeword))
    i_codeword_array = np.array(list(_i_codeword_array))
   ....

So, converting back still looks an improvement over no caching at all. But tomorrow I will run a couple of more tests.

BastienTr commented 3 years ago

Great! Thanks for the help :+1:

BastienTr commented 3 years ago

Why do you use a list before building the numpy array? This should give the same results with less type changes

def _compute_branch_metrics(decoding_type, _r_codeword: tuple, _i_codeword_array: tuple):
    r_codeword = np.array(_r_codeword)
    i_codeword_array = np.array(_i_codeword_array)
eSoares commented 3 years ago

Yes, my mistake. No need to unwrap to list before constructing an numpy array. PR with the fix done.