This is merely a historical archive of years 2008-2021, before the migration to mailman3.
A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/gerrit-log@lists.osmocom.org/.
tnt gerrit-no-reply at lists.osmocom.orgtnt has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmocore/+/26657 ) Change subject: conv: Fix the traceback for tail biting codes ...................................................................... conv: Fix the traceback for tail biting codes When picking the end state, looking only at the path metric is highly suboptimal because in a tail biting code, we _know_ that whatever treillis path is correct, it must start and end at the same state. So we only consider path meeting that condition. We know any path that doesn't isn't the right one. We only fallback to only path metric if no path met that condition. Fixes #4508 Signed-off-by: Sylvain Munaut <tnt at 246tNt.com> Change-Id: I87e51d3880c0fe7bf3d6cd08fd46517a424a230c --- M include/osmocom/core/conv.h M src/conv.c M src/conv_acc.c 3 files changed, 93 insertions(+), 24 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/57/26657/1 diff --git a/include/osmocom/core/conv.h b/include/osmocom/core/conv.h index 1c14c3b..84ef0f8 100644 --- a/include/osmocom/core/conv.h +++ b/include/osmocom/core/conv.h @@ -124,6 +124,7 @@ const sbit_t *input, int n); int osmo_conv_decode_flush(struct osmo_conv_decoder *decoder, const sbit_t *input); +int osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder); int osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder, ubit_t *output, int has_flush, int end_state); diff --git a/src/conv.c b/src/conv.c index 0e07e1f..453e942 100644 --- a/src/conv.c +++ b/src/conv.c @@ -526,6 +526,68 @@ } int +osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder) +{ + const struct osmo_conv_code *code = decoder->code; + + int min_ae, min_state; + int s; + + /* If flushed, we _know_ the end state */ + if (code->term == CONV_TERM_FLUSH) + return 0; + + /* Search init */ + min_state = -1; + min_ae = MAX_AE; + + /* If tail biting, we search for the minimum path metric that + * gives a circular traceback (i.e. start_state == end_state */ + if (code->term == CONV_TERM_TAIL_BITING) + { + int t, n, i; + uint8_t *sh_ptr; + + for (s=0; s<decoder->n_states; s++) + { + /* Check if that state traces back to itself */ + n = decoder->o_idx; + sh_ptr = &decoder->state_history[decoder->n_states * (n-1)]; + t = s; + + for (i=n-1; i>=0; i--) { + t = sh_ptr[t]; + sh_ptr -= decoder->n_states; + } + + if (s != t) + continue; + + /* If it does, consider it */ + if (decoder->ae[s] < min_ae) { + min_ae = decoder->ae[s]; + min_state = s; + } + } + + if (min_ae < MAX_AE) + return min_state; + } + + /* Finally, just the lowest path metric */ + for (s=0; s<decoder->n_states; s++) + { + /* Is it smaller ? */ + if (decoder->ae[s] < min_ae) { + min_ae = decoder->ae[s]; + min_state = s; + } + } + + return min_state; +} + +int osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder, ubit_t *output, int has_flush, int end_state) { @@ -533,30 +595,19 @@ int min_ae; uint8_t min_state, cur_state; - int i, s, n; + int i, n; uint8_t *sh_ptr; /* End state ? */ - if (end_state < 0) { - /* Find state with least error */ - min_ae = MAX_AE; - min_state = 0xff; + if (end_state < 0) + end_state = osmo_conv_decode_get_best_end_state(decoder); - for (s=0; s<decoder->n_states; s++) - { - if (decoder->ae[s] < min_ae) { - min_ae = decoder->ae[s]; - min_state = s; - } - } + if (end_state < 0) + return -1; - if (min_state == 0xff) - return -1; - } else { - min_state = (uint8_t) end_state; - min_ae = decoder->ae[end_state]; - } + min_state = (uint8_t) end_state; + min_ae = decoder->ae[end_state]; /* Traceback */ cur_state = min_state; @@ -598,8 +649,8 @@ * * This is an all-in-one function, taking care of * \ref osmo_conv_decode_init, \ref osmo_conv_decode_scan, - * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_output and - * \ref osmo_conv_decode_deinit. + * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_best_end_state, + * \ref osmo_conv_decode_get_output and \ref osmo_conv_decode_deinit. */ int osmo_conv_decode(const struct osmo_conv_code *code, @@ -626,7 +677,7 @@ rv = osmo_conv_decode_get_output(&decoder, output, code->term == CONV_TERM_FLUSH, /* has_flush */ - code->term == CONV_TERM_FLUSH ? 0 : -1 /* end_state */ + -1 /* end_state */ ); osmo_conv_decode_deinit(&decoder); diff --git a/src/conv_acc.c b/src/conv_acc.c index a26ed3b..4bd3b07 100644 --- a/src/conv_acc.c +++ b/src/conv_acc.c @@ -483,10 +483,27 @@ */ static int traceback(struct vdecoder *dec, uint8_t *out, int term, int len) { - int i, sum, max = -1; - unsigned path, state = 0; + int i, j, sum, max = -1; + unsigned path, state = 0, state_scan; - if (term != CONV_TERM_FLUSH) { + if (term == CONV_TERM_TAIL_BITING) { + for (i = 0; i < dec->trellis.num_states; i++) { + state_scan = i; + for (j = len - 1; j >= 0; j--) { + path = dec->paths[j][state_scan] + 1; + state_scan = vstate_lshift(state_scan, dec->k, path); + } + if (state_scan != i) + continue; + sum = dec->trellis.sums[i]; + if (sum > max) { + max = sum; + state = i; + } + } + } + + if ((max < 0) && (term != CONV_TERM_FLUSH)) { for (i = 0; i < dec->trellis.num_states; i++) { sum = dec->trellis.sums[i]; if (sum > max) { -- To view, visit https://gerrit.osmocom.org/c/libosmocore/+/26657 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmocore Gerrit-Branch: master Gerrit-Change-Id: I87e51d3880c0fe7bf3d6cd08fd46517a424a230c Gerrit-Change-Number: 26657 Gerrit-PatchSet: 1 Gerrit-Owner: tnt <tnt at 246tNt.com> Gerrit-MessageType: newchange -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.osmocom.org/pipermail/gerrit-log/attachments/20211221/93c3797a/attachment.htm>