[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Discuss-gnuradio] "half-butterfly" viterbi decoding (VOLK)
From: |
rear1019 |
Subject: |
Re: [Discuss-gnuradio] "half-butterfly" viterbi decoding (VOLK) |
Date: |
Thu, 4 Apr 2019 13:03:39 +0200 |
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