summaryrefslogtreecommitdiff
path: root/gnuradio-core/src/lib/viterbi
diff options
context:
space:
mode:
Diffstat (limited to 'gnuradio-core/src/lib/viterbi')
-rw-r--r--gnuradio-core/src/lib/viterbi/Makefile.am41
-rw-r--r--gnuradio-core/src/lib/viterbi/decode.cc88
-rw-r--r--gnuradio-core/src/lib/viterbi/encode.cc54
-rw-r--r--gnuradio-core/src/lib/viterbi/metrics.c119
-rw-r--r--gnuradio-core/src/lib/viterbi/tab.c57
-rw-r--r--gnuradio-core/src/lib/viterbi/viterbi.c355
-rw-r--r--gnuradio-core/src/lib/viterbi/viterbi.h49
7 files changed, 763 insertions, 0 deletions
diff --git a/gnuradio-core/src/lib/viterbi/Makefile.am b/gnuradio-core/src/lib/viterbi/Makefile.am
new file mode 100644
index 000000000..3eb1502ba
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/Makefile.am
@@ -0,0 +1,41 @@
+#
+# Copyright 2008 Free Software Foundation, Inc.
+#
+# GNU Radio 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 3, or (at your option)
+# any later version.
+#
+# GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+# the Free Software Foundation, Inc., 51 Franklin Street,
+# Boston, MA 02110-1301, USA.
+#
+
+INCLUDES = -Wall -Werror
+LIBS = -lm
+
+noinst_LTLIBRARIES = libviterbi.la
+
+libviterbi_la_SOURCES = \
+ metrics.c \
+ tab.c \
+ viterbi.c
+
+noinst_HEADERS = \
+ viterbi.h
+
+noinst_PROGRAMS = encode decode
+
+encode_SOURCES = encode.cc
+
+encode_LDADD = libviterbi.la
+
+decode_SOURCES = decode.cc
+
+decode_LDADD = libviterbi.la
diff --git a/gnuradio-core/src/lib/viterbi/decode.cc b/gnuradio-core/src/lib/viterbi/decode.cc
new file mode 100644
index 000000000..6580e4d66
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/decode.cc
@@ -0,0 +1,88 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+/*
+ * This is a minimal example demonstrating how to call the Viterbi decoder
+ * in continuous streaming mode. It accepts data on stdin and writes to
+ * stdout.
+ *
+ */
+
+extern "C" {
+#include "viterbi.h"
+}
+
+#include <cstdio>
+#include <cmath>
+
+#define MAXCHUNKSIZE 4096
+#define MAXENCSIZE MAXCHUNKSIZE*16
+
+int main()
+{
+ unsigned char data[MAXCHUNKSIZE];
+ signed char syms[MAXENCSIZE];
+ int count = 0;
+
+ // Initialize metric table
+ int mettab[2][256];
+ int amp = 100;
+ float RATE=0.5;
+ float ebn0 = 12.0;
+ float esn0 = RATE*pow(10.0, ebn0/10);
+ gen_met(mettab, amp, esn0, 0.0, 4);
+
+ // Initialize decoder state
+ struct viterbi_state state0[64];
+ struct viterbi_state state1[64];
+ unsigned char viterbi_in[16];
+ viterbi_chunks_init(state0);
+
+ while (!feof(stdin)) {
+ unsigned int n = fread(syms, 1, MAXENCSIZE, stdin);
+ unsigned char *out = data;
+
+ for (unsigned int i = 0; i < n; i++) {
+
+ // FIXME: This implements hard decoding by slicing the input stream
+ unsigned char sym = syms[i] > 0 ? -amp : amp;
+
+ // Write the symbol to the decoder input
+ viterbi_in[count % 4] = sym;
+
+ // Every four symbols, perform the butterfly2 operation
+ if ((count % 4) == 3) {
+ viterbi_butterfly2(viterbi_in, mettab, state0, state1);
+
+ // Every sixteen symbols, perform the readback operation
+ if ((count > 64) && (count % 16) == 11) {
+ viterbi_get_output(state0, out);
+ fwrite(out++, 1, 1, stdout);
+ }
+ }
+
+ count++;
+ }
+ }
+
+ return 0;
+}
diff --git a/gnuradio-core/src/lib/viterbi/encode.cc b/gnuradio-core/src/lib/viterbi/encode.cc
new file mode 100644
index 000000000..01acb3987
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/encode.cc
@@ -0,0 +1,54 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+/*
+ * This is a minimal example demonstrating how to call the ECC encoder
+ * in continuous streaming mode. It accepts data on stdin and writes to
+ * stdout.
+ *
+ * FIXME: This does not flush the final bits out of the encoder.
+ *
+ */
+
+extern "C" {
+#include "viterbi.h"
+}
+
+#include <cstdio>
+
+#define MAXCHUNKSIZE 4096
+#define MAXENCSIZE MAXCHUNKSIZE*16
+
+int main()
+{
+ unsigned char encoder_state = 0;
+ unsigned char data[MAXCHUNKSIZE];
+ unsigned char syms[MAXENCSIZE];
+
+ while (!feof(stdin)) {
+ unsigned int n = fread(data, 1, MAXCHUNKSIZE, stdin);
+ encoder_state = encode(syms, data, n, encoder_state);
+ fwrite(syms, 1, n*16, stdout);
+ }
+
+ return 0;
+}
diff --git a/gnuradio-core/src/lib/viterbi/metrics.c b/gnuradio-core/src/lib/viterbi/metrics.c
new file mode 100644
index 000000000..74f8ce09d
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/metrics.c
@@ -0,0 +1,119 @@
+/*
+ * Copyright 1995 Phil Karn, KA9Q
+ * Copyright 2008 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+/*
+ * Generate metric tables for a soft-decision convolutional decoder
+ * assuming gaussian noise on a PSK channel.
+ *
+ * Works from "first principles" by evaluating the normal probability
+ * function and then computing the log-likelihood function
+ * for every possible received symbol value
+ *
+ */
+
+/* Symbols are offset-binary, with 128 corresponding to an erased (no
+ * information) symbol
+ */
+#define OFFSET 128
+
+#include <stdlib.h>
+#include <math.h>
+
+/* Normal function integrated from -Inf to x. Range: 0-1 */
+#define normal(x) (0.5 + 0.5*erf((x)/M_SQRT2))
+
+/* Logarithm base 2 */
+#define log2(x) (log(x)*M_LOG2E)
+
+/* Generate log-likelihood metrics for 8-bit soft quantized channel
+ * assuming AWGN and BPSK
+ */
+void
+gen_met(int mettab[2][256], /* Metric table, [sent sym][rx symbol] */
+ int amp, /* Signal amplitude, units */
+ double esn0, /* Es/N0 ratio in dB */
+ double bias, /* Metric bias; 0 for viterbi, rate for sequential */
+ int scale) /* Scale factor */
+{
+ double noise;
+ int s,bit;
+ double metrics[2][256];
+ double p0,p1;
+
+ /* Es/N0 as power ratio */
+ esn0 = pow(10.,esn0/10);
+
+ noise = 0.5/esn0; /* only half the noise for BPSK */
+ noise = sqrt(noise); /* noise/signal Voltage ratio */
+
+ /* Zero is a special value, since this sample includes all
+ * lower samples that were clipped to this value, i.e., it
+ * takes the whole lower tail of the curve
+ */
+ p1 = normal(((0-OFFSET+0.5)/amp - 1)/noise); /* P(s|1) */
+
+ /* Prob of this value occurring for a 0-bit */ /* P(s|0) */
+ p0 = normal(((0-OFFSET+0.5)/amp + 1)/noise);
+ metrics[0][0] = log2(2*p0/(p1+p0)) - bias;
+ metrics[1][0] = log2(2*p1/(p1+p0)) - bias;
+
+ for(s=1;s<255;s++){
+ /* P(s|1), prob of receiving s given 1 transmitted */
+ p1 = normal(((s-OFFSET+0.5)/amp - 1)/noise) -
+ normal(((s-OFFSET-0.5)/amp - 1)/noise);
+
+ /* P(s|0), prob of receiving s given 0 transmitted */
+ p0 = normal(((s-OFFSET+0.5)/amp + 1)/noise) -
+ normal(((s-OFFSET-0.5)/amp + 1)/noise);
+
+#ifdef notdef
+ printf("P(%d|1) = %lg, P(%d|0) = %lg\n",s,p1,s,p0);
+#endif
+ metrics[0][s] = log2(2*p0/(p1+p0)) - bias;
+ metrics[1][s] = log2(2*p1/(p1+p0)) - bias;
+ }
+ /* 255 is also a special value */
+ /* P(s|1) */
+ p1 = 1 - normal(((255-OFFSET-0.5)/amp - 1)/noise);
+ /* P(s|0) */
+ p0 = 1 - normal(((255-OFFSET-0.5)/amp + 1)/noise);
+
+ metrics[0][255] = log2(2*p0/(p1+p0)) - bias;
+ metrics[1][255] = log2(2*p1/(p1+p0)) - bias;
+#ifdef notdef
+ /* The probability of a raw symbol error is the probability
+ * that a 1-bit would be received as a sample with value
+ * 0-128. This is the offset normal curve integrated from -Inf to 0.
+ */
+ printf("symbol Pe = %lg\n",normal(-1/noise));
+#endif
+ for(bit=0;bit<2;bit++){
+ for(s=0;s<256;s++){
+ /* Scale and round to nearest integer */
+ mettab[bit][s] = floor(metrics[bit][s] * scale + 0.5);
+#ifdef notdef
+ printf("metrics[%d][%d] = %lg, mettab = %d\n",
+ bit,s,metrics[bit][s],mettab[bit][s]);
+#endif
+ }
+ }
+}
diff --git a/gnuradio-core/src/lib/viterbi/tab.c b/gnuradio-core/src/lib/viterbi/tab.c
new file mode 100644
index 000000000..1133c6308
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/tab.c
@@ -0,0 +1,57 @@
+/*
+ * Copyright 1995 Phil Karn, KA9Q
+ * Copyright 2008 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+/* 8-bit parity lookup table, generated by partab.c */
+unsigned char Partab[] = {
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 0, 1, 1, 0, 1, 0, 0, 1,
+ 1, 0, 0, 1, 0, 1, 1, 0,
+};
diff --git a/gnuradio-core/src/lib/viterbi/viterbi.c b/gnuradio-core/src/lib/viterbi/viterbi.c
new file mode 100644
index 000000000..9f5c1e72a
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/viterbi.c
@@ -0,0 +1,355 @@
+/*
+ * Copyright 1995 Phil Karn, KA9Q
+ * Copyright 2008 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+/*
+ * Viterbi decoder for K=7 rate=1/2 convolutional code
+ * Some modifications from original Karn code by Matt Ettus
+ */
+
+#include "viterbi.h"
+
+/* The two generator polynomials for the NASA Standard K=7 code.
+ * Since these polynomials are known to be optimal for this constraint
+ * length there is not much point in changing them. But if you do, you
+ * will have to regenerate the BUTTERFLY macro calls in viterbi()
+ */
+#define POLYA 0x6d
+#define POLYB 0x4f
+
+/* The basic Viterbi decoder operation, called a "butterfly"
+ * operation because of the way it looks on a trellis diagram. Each
+ * butterfly involves an Add-Compare-Select (ACS) operation on the two nodes
+ * where the 0 and 1 paths from the current node merge at the next step of
+ * the trellis.
+ *
+ * The code polynomials are assumed to have 1's on both ends. Given a
+ * function encode_state() that returns the two symbols for a given
+ * encoder state in the low two bits, such a code will have the following
+ * identities for even 'n' < 64:
+ *
+ * encode_state(n) = encode_state(n+65)
+ * encode_state(n+1) = encode_state(n+64) = (3 ^ encode_state(n))
+ *
+ * Any convolutional code you would actually want to use will have
+ * these properties, so these assumptions aren't too limiting.
+ *
+ * Doing this as a macro lets the compiler evaluate at compile time the
+ * many expressions that depend on the loop index and encoder state and
+ * emit them as immediate arguments.
+ * This makes an enormous difference on register-starved machines such
+ * as the Intel x86 family where evaluating these expressions at runtime
+ * would spill over into memory.
+ */
+#define BUTTERFLY(i,sym) { \
+ int m0,m1;\
+\
+ /* ACS for 0 branch */\
+ m0 = state[i].metric + mets[sym]; /* 2*i */\
+ m1 = state[i+32].metric + mets[3^sym]; /* 2*i + 64 */\
+ if(m0 > m1){\
+ next[2*i].metric = m0;\
+ next[2*i].path = state[i].path << 1;\
+ } else {\
+ next[2*i].metric = m1;\
+ next[2*i].path = (state[i+32].path << 1)|1;\
+ }\
+ /* ACS for 1 branch */\
+ m0 = state[i].metric + mets[3^sym]; /* 2*i + 1 */\
+ m1 = state[i+32].metric + mets[sym]; /* 2*i + 65 */\
+ if(m0 > m1){\
+ next[2*i+1].metric = m0;\
+ next[2*i+1].path = state[i].path << 1;\
+ } else {\
+ next[2*i+1].metric = m1;\
+ next[2*i+1].path = (state[i+32].path << 1)|1;\
+ }\
+}
+
+extern unsigned char Partab[]; /* Parity lookup table */
+
+/* Convolutionally encode data into binary symbols */
+unsigned char
+encode(unsigned char *symbols,
+ unsigned char *data,
+ unsigned int nbytes,
+ unsigned char encstate)
+{
+ int i;
+
+ while(nbytes-- != 0){
+ for(i=7;i>=0;i--){
+ encstate = (encstate << 1) | ((*data >> i) & 1);
+ *symbols++ = Partab[encstate & POLYA];
+ *symbols++ = Partab[encstate & POLYB];
+ }
+ data++;
+ }
+
+ return encstate;
+}
+
+/* Viterbi decoder */
+int
+viterbi(unsigned long *metric, /* Final path metric (returned value) */
+ unsigned char *data, /* Decoded output data */
+ unsigned char *symbols, /* Raw deinterleaved input symbols */
+ unsigned int nbits, /* Number of output bits */
+ int mettab[2][256] /* Metric table, [sent sym][rx symbol] */
+ ){
+ unsigned int bitcnt = 0;
+ int mets[4];
+ long bestmetric;
+ int beststate,i;
+ struct viterbi_state state0[64],state1[64],*state,*next;
+
+ state = state0;
+ next = state1;
+
+ /* Initialize starting metrics to prefer 0 state */
+ state[0].metric = 0;
+ for(i=1;i<64;i++)
+ state[i].metric = -999999;
+ state[0].path = 0;
+
+ for(bitcnt = 0;bitcnt < nbits;bitcnt++){
+ /* Read input symbol pair and compute all possible branch
+ * metrics
+ */
+ mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
+ mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
+ mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
+ mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
+ symbols += 2;
+
+ /* These macro calls were generated by genbut.c */
+ BUTTERFLY(0,0);
+ BUTTERFLY(1,1);
+ BUTTERFLY(2,3);
+ BUTTERFLY(3,2);
+ BUTTERFLY(4,3);
+ BUTTERFLY(5,2);
+ BUTTERFLY(6,0);
+ BUTTERFLY(7,1);
+ BUTTERFLY(8,0);
+ BUTTERFLY(9,1);
+ BUTTERFLY(10,3);
+ BUTTERFLY(11,2);
+ BUTTERFLY(12,3);
+ BUTTERFLY(13,2);
+ BUTTERFLY(14,0);
+ BUTTERFLY(15,1);
+ BUTTERFLY(16,2);
+ BUTTERFLY(17,3);
+ BUTTERFLY(18,1);
+ BUTTERFLY(19,0);
+ BUTTERFLY(20,1);
+ BUTTERFLY(21,0);
+ BUTTERFLY(22,2);
+ BUTTERFLY(23,3);
+ BUTTERFLY(24,2);
+ BUTTERFLY(25,3);
+ BUTTERFLY(26,1);
+ BUTTERFLY(27,0);
+ BUTTERFLY(28,1);
+ BUTTERFLY(29,0);
+ BUTTERFLY(30,2);
+ BUTTERFLY(31,3);
+
+ /* Swap current and next states */
+ if(bitcnt & 1){
+ state = state0;
+ next = state1;
+ } else {
+ state = state1;
+ next = state0;
+ }
+ // ETTUS
+ //if(bitcnt > nbits-7){
+ /* In tail, poison non-zero nodes */
+ //for(i=1;i<64;i += 2)
+ // state[i].metric = -9999999;
+ //}
+ /* Produce output every 8 bits once path memory is full */
+ if((bitcnt % 8) == 5 && bitcnt > 32){
+ /* Find current best path */
+ bestmetric = state[0].metric;
+ beststate = 0;
+ for(i=1;i<64;i++){
+ if(state[i].metric > bestmetric){
+ bestmetric = state[i].metric;
+ beststate = i;
+ }
+ }
+#ifdef notdef
+ printf("metrics[%d] = %d state = %lx\n",beststate,
+ state[beststate].metric,state[beststate].path);
+#endif
+ *data++ = state[beststate].path >> 24;
+ }
+
+ }
+ /* Output remaining bits from 0 state */
+ // ETTUS Find best state instead
+ bestmetric = state[0].metric;
+ beststate = 0;
+ for(i=1;i<64;i++){
+ if(state[i].metric > bestmetric){
+ bestmetric = state[i].metric;
+ beststate = i;
+ }
+ }
+ if((i = bitcnt % 8) != 6)
+ state[beststate].path <<= 6-i;
+
+ *data++ = state[beststate].path >> 24;
+ *data++ = state[beststate].path >> 16;
+ *data++ = state[beststate].path >> 8;
+ *data = state[beststate].path;
+ //printf ("BS = %d\tBSM = %d\tM0 = %d\n",beststate,state[beststate].metric,state[0].metric);
+ *metric = state[beststate].metric;
+ return 0;
+}
+
+
+void
+viterbi_chunks_init(struct viterbi_state* state) {
+ // Initialize starting metrics to prefer 0 state
+ int i;
+ state[0].metric = 0;
+ state[0].path = 0;
+ for(i=1;i<64;i++)
+ state[i].metric = -999999;
+}
+
+void
+viterbi_butterfly8(unsigned char *symbols, int mettab[2][256], struct viterbi_state *state0, struct viterbi_state *state1)
+{
+ unsigned int bitcnt;
+ int mets[4];
+
+ struct viterbi_state *state, *next;
+ state = state0;
+ next = state1;
+ // Operate on 16 symbols (8 bits) at a time
+ for(bitcnt = 0;bitcnt < 8;bitcnt++){
+ // Read input symbol pair and compute all possible branch metrics
+ mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
+ mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
+ mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
+ mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
+ symbols += 2;
+
+ // These macro calls were generated by genbut.c
+ BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2);
+ BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1);
+ BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2);
+ BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1);
+ BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0);
+ BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3);
+ BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0);
+ BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3);
+
+ // Swap current and next states
+ if(bitcnt & 1){
+ state = state0;
+ next = state1;
+ } else {
+ state = state1;
+ next = state0;
+ }
+ }
+}
+
+void
+viterbi_butterfly2(unsigned char *symbols, int mettab[2][256], struct viterbi_state *state0, struct viterbi_state *state1)
+{
+ //unsigned int bitcnt;
+ int mets[4];
+
+ struct viterbi_state *state, *next;
+ state = state0;
+ next = state1;
+ // Operate on 4 symbols (2 bits) at a time
+
+ // Read input symbol pair and compute all possible branch metrics
+ mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
+ mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
+ mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
+ mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
+
+ // These macro calls were generated by genbut.c
+ BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2);
+ BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1);
+ BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2);
+ BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1);
+ BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0);
+ BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3);
+ BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0);
+ BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3);
+
+ state = state1;
+ next = state0;
+
+ // Read input symbol pair and compute all possible branch metrics
+ mets[0] = mettab[0][symbols[2]] + mettab[0][symbols[3]];
+ mets[1] = mettab[0][symbols[2]] + mettab[1][symbols[3]];
+ mets[2] = mettab[1][symbols[2]] + mettab[0][symbols[3]];
+ mets[3] = mettab[1][symbols[2]] + mettab[1][symbols[3]];
+
+ // These macro calls were generated by genbut.c
+ BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2);
+ BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1);
+ BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2);
+ BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1);
+ BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0);
+ BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3);
+ BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0);
+ BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3);
+}
+
+unsigned char
+viterbi_get_output(struct viterbi_state *state, unsigned char *outbuf) {
+ // Produce output every 8 bits once path memory is full
+ // if((bitcnt % 8) == 5 && bitcnt > 32) {
+
+ // Find current best path
+ unsigned int i,beststate;
+ int bestmetric;
+
+ bestmetric = state[0].metric;
+ beststate = 0;
+ for(i=1;i<64;i++)
+ if(state[i].metric > bestmetric) {
+ bestmetric = state[i].metric;
+ beststate = i;
+ }
+ *outbuf = state[beststate].path >> 24;
+ return bestmetric;
+}
+
+
+//printf ("BS = %d\tBSM = %d\tM0 = %d\n",beststate,state[beststate].metric,state[0].metric);
+// In tail, poison non-zero nodes
+//if(bits_out > packet_size-7)
+// for(i=1;i<64;i += 2)
+// state[i].metric = -9999999;
+
diff --git a/gnuradio-core/src/lib/viterbi/viterbi.h b/gnuradio-core/src/lib/viterbi/viterbi.h
new file mode 100644
index 000000000..155b0d93a
--- /dev/null
+++ b/gnuradio-core/src/lib/viterbi/viterbi.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2008 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio 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 GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+/* The path memory for each state is 32 bits. This is slightly shorter
+ * than we'd like for K=7, especially since we chain back every 8 bits.
+ * But it fits so nicely into a 32-bit machine word...
+ */
+struct viterbi_state {
+ unsigned long path; /* Decoded path to this state */
+ long metric; /* Cumulative metric to this state */
+};
+
+int gen_met(int mettab[2][256], /* Metric table */
+ int amp, /* Signal amplitude */
+ double esn0, /* Es/N0 ratio in dB */
+ double bias, /* Metric bias */
+ int scale); /* Scale factor */
+
+unsigned char
+encode(unsigned char *symbols, unsigned char *data,
+ unsigned int nbytes,unsigned char encstate);
+
+void
+viterbi_chunks_init(struct viterbi_state* state);
+
+void
+viterbi_butterfly2(unsigned char *symbols, int mettab[2][256],
+ struct viterbi_state *state0, struct viterbi_state *state1);
+
+unsigned char
+viterbi_get_output(struct viterbi_state *state, unsigned char *outbuf);
generated by cgit (git 2.34.1) at 2024-12-21 05:08:01 +0000