diff --git a/src/conv.c b/src/conv.c
index 0e07e1f..4696a44 100644
--- a/src/conv.c
+++ b/src/conv.c
@@ -526,38 +526,87 @@
 }
 
 int
-osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
-                            ubit_t *output, int has_flush, int end_state)
+osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder)
 {
 	const struct osmo_conv_code *code = decoder->code;
 
-	int min_ae;
-	uint8_t min_state, cur_state;
-	int i, s, n;
+	int min_ae, min_state;
+	int s;
 
-	uint8_t *sh_ptr;
+	/* If flushed, we _know_ the end state */
+	if (code->term == CONV_TERM_FLUSH)
+		return 0;
 
-	/* End state ? */
-	if (end_state < 0) {
-		/* Find state with least error */
-		min_ae = MAX_AE;
-		min_state = 0xff;
+	/* 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_state == 0xff)
-			return -1;
-	} else {
-		min_state = (uint8_t) end_state;
-		min_ae = decoder->ae[end_state];
+		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)
+{
+	const struct osmo_conv_code *code = decoder->code;
+
+	int min_ae;
+	uint8_t min_state, cur_state;
+	int i, n;
+
+	uint8_t *sh_ptr;
+
+	/* End state ? */
+	if (end_state < 0)
+		end_state = osmo_conv_decode_get_best_end_state(decoder);
+
+	if (end_state < 0)
+		return -1;
+
+	min_state = (uint8_t) end_state;
+	min_ae = decoder->ae[end_state];
+
 	/* Traceback */
 	cur_state = min_state;
 
@@ -598,8 +647,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 +675,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) {