<p>tnt has uploaded this change for <strong>review</strong>.</p><p><a href="https://gerrit.osmocom.org/c/libosmocore/+/26657">View Change</a></p><pre style="font-family: monospace,monospace; white-space: pre-wrap;">conv: Fix the traceback for tail biting codes<br><br>When picking the end state, looking only at the path metric<br>is highly suboptimal because in a tail biting code, we _know_ that<br>whatever treillis path is correct, it must start and end at the same<br>state. So we only consider path meeting that condition. We know any<br>path that doesn't isn't the right one. We only fallback to only<br>path metric if no path met that condition.<br><br>Fixes #4508<br><br>Signed-off-by: Sylvain Munaut <tnt@246tNt.com><br>Change-Id: I87e51d3880c0fe7bf3d6cd08fd46517a424a230c<br>---<br>M include/osmocom/core/conv.h<br>M src/conv.c<br>M src/conv_acc.c<br>3 files changed, 93 insertions(+), 24 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;">git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/57/26657/1</pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;"><span>diff --git a/include/osmocom/core/conv.h b/include/osmocom/core/conv.h</span><br><span>index 1c14c3b..84ef0f8 100644</span><br><span>--- a/include/osmocom/core/conv.h</span><br><span>+++ b/include/osmocom/core/conv.h</span><br><span>@@ -124,6 +124,7 @@</span><br><span> const sbit_t *input, int n);</span><br><span> int osmo_conv_decode_flush(struct osmo_conv_decoder *decoder,</span><br><span> const sbit_t *input);</span><br><span style="color: hsl(120, 100%, 40%);">+int osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder);</span><br><span> int osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,</span><br><span> ubit_t *output, int has_flush, int end_state);</span><br><span> </span><br><span>diff --git a/src/conv.c b/src/conv.c</span><br><span>index 0e07e1f..453e942 100644</span><br><span>--- a/src/conv.c</span><br><span>+++ b/src/conv.c</span><br><span>@@ -526,6 +526,68 @@</span><br><span> }</span><br><span> </span><br><span> int</span><br><span style="color: hsl(120, 100%, 40%);">+osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ const struct osmo_conv_code *code = decoder->code;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ int min_ae, min_state;</span><br><span style="color: hsl(120, 100%, 40%);">+ int s;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ /* If flushed, we _know_ the end state */</span><br><span style="color: hsl(120, 100%, 40%);">+ if (code->term == CONV_TERM_FLUSH)</span><br><span style="color: hsl(120, 100%, 40%);">+ return 0;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ /* Search init */</span><br><span style="color: hsl(120, 100%, 40%);">+ min_state = -1;</span><br><span style="color: hsl(120, 100%, 40%);">+ min_ae = MAX_AE;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ /* If tail biting, we search for the minimum path metric that</span><br><span style="color: hsl(120, 100%, 40%);">+ * gives a circular traceback (i.e. start_state == end_state */</span><br><span style="color: hsl(120, 100%, 40%);">+ if (code->term == CONV_TERM_TAIL_BITING)</span><br><span style="color: hsl(120, 100%, 40%);">+ {</span><br><span style="color: hsl(120, 100%, 40%);">+ int t, n, i;</span><br><span style="color: hsl(120, 100%, 40%);">+ uint8_t *sh_ptr;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ for (s=0; s<decoder->n_states; s++)</span><br><span style="color: hsl(120, 100%, 40%);">+ {</span><br><span style="color: hsl(120, 100%, 40%);">+ /* Check if that state traces back to itself */</span><br><span style="color: hsl(120, 100%, 40%);">+ n = decoder->o_idx;</span><br><span style="color: hsl(120, 100%, 40%);">+ sh_ptr = &decoder->state_history[decoder->n_states * (n-1)];</span><br><span style="color: hsl(120, 100%, 40%);">+ t = s;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ for (i=n-1; i>=0; i--) {</span><br><span style="color: hsl(120, 100%, 40%);">+ t = sh_ptr[t];</span><br><span style="color: hsl(120, 100%, 40%);">+ sh_ptr -= decoder->n_states;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if (s != t)</span><br><span style="color: hsl(120, 100%, 40%);">+ continue;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ /* If it does, consider it */</span><br><span style="color: hsl(120, 100%, 40%);">+ if (decoder->ae[s] < min_ae) {</span><br><span style="color: hsl(120, 100%, 40%);">+ min_ae = decoder->ae[s];</span><br><span style="color: hsl(120, 100%, 40%);">+ min_state = s;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if (min_ae < MAX_AE)</span><br><span style="color: hsl(120, 100%, 40%);">+ return min_state;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ /* Finally, just the lowest path metric */</span><br><span style="color: hsl(120, 100%, 40%);">+ for (s=0; s<decoder->n_states; s++)</span><br><span style="color: hsl(120, 100%, 40%);">+ {</span><br><span style="color: hsl(120, 100%, 40%);">+ /* Is it smaller ? */</span><br><span style="color: hsl(120, 100%, 40%);">+ if (decoder->ae[s] < min_ae) {</span><br><span style="color: hsl(120, 100%, 40%);">+ min_ae = decoder->ae[s];</span><br><span style="color: hsl(120, 100%, 40%);">+ min_state = s;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ return min_state;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+int</span><br><span> osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,</span><br><span> ubit_t *output, int has_flush, int end_state)</span><br><span> {</span><br><span>@@ -533,30 +595,19 @@</span><br><span> </span><br><span> int min_ae;</span><br><span> uint8_t min_state, cur_state;</span><br><span style="color: hsl(0, 100%, 40%);">- int i, s, n;</span><br><span style="color: hsl(120, 100%, 40%);">+ int i, n;</span><br><span> </span><br><span> uint8_t *sh_ptr;</span><br><span> </span><br><span> /* End state ? */</span><br><span style="color: hsl(0, 100%, 40%);">- if (end_state < 0) {</span><br><span style="color: hsl(0, 100%, 40%);">- /* Find state with least error */</span><br><span style="color: hsl(0, 100%, 40%);">- min_ae = MAX_AE;</span><br><span style="color: hsl(0, 100%, 40%);">- min_state = 0xff;</span><br><span style="color: hsl(120, 100%, 40%);">+ if (end_state < 0)</span><br><span style="color: hsl(120, 100%, 40%);">+ end_state = osmo_conv_decode_get_best_end_state(decoder);</span><br><span> </span><br><span style="color: hsl(0, 100%, 40%);">- for (s=0; s<decoder->n_states; s++)</span><br><span style="color: hsl(0, 100%, 40%);">- {</span><br><span style="color: hsl(0, 100%, 40%);">- if (decoder->ae[s] < min_ae) {</span><br><span style="color: hsl(0, 100%, 40%);">- min_ae = decoder->ae[s];</span><br><span style="color: hsl(0, 100%, 40%);">- min_state = s;</span><br><span style="color: hsl(0, 100%, 40%);">- }</span><br><span style="color: hsl(0, 100%, 40%);">- }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (end_state < 0)</span><br><span style="color: hsl(120, 100%, 40%);">+ return -1;</span><br><span> </span><br><span style="color: hsl(0, 100%, 40%);">- if (min_state == 0xff)</span><br><span style="color: hsl(0, 100%, 40%);">- return -1;</span><br><span style="color: hsl(0, 100%, 40%);">- } else {</span><br><span style="color: hsl(0, 100%, 40%);">- min_state = (uint8_t) end_state;</span><br><span style="color: hsl(0, 100%, 40%);">- min_ae = decoder->ae[end_state];</span><br><span style="color: hsl(0, 100%, 40%);">- }</span><br><span style="color: hsl(120, 100%, 40%);">+ min_state = (uint8_t) end_state;</span><br><span style="color: hsl(120, 100%, 40%);">+ min_ae = decoder->ae[end_state];</span><br><span> </span><br><span> /* Traceback */</span><br><span> cur_state = min_state;</span><br><span>@@ -598,8 +649,8 @@</span><br><span> *</span><br><span> * This is an all-in-one function, taking care of</span><br><span> * \ref osmo_conv_decode_init, \ref osmo_conv_decode_scan,</span><br><span style="color: hsl(0, 100%, 40%);">- * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_output and</span><br><span style="color: hsl(0, 100%, 40%);">- * \ref osmo_conv_decode_deinit.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_best_end_state,</span><br><span style="color: hsl(120, 100%, 40%);">+ * \ref osmo_conv_decode_get_output and \ref osmo_conv_decode_deinit.</span><br><span> */</span><br><span> int</span><br><span> osmo_conv_decode(const struct osmo_conv_code *code,</span><br><span>@@ -626,7 +677,7 @@</span><br><span> </span><br><span> rv = osmo_conv_decode_get_output(&decoder, output,</span><br><span> code->term == CONV_TERM_FLUSH, /* has_flush */</span><br><span style="color: hsl(0, 100%, 40%);">- code->term == CONV_TERM_FLUSH ? 0 : -1 /* end_state */</span><br><span style="color: hsl(120, 100%, 40%);">+ -1 /* end_state */</span><br><span> );</span><br><span> </span><br><span> osmo_conv_decode_deinit(&decoder);</span><br><span>diff --git a/src/conv_acc.c b/src/conv_acc.c</span><br><span>index a26ed3b..4bd3b07 100644</span><br><span>--- a/src/conv_acc.c</span><br><span>+++ b/src/conv_acc.c</span><br><span>@@ -483,10 +483,27 @@</span><br><span> */</span><br><span> static int traceback(struct vdecoder *dec, uint8_t *out, int term, int len)</span><br><span> {</span><br><span style="color: hsl(0, 100%, 40%);">- int i, sum, max = -1;</span><br><span style="color: hsl(0, 100%, 40%);">- unsigned path, state = 0;</span><br><span style="color: hsl(120, 100%, 40%);">+ int i, j, sum, max = -1;</span><br><span style="color: hsl(120, 100%, 40%);">+ unsigned path, state = 0, state_scan;</span><br><span> </span><br><span style="color: hsl(0, 100%, 40%);">- if (term != CONV_TERM_FLUSH) {</span><br><span style="color: hsl(120, 100%, 40%);">+ if (term == CONV_TERM_TAIL_BITING) {</span><br><span style="color: hsl(120, 100%, 40%);">+ for (i = 0; i < dec->trellis.num_states; i++) {</span><br><span style="color: hsl(120, 100%, 40%);">+ state_scan = i;</span><br><span style="color: hsl(120, 100%, 40%);">+ for (j = len - 1; j >= 0; j--) {</span><br><span style="color: hsl(120, 100%, 40%);">+ path = dec->paths[j][state_scan] + 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ state_scan = vstate_lshift(state_scan, dec->k, path);</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (state_scan != i)</span><br><span style="color: hsl(120, 100%, 40%);">+ continue;</span><br><span style="color: hsl(120, 100%, 40%);">+ sum = dec->trellis.sums[i];</span><br><span style="color: hsl(120, 100%, 40%);">+ if (sum > max) {</span><br><span style="color: hsl(120, 100%, 40%);">+ max = sum;</span><br><span style="color: hsl(120, 100%, 40%);">+ state = i;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if ((max < 0) && (term != CONV_TERM_FLUSH)) {</span><br><span> for (i = 0; i < dec->trellis.num_states; i++) {</span><br><span> sum = dec->trellis.sums[i];</span><br><span> if (sum > max) {</span><br><span></span><br></pre><p>To view, visit <a href="https://gerrit.osmocom.org/c/libosmocore/+/26657">change 26657</a>. To unsubscribe, or for help writing mail filters, visit <a href="https://gerrit.osmocom.org/settings">settings</a>.</p><div itemscope itemtype="http://schema.org/EmailMessage"><div itemscope itemprop="action" itemtype="http://schema.org/ViewAction"><link itemprop="url" href="https://gerrit.osmocom.org/c/libosmocore/+/26657"/><meta itemprop="name" content="View Change"/></div></div>
<div style="display:none"> Gerrit-Project: libosmocore </div>
<div style="display:none"> Gerrit-Branch: master </div>
<div style="display:none"> Gerrit-Change-Id: I87e51d3880c0fe7bf3d6cd08fd46517a424a230c </div>
<div style="display:none"> Gerrit-Change-Number: 26657 </div>
<div style="display:none"> Gerrit-PatchSet: 1 </div>
<div style="display:none"> Gerrit-Owner: tnt <tnt@246tNt.com> </div>
<div style="display:none"> Gerrit-MessageType: newchange </div>