Re: [Discuss-gnuradio] "half-butterfly" viterbi decoding (VOLK)

[Christoph Mayer]

> What exactly is the template parameter N? In viterbi2.hpp it must
> correspond to K (constraint length) from Phil Karn’s code.

Sorry, N is the constraint length K.

> The number of
> states is calculated as M = 2^(N-1) (line 17) and the main loop runs M/2
> times (“full-butterfly”, line 50).
>

> The other two implementations define M = 2^N; viterbi2_simple.hpp loops
> M times and viterbi2_simd.hpp M/8 times. Which value do you use for N
> with the new implementations?
>

Also here N is the constraint length.

The basic idea is to have SIMD versions of the algorithm in
viterbi2_simple.hpp. While viterbi2_simple.hpp loops M times (factor 2
more than the original code), when using SIMD this disadvantage is
more than offset, and in addition the SIMD kernels are simple.

> Regardless of the exact meaning of N it does not make sense to use it as
> a parameter. The number of states and thus the number of required loop
> runs is determined by the used polynomials. Those are fixed in your
> code (→ number of states is fixed as well).

In the end I would like to have decoders for different constraint
lengths (e.g., 7 and 9). Therefore it is a template parameter.

>
> > By the way, can someone point me to where branch metric overflows are
> > avoided in the VOLK kernels related to Viterbi decoding?
>
> See function “renormalize” in [1].
>
> [1] 
> https://github.com/gnuradio/volk/blob/master/kernels/volk/volk_8u_x4_conv_k7_r2_8u.h

Thanks! I was looking at the wrong file (volk_32f_8u_polarbutterfly_32f.h).

I see that renormalize is called after each full update of the path metrics.
There is a tradeoff between tracking the minimum (or maximum) value of
the path metrics and calling renormalize only when needed and to call
it after each full update of the path metrics.

Was the code in volk_8u_x4_conv_k7_r2_8u_avx2 and
volk_8u_x4_conv_k7_r2_8u_spiral generated by some other software?

Cheers

Christoph