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

[Christoph Mayer]

Hi all,

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.

The SIMD version processes 8 states in parallel and is 7.5 times
faster than the half-butterfly non-SIMD version and 2.8 times faster
than the original version

I wonder if this idea has been considered before.

It would also be good
* to add Viterbi decoders for constraint lengths >7 and with more than
two polynomials to VOLK/GNURadio
* to have information about the maximum path metric for quality monitoring

By the way, can someone point me to where branch metric overflows are
avoided in the VOLK kernels related to Viterbi decoding?

Any comments/suggestions are welcome.

Best regards
Christoph