core/conv: Add some generic code for convolutional coding/decoding

Far from perfect but suits our need thus far.

The viterbi with softbit input is quite cpu-intensive. Since
most received bursts are often mostly error free, you could
use a less cpu intensive algorithm (Fano ?) and with hard bit
input. Then only switch to viterbi soft bit input if the channel
is bad enough to justify it.

Soft output is not implemented as its usefulness for the block
coding is limited.

Signed-off-by: Sylvain Munaut <tnt@246tNt.com>

2 files changed, 102 insertions, 1 deletions

diff --git a/include/osmocom/core/Makefile.am b/include/osmocom/core/Makefile.am
index 6109f478..b21e0476 100644
--- a/include/osmocom/core/Makefile.am
+++ b/include/osmocom/core/Makefile.am
@@ -3,7 +3,7 @@ osmocore_HEADERS = signal.h linuxlist.h timer.h select.h msgb.h bits.h \
 		   gsmtap.h write_queue.h \
 		   logging.h rate_ctr.h gsmtap_util.h \
 		   plugin.h crc16.h panic.h process.h msgfile.h \
-		   backtrace.h
+		   backtrace.h conv.h
 
 if ENABLE_TALLOC
 osmocore_HEADERS += talloc.h
diff --git a/include/osmocom/core/conv.h b/include/osmocom/core/conv.h
new file mode 100644
index 00000000..af676eed
--- /dev/null
+++ b/include/osmocom/core/conv.h
@@ -0,0 +1,101 @@
+/*
+ * conv.h
+ *
+ * Copyright (C) 2011  Sylvain Munaut <tnt@246tNt.com>
+ *
+ * All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifndef __OSMO_CONV_H__
+#define __OSMO_CONV_H__
+
+#include <stdint.h>
+
+#include <osmocom/core/bits.h>
+
+struct osmo_conv_code {
+	int N;
+	int K;
+	int len;
+
+	const uint8_t (*next_output)[2];
+	const uint8_t (*next_state)[2];
+
+	const uint8_t *next_term_output;
+	const uint8_t *next_term_state;
+
+	const int *puncture;
+};
+
+
+/* Encoding */
+
+	/* Low level API */
+struct osmo_conv_encoder {
+	const struct osmo_conv_code *code;
+	int i_idx;	/* Next input bit index */
+	int p_idx;	/* Current puncture index */
+	uint8_t state;	/* Current state */
+};
+
+void osmo_conv_encode_init(struct osmo_conv_encoder *encoder,
+                           const struct osmo_conv_code *code);
+int  osmo_conv_encode_raw(struct osmo_conv_encoder *encoder,
+                          const ubit_t *input, ubit_t *output, int n);
+int  osmo_conv_encode_finish(struct osmo_conv_encoder *encoder, ubit_t *output);
+
+	/* All-in-one */
+int  osmo_conv_encode(const struct osmo_conv_code *code,
+                      const ubit_t *input, ubit_t *output);
+
+
+/* Decoding */
+
+	/* Low level API */
+struct osmo_conv_decoder {
+	const struct osmo_conv_code *code;
+
+	int n_states;
+
+	int len;		/* Max o_idx (excl. termination) */
+
+	int o_idx;		/* output index */
+	int p_idx;		/* puncture index */
+
+	unsigned int *ae;	/* accumulater error */
+	unsigned int *ae_next;	/* next accumulated error (tmp in scan) */
+	uint8_t *state_history;	/* state history [len][n_states] */
+};
+
+void osmo_conv_decode_init(struct osmo_conv_decoder *decoder,
+                           const struct osmo_conv_code *code, int len);
+void osmo_conv_decode_reset(struct osmo_conv_decoder *decoder);
+void osmo_conv_decode_deinit(struct osmo_conv_decoder *decoder);
+
+int osmo_conv_decode_scan(struct osmo_conv_decoder *decoder,
+                          const sbit_t *input, int n);
+int osmo_conv_decode_finish(struct osmo_conv_decoder *decoder,
+                            const sbit_t *input);
+int osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
+                                ubit_t *output, int has_finish);
+
+	/* All-in-one */
+int osmo_conv_decode(const struct osmo_conv_code *code,
+                     const sbit_t *input, ubit_t *output);
+
+
+#endif /* __OSMO_CONV_H__ */