libosmocore[master]: core/conv: implement optimized Viterbi decoder

[Tom Tsou]

Patch Set 5:

> Just rebased the change to the current master. I don't know why,
 > but with this decoder the coding_test fails.

The build failure can be fixed with the below change. In terms of decoder 'correctness' there is nothing wrong. The Viterbi ACS (add-compare-select) is based on a min() or max() function that becomes ambiguous under equivalency. The difference is whether one guesses 1 or 0 when path metrics are equal - statistically the outcomes are the same. The test case adds zeros to otherwise signed bits, which makes the code differences apparent.

diff --git a/src/viterbi_gen.c b/src/viterbi_gen.c
index 219b25b..7972c39 100644
--- a/src/viterbi_gen.c
+++ b/src/viterbi_gen.c
@@ -44,7 +44,7 @@ static void acs_butterfly(int state, int num_states,
        sum2 = state0 - metric;
        sum3 = state1 + metric;
 
-       if (sum0 > sum1) {
+       if (sum0 >= sum1) {
                *new_sum = sum0;
                *path = -1;
        } else {
@@ -52,7 +52,7 @@ static void acs_butterfly(int state, int num_states,
                *path = 0;
        }
 
-       if (sum2 > sum3) {
+       if (sum2 >= sum3) {
                *(new_sum + num_states / 2) = sum2;
                *(path + num_states / 2) = -1;
        } else {
--

Alternatively, matching in the other direction also brings both implementation outputs together. Neither selection is technically right or wrong.

diff --git a/src/conv.c b/src/conv.c
index 79b3a7c..8f007a4 100644
--- a/src/conv.c
+++ b/src/conv.c
@@ -405,7 +405,7 @@ osmo_conv_decode_scan(struct osmo_conv_decoder *decoder,
                                }
 
                                /* Is it survivor ? */
-                               if (ae_next[state] > nae) {
+                               if (ae_next[state] >= nae) {
                                        ae_next[state] = nae;
                                        state_history[(n_states * i) + state] = s;
                                }
--

-- 
To view, visit https://gerrit.osmocom.org/1337
To unsubscribe, visit https://gerrit.osmocom.org/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I74d355274b4176a7d924f91ef3c96912ce338fb2
Gerrit-PatchSet: 5
Gerrit-Project: libosmocore
Gerrit-Branch: master
Gerrit-Owner: Vadim Yanitskiy <axilirator at gmail.com>
Gerrit-Reviewer: Alexander Chemeris <Alexander.Chemeris at gmail.com>
Gerrit-Reviewer: Harald Welte <laforge at gnumonks.org>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: Max <msuraev at sysmocom.de>
Gerrit-Reviewer: Tom Tsou <tom at tsou.cc>
Gerrit-Reviewer: Vadim Yanitskiy <axilirator at gmail.com>
Gerrit-Reviewer: tnt <tnt at 246tNt.com>
Gerrit-HasComments: No