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

[rear1019]

On Wed, 03 Apr 2019 at 12:57:25 +0200, Christoph Mayer wrote:
> a while ago I wrote a soft-decision Viterbi decoder based on Phil Karn's code:
> https://github.com/hcab14/signal-analysis/blob/master/include/viterbi2.hpp
>
> and then realized that there is a version of Viterbi decoding using
> "half bufferflys": At the cost of looping over two times more states,
> it is more simple, i.e., there is one operation on each state and
> these operations are all independent
> https://github.com/hcab14/signal-analysis/blob/master/include/viterbi2_simple.hpp
>
> Therefore implementing such a half-butterfly Viterbi decoder using
> SIMD is quite easy, see
> https://github.com/hcab14/signal-analysis/blob/master/include/viterbi2_simd.hpp
> for an example using AARCH64 NEON SIMD.

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

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

> 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