Wrong output table for trellis in convcode.py (Probably in other parts too)

[ArmanRZ]

When creating the output table for Convolutional Codes, you have to notice that the generator matrix polynomials and shift registers don't match up in their direction (polynomials are expressed left-to-right, while the corresponding shift register is right-to-left. To calculate the output, you need to reverse either one first before multiplication.

A quick fix: In lines 157-158 of convcode.py replace: generator_array = dec2bitarray(g_matrix[l][r], memory[l] + 1) with: generator_array = dec2bitarray(g_matrix[l][r], memory[l] + 1)[::-1] to reverse the generator's corresponding bit array to match with the shift register's order.

Note: I didn't check the feedback loop. It might have the same problem.

[BastienTr]

Hi @ArmanRZ,

Thanks for your feedback. It's true that the different order between polynomials and shift registers is misleading. This drawback appeared as a result of backwards compatibility issues and the definition of other library functions. However, I don't think there are any inconsistencies.

test_convcode.py compares for several configurations the output of the code with a calculation I did by hand. The results matche each time. Do you notice any error in this test?

Also, the development version on GitHub provides an additional argument and clearer documentation of the polynomials order (MSB or LSB first). This change is not yet added in a pip version but you should take a look at it as well.

Could you please tell me if the answer convinces you or if you think there is still an error?

[ArmanRZ]

Thank you Bastien for your response, I didn't check that file. But I was working with Bluetooth5 FEC scheme I noticed that. I did a simple test for BT5 scheme (octal [17 15] / decimal [15 13]). The results 1) from my own encoder function, and 2) on paper by hand matched up, by they didn't match up with that of 3) commpy. I had to debug and fix it in the way I mentioned above to get consistent results for all three. I'll be grateful if you double-check.

[BastienTr]

I would be glad to have a look and found out what's going on. Could you please provide your information (paper or expected result ; assumptions on bit ordering for input and output ; numbering of shift registers). I'll have a look ASAP

[ArmanRZ]

Sorry for being late on this Bastien. Bluetooth5's FEC is g=[0o17 0o15] and feedback=0

I tested this example input: [1, 0, 0, 1, 1, 0, 1, 0, 0, 0] My hand-derived output as well as a simple function I wrote were giving me this output: [1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1] Your output commpy was returning was the codeword: [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1] Which was mismatching. The trellis turned out to be wrong.

After the fix I proposed, the trellis is corrected and matches the trellis expected from BT5's FEC. The outputs also match as expected.

That would be great if you try it yourself and let me know.

[BastienTr]

Hi @ArmanRZ, Thanks for your feedback. I found out what's going on. The mismatch come from the LSB-first vs MSB-first convention in the generator matrix. The code bellow compares the output when specifying the generator matix with MSB-first or LSB-first. It uses the argument added in the development version on GitHub. In the last pip version (v0.5.0), MSB-first is the only ordering available.

You can see on the outputs that MSB-first provides the results that you expected whereas LSB-first coresponds to the the other one. However, I'm surprised that you get [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1] without specifiying any polynomial_format argument since MSB-first is the default argument as well as the legacy behaviour in v0.5. Did you specified any polynomial_format argument?

import commpy.channelcoding.convcode as cc
import numpy as np

# Number of delay elements in the convolutional encoder
memory = np.array(3, ndmin=1)

# Generator matrix
g = np.array((0o17, 0o15), ndmin=2)

# Create trellis data structure
trellis_default = cc.Trellis(memory, g)
trellis_MSB = cc.Trellis(memory, g, polynomial_format='MSB')
trellis_LSB = cc.Trellis(memory, g, polynomial_format='LSB')

# Test the provided input
message = np.array([1, 0, 0, 1, 1, 0, 1, 0, 0, 0])
print('With default argument (same as in v0.5)', cc.conv_encode(message, trellis_default, 'cont'))
print('With MSB-first', cc.conv_encode(message, trellis_MSB, 'cont'))
print('With LSB-first', cc.conv_encode(message, trellis_LSB, 'cont'))

This code prints out:

With default argument (same as in v0.5) [1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1]
With MSB-first [1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1]
With LSB-first [1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1]

[ArmanRZ]

Hi Bastien, Oh, I see. The version I'm working with oddly has no argument polynomial_format when initializing cc.trellis. So it might have been a later modification that I had missed. I'm not sure about the source of the version I'm using. So it should solve it. Thanks.

Edit: The visualized trellis is still wrong (It won't change with LSB or MSB). While it makes sense for it to change accordingly as well. Please take a look at that too. Thanks.

Th correct trellis (for my scheme and what apparently MSB_first works with) (Figure 1):

What your trellis.visualize() returns: (Figure 2) A better version of Figure 2:

[BastienTr]

Hi @ArmanRZ, The treillis are changing accordingly even on your screenshots. See for instance the inputs number at the left of state 5. In the first plot, the input 1 leads to output 1 (0/1) and input 1 leads to output 2 (1/2). On the last figure, the relations are input 0 leads to output 0 (0/0) and input 3 leads to output 3 (1/3)

[ArmanRZ]

Bastien, The first figure is what it's supposed to look like. I generated it myself from the older version with my fix. Your current version always returns the second one, regardless of MSB or LSB. Sorry for the confusion.

[BastienTr]

In that case, you still have a issue in your CommPy install... You may want to clone it from github once more. I just ran the following code on my laptop and obtain the expected results.

import commpy.channelcoding.convcode as cc
import numpy as np

# Number of delay elements in the convolutional encoder
memory = np.array(3, ndmin=1)

# Generator matrix
g = np.array((0o17, 0o15), ndmin=2)

# Create trellis data structure
trellis_MSB = cc.Trellis(memory, g, polynomial_format='MSB')
trellis_LSB = cc.Trellis(memory, g, polynomial_format='LSB')

# Visualize Treillis
trellis_MSB.visualize()
trellis_LSB.visualize()

First figure Second figure

[ArmanRZ]

Gotcha. Will figure that out. Thanks for your time.

[BastienTr]

You welcome :)