Merge branch '8psk' of github.com:trondeau/gnuradio into 8psk

Conflicts:
	gr-digital/lib/digital_costas_loop_cc.cc
	gr-digital/python/qa_costas_loop_cc.py

10 files changed, 369 insertions, 43 deletions

diff --git a/gr-trellis/src/lib/Makefile.am b/gr-trellis/src/lib/Makefile.am
index 08e75291a..d6926f2a0 100644
--- a/gr-trellis/src/lib/Makefile.am
+++ b/gr-trellis/src/lib/Makefile.am
@@ -66,12 +66,12 @@ grinclude_HEADERS =			\
         quicksort_index.h		\
         base.h				\
         interleaver.h			\
-        trellis_metric_type.h		\
         trellis_calc_metric.h		\
         trellis_permutation.h		\
         trellis_siso_type.h		\
 	trellis_siso_f.h		\
 	trellis_siso_combined_f.h	\
+	trellis_constellation_metrics_cf.h \
 	$(GENERATED_H)
 
 lib_LTLIBRARIES = libgnuradio-trellis.la
@@ -85,6 +85,7 @@ libgnuradio_trellis_la_SOURCES = 	\
         trellis_permutation.cc		\
 	trellis_siso_f.cc		\
 	trellis_siso_combined_f.cc	\
+	trellis_constellation_metrics_cf.cc \
 	$(GENERATED_CC)
 
 libgnuradio_trellis_la_LIBADD =	\
@@ -119,6 +120,7 @@ trellis_swiginclude_headers = 		\
 	trellis_permutation.i		\
 	trellis_siso_f.i		\
 	trellis_siso_combined_f.i	\
+	trellis_constellation_metrics_cf.i \
 	trellis_generated.i
 
 # Do creation and inclusion of other Makefiles last
diff --git a/gr-trellis/src/lib/Makefile.swig.gen b/gr-trellis/src/lib/Makefile.swig.gen
index 784c146cf..2d014b946 100644
--- a/gr-trellis/src/lib/Makefile.swig.gen
+++ b/gr-trellis/src/lib/Makefile.swig.gen
@@ -105,7 +105,7 @@ _trellis_la_CXXFLAGS =			\
 	$(trellis_la_swig_cxxflags)
 
 python/trellis.cc: trellis.py
-trellis.py: trellis.i
+trellis.py: trellis.i 
 
 # Include the python dependencies for this file
 -include python/trellis.d
diff --git a/gr-trellis/src/lib/fsm.cc b/gr-trellis/src/lib/fsm.cc
index 5950b56b9..889a3918b 100644
--- a/gr-trellis/src/lib/fsm.cc
+++ b/gr-trellis/src/lib/fsm.cc
@@ -417,7 +417,7 @@ void fsm::generate_TM()
       done = find_es(s);
       attempts ++;
     }
-    if (done == false) {
+    if (done == false and d_S > 1) {
       //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be disconnected\n");
       printf("fsm::generate_TM(): FSM appears to be disconnected\n");
       printf("state %d cannot be reached from all other states\n",s);
diff --git a/gr-trellis/src/lib/fsm.h b/gr-trellis/src/lib/fsm.h
index 0a90b2cd3..8bae91754 100644
--- a/gr-trellis/src/lib/fsm.h
+++ b/gr-trellis/src/lib/fsm.h
@@ -1,6 +1,6 @@
 /* -*- c++ -*- */
 /*
- * Copyright 2002 Free Software Foundation, Inc.
+ * Copyright 2002,2011 Free Software Foundation, Inc.
  *
  * This file is part of GNU Radio
  *
@@ -27,31 +27,114 @@
 #include <iosfwd>
 
 /*!
- * \brief  FSM class
+ * \brief  Finite State Machine Specification class.
+ *
+ * An instance of this class represents a finite state machine specification (FSMS)
+ * rather than the FSM itself.  It particular the state of the FSM
+ * is not stored within an instance of this class.
  */
 class fsm {
 private:
+  // Input alphabet cardinality.
   int d_I;
+  // Number of states.
   int d_S;
+  // Output alphabet cardinality.
   int d_O;
+  // NS means Next State.
+  // next_state = d_NS[current_state * d_I + input_symbol]
   std::vector<int> d_NS;
+  // OS means Output Symbol.
+  // output_symbol = d_OS[current_state * d_I + input_symbol]          
   std::vector<int> d_OS;
+  // PS means Previous State.
   std::vector< std::vector<int> > d_PS;
+  // PI means Previous Input Symbol.
+  // d_PS[current_state][k] and d_PI[current_state][k], is a pair of the form
+  // (previous_state, previous_input_symbol) that could have produced the
+  // current state.
   std::vector< std::vector<int> > d_PI;
-  std::vector<int> d_TMi;
+  // TM means Termination matrix.
+  // d_TMl[s*d_S+es] is the shortest number of steps to get from state s to
+  // state es.
   std::vector<int> d_TMl;
+  // d_TMi[s*d_S+es] is the input symbol required to set off on the shortest
+  // path from state s to es.
+  std::vector<int> d_TMi;
   void generate_PS_PI ();
   void generate_TM ();
   bool find_es(int es);
 public:
+ /*!
+   * \brief Constructor to create an uninitialized FSMS.
+   */
   fsm();
+ /*!
+   * \brief Constructor to copy an FSMS.
+   */
   fsm(const fsm &FSM);
+ /*!
+   * \brief Constructor to to create an FSMS.
+   *
+   * \param I	        The number of possible input symbols.
+   * \param S           The number of possible FSM states.
+   * \param O           The number of possible output symbols.
+   * \param NS          A mapping from (current state, input symbol) to next state.
+   *                    next_state = NS[current_state * I + input_symbol]
+   * \param OS          A mapping from (current state, input symbol) to output symbol.
+   *                    output_symbol = OS[current_state * I + input_symbol]          
+   *
+   */
   fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS);
+ /*!
+   * \brief Constructor to create an FSMS from file contents.
+   *
+   * \param name        filename
+   *
+   */
   fsm(const char *name);
+ /*!
+   * \brief Creates an FSMS from the generator matrix of a (n, k) binary convolutional code.
+   *
+   * \param k      ???
+   * \param n      ???
+   * \param G      ???
+   *
+   */
   fsm(int k, int n, const std::vector<int> &G);
+  /*!
+   * \brief Creates an FSMS describing ISI.
+   *
+   * \param mod_size    modulation size
+   * \param ch_lenth    channel length
+   *
+   */
   fsm(int mod_size, int ch_length);
+  /*!
+   * \brief Creates an FSMS describing the trellis for a CPM.
+   *
+   * \param P    ???? h=K/P (relatively prime)
+   * \param M    alphabet size
+   * \param L    pulse duration
+   *
+   * This FSM is based on the paper by B. Rimoldi
+   * "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
+   * See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
+   */
   fsm(int P, int M, int L);
+  /*!
+   * \brief Creates an FSMS describing the joint trellis of two FSMs.
+   *
+   * \param fsm1  first FSMS
+   * \param fsm2  second FSMS
+   */
   fsm(const fsm &FSM1, const fsm &FSM2);
+  /*!
+   * \brief Creates an FSMS representing n stages through the originial FSM (AKA radix-n FSM).
+   *
+   * \param original FSMS
+   * \param n        Number of stages.
+   */
   fsm(const fsm &FSM, int n);
   int I () const { return d_I; }
   int S () const { return d_S; }
@@ -62,7 +145,20 @@ public:
   const std::vector< std::vector<int> > & PI () const { return d_PI; }
   const std::vector<int> & TMi () const { return d_TMi; }
   const std::vector<int> & TMl () const { return d_TMl; }
+  /*!
+   * \brief Creates an svg image of the trellis representation.
+   *
+   * \param filename         filename
+   * \param number_stages    ????
+   *
+   */  
   void write_trellis_svg(std::string filename ,int number_stages);
+  /*!
+   * \brief Write the FSMS to a file.
+   *
+   * \param filename   filename
+   *
+   */
   void write_fsm_txt(std::string filename);
 };
 
diff --git a/gr-trellis/src/lib/trellis.i b/gr-trellis/src/lib/trellis.i
index d035cea54..fe74c8d9f 100644
--- a/gr-trellis/src/lib/trellis.i
+++ b/gr-trellis/src/lib/trellis.i
@@ -28,8 +28,11 @@
 #include "trellis_permutation.h"
 #include "trellis_siso_f.h"
 #include "trellis_siso_combined_f.h"
+#include "trellis_constellation_metrics_cf.h"
+#include "gr_constellation.h"
 %}
 
+
 // ----------------------------------------------------------------
 
 %include "fsm.i"
@@ -38,12 +41,19 @@
 %include "trellis_siso_f.i"
 %include "trellis_siso_combined_f.i"
 
-%include "trellis_metric_type.h"
 %include "trellis_siso_type.h"
 
+%include "trellis_constellation_metrics_cf.i"
 
 %include "trellis_generated.i"
 
+%import "gr_metric_type.h"
+%import "gr_constellation.i"
+
+%pythoncode %{
+  from gnuradio.gr import TRELLIS_EUCLIDEAN, TRELLIS_HARD_SYMBOL, TRELLIS_HARD_BIT
+  %}
+
 #if SWIGGUILE
 %scheme %{
 (load-extension-global "libguile-gnuradio-trellis" "scm_init_gnuradio_trellis_module")
diff --git a/gr-trellis/src/lib/trellis_calc_metric.h b/gr-trellis/src/lib/trellis_calc_metric.h
index fabf4e145..b9eacb086 100644
--- a/gr-trellis/src/lib/trellis_calc_metric.h
+++ b/gr-trellis/src/lib/trellis_calc_metric.h
@@ -25,7 +25,7 @@
 
 #include <vector>
 #include <gr_complex.h>
-#include <trellis_metric_type.h>
+#include <gr_metric_type.h>
 
 
 template <class T> 
diff --git a/gr-trellis/src/lib/trellis_constellation_metrics_cf.cc b/gr-trellis/src/lib/trellis_constellation_metrics_cf.cc
new file mode 100644
index 000000000..fb529aaa7
--- /dev/null
+++ b/gr-trellis/src/lib/trellis_constellation_metrics_cf.cc
@@ -0,0 +1,92 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2004,2010,2011 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.
+ */
+
+// WARNING: this file is machine generated.  Edits will be over written
+
+#ifndef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <trellis_constellation_metrics_cf.h>
+#include <gr_io_signature.h>
+#include <assert.h>
+#include <stdexcept>
+#include <iostream>
+
+
+
+trellis_constellation_metrics_cf_sptr
+trellis_make_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE)
+{
+  return gnuradio::get_initial_sptr (new trellis_constellation_metrics_cf (constellation, TYPE));
+}
+
+
+
+trellis_constellation_metrics_cf::trellis_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE)
+  : gr_block ("constellation_metrics_cf",
+	      gr_make_io_signature (1, -1, sizeof (gr_complex)),
+	      gr_make_io_signature (1, -1, sizeof (float))),
+    d_constellation (constellation),
+    d_TYPE (TYPE),
+    d_O (constellation->arity()),
+    d_D (constellation->dimensionality())
+{
+  set_relative_rate (1.0 * d_O / ((double) d_D));
+  set_output_multiple ((int)d_O);
+}
+
+void
+trellis_constellation_metrics_cf::forecast (int noutput_items, gr_vector_int &ninput_items_required)
+{
+  assert (noutput_items % d_O == 0);
+  unsigned int input_required =  d_D * noutput_items / d_O;
+  unsigned int ninputs = ninput_items_required.size();
+  for (unsigned int i = 0; i < ninputs; i++)
+    ninput_items_required[i] = input_required;
+}
+
+
+
+int
+trellis_constellation_metrics_cf::general_work (int noutput_items,
+				gr_vector_int &ninput_items,
+				gr_vector_const_void_star &input_items,
+				gr_vector_void_star &output_items)
+{
+
+  assert (noutput_items % d_O == 0);
+  assert (input_items.size() == output_items.size());
+  unsigned int nstreams = input_items.size();
+
+for (unsigned int m=0;m<nstreams;m++) {
+  const gr_complex *in = (gr_complex *) input_items[m];
+  float *out = (float *) output_items[m];
+
+  for (unsigned int i = 0; i < noutput_items / d_O ; i++){
+    d_constellation->calc_metric(&(in[i*d_D]), &(out[i*d_O]), d_TYPE); 
+  } 
+}
+
+  consume_each (d_D * noutput_items / d_O);
+  return noutput_items;
+}
diff --git a/gr-trellis/src/lib/trellis_constellation_metrics_cf.h b/gr-trellis/src/lib/trellis_constellation_metrics_cf.h
new file mode 100644
index 000000000..df35f16d2
--- /dev/null
+++ b/gr-trellis/src/lib/trellis_constellation_metrics_cf.h
@@ -0,0 +1,61 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2004,2010,2011 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.
+ */
+
+#ifndef INCLUDED_TRELLIS_CONSTELLATION_METRICS_CF_H
+#define INCLUDED_TRELLIS_CONSTELLATION_METRICS_CF_H
+
+#include <gr_block.h>
+#include <gr_constellation.h>
+#include <gr_metric_type.h>
+
+class trellis_constellation_metrics_cf;
+typedef boost::shared_ptr<trellis_constellation_metrics_cf> trellis_constellation_metrics_cf_sptr;
+
+trellis_constellation_metrics_cf_sptr trellis_make_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE);
+
+/*!
+ * \brief Evaluate metrics for use by the Viterbi algorithm.
+ * \ingroup coding_blk
+ */
+class trellis_constellation_metrics_cf : public gr_block
+{
+ public:
+  void forecast (int noutput_items,
+		 gr_vector_int &ninput_items_required);
+  int general_work (int noutput_items,
+		    gr_vector_int &ninput_items,
+		    gr_vector_const_void_star &input_items,
+		    gr_vector_void_star &output_items);
+ protected:
+  trellis_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE);
+ 
+ private:
+  gr_constellation_sptr d_constellation;
+  trellis_metric_type_t d_TYPE;
+  unsigned int d_O;
+  unsigned int d_D;
+  friend trellis_constellation_metrics_cf_sptr trellis_make_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE);
+
+};
+
+
+#endif
diff --git a/gr-trellis/src/lib/trellis_metric_type.h b/gr-trellis/src/lib/trellis_constellation_metrics_cf.i
index a1040f108..f863453f2 100644
--- a/gr-trellis/src/lib/trellis_metric_type.h
+++ b/gr-trellis/src/lib/trellis_constellation_metrics_cf.i
@@ -1,6 +1,6 @@
 /* -*- c++ -*- */
 /*
- * Copyright 2004 Free Software Foundation, Inc.
+ * Copyright 2004,2011 Free Software Foundation, Inc.
  *
  * This file is part of GNU Radio
  *
@@ -20,12 +20,14 @@
  * Boston, MA 02110-1301, USA.
  */
 
-#ifndef INCLUDED_TRELLIS_METRIC_TYPE_H
-#define INCLUDED_TRELLIS_METRIC_TYPE_H
+// WARNING: this file is machine generated.  Edits will be over written
 
-typedef enum {
-  TRELLIS_EUCLIDEAN = 200, TRELLIS_HARD_SYMBOL, TRELLIS_HARD_BIT
-} trellis_metric_type_t;
+GR_SWIG_BLOCK_MAGIC(trellis,constellation_metrics_cf);
 
-#endif
+trellis_constellation_metrics_cf_sptr trellis_make_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE);
 
+class trellis_constellation_metrics_cf : public gr_block
+{
+private:
+  trellis_constellation_metrics_cf (gr_constellation_sptr constellation, trellis_metric_type_t TYPE);
+};
diff --git a/gr-trellis/src/python/qa_trellis.py b/gr-trellis/src/python/qa_trellis.py
index cfeefea06..ba415e6c9 100755
--- a/gr-trellis/src/python/qa_trellis.py
+++ b/gr-trellis/src/python/qa_trellis.py
@@ -20,46 +20,45 @@
 # Boston, MA 02110-1301, USA.
 # 
 
-from gnuradio import gr, gr_unittest
+import math
+
+
+from gnuradio import gr, gr_unittest, blks2
+# It's pretty ugly that we can't import trellis from gnuradio in this test
+# but because it runs on the non-installed python code it's all a mess.
 import trellis
 
-class test_trellis (gr_unittest.TestCase):
+fsm_args = {"awgn1o2_4": (2, 4, 4,
+                          (0, 2, 0, 2, 1, 3, 1, 3),
+                          (0, 3, 3, 0, 1, 2, 2, 1),
+                          ),
+            "rep2": (2, 1, 4, (0, 0), (0, 3)),
+            "nothing": (2, 1, 2, (0, 0), (0, 1)),
+            }
 
-    def setUp (self):
-        self.tb = gr.top_block ()
+constells = {2: blks2.bpsk_constellation(),
+             4: blks2.qpsk_constellation(),
+             }
 
-    def tearDown (self):
-        self.tb = None
+class test_trellis (gr_unittest.TestCase):
 
     def test_001_fsm (self):
-        I = 2
-        S = 4
-        O = 4
-        NS = (0, 2, 0, 2, 1, 3, 1, 3)
-        OS = (0, 3, 3, 0, 1, 2, 2, 1)
-        f = trellis.fsm(I,S,O,NS,OS)
-        self.assertEqual((I,S,O,NS,OS),(f.I(),f.S(),f.O(),f.NS(),f.OS()))
+        f = trellis.fsm(*fsm_args["awgn1o2_4"])
+        self.assertEqual(fsm_args["awgn1o2_4"],(f.I(),f.S(),f.O(),f.NS(),f.OS()))
 
     def test_002_fsm (self):
-        I = 2
-        S = 4
-        O = 4
-        NS = (0, 2, 0, 2, 1, 3, 1, 3)
-        OS = (0, 3, 3, 0, 1, 2, 2, 1)
-        f = trellis.fsm(I,S,O,NS,OS)
+        f = trellis.fsm(*fsm_args["awgn1o2_4"])
         g = trellis.fsm(f)
         self.assertEqual((g.I(),g.S(),g.O(),g.NS(),g.OS()),(f.I(),f.S(),f.O(),f.NS(),f.OS()))
 
     def test_003_fsm (self):
-        I = 2
-        S = 4
-        O = 4
-        NS = (0, 2, 0, 2, 1, 3, 1, 3)
-        OS = (0, 3, 3, 0, 1, 2, 2, 1)
-        #f = trellis.fsm("awgn1o2_4.fsm")
-        #self.assertEqual((I,S,O,NS,OS),(f.I(),f.S(),f.O(),f.NS(),f.OS()))
-        # temporary fix so that make distcheck does not fail on this
-        self.assertEqual(0,0)
+        f = trellis.fsm("awgn1o2_4.fsm")
+        self.assertEqual(fsm_args["awgn1o2_4"],(f.I(),f.S(),f.O(),f.NS(),f.OS()))
+
+    def test_004_fsm(self):
+        """ Test to make sure fsm works with a single state fsm."""
+        # Just checking that it initializes properly.
+        f = trellis.fsm(*fsm_args["rep2"])
 
     def test_001_interleaver (self):
         K = 5
@@ -68,5 +67,69 @@ class test_trellis (gr_unittest.TestCase):
         i = trellis.interleaver(K,IN)
         self.assertEqual((K,IN,DIN),(i.K(),i.INTER(),i.DEINTER()))
 
+    def test_001_viterbi(self):
+        """
+        Runs some coding/decoding tests with a few different FSM
+        specs.
+        """
+        for name, args in fsm_args.items():
+            constellation = constells[args[2]]
+            fsms = trellis.fsm(*args)
+            noise = 0.1
+            tb = trellis_tb(constellation, fsms, noise)
+            tb.run()
+            # Make sure all packets succesfully transmitted.
+            self.assertEqual(tb.dst.ntotal(), tb.dst.nright())
+
+
+class trellis_tb(gr.top_block):
+    """
+    A simple top block for use testing gr-trellis.
+    """
+    def __init__(self, constellation, f, N0=0.25, seed=-666L):
+        """
+        constellation - a constellation object used for modulation.
+        f - a finite state machine specification used for coding.
+        N0 - noise level
+        seed - random seed
+        """
+        super(trellis_tb, self).__init__()
+        # packet size in bits (make it multiple of 16 so it can be packed in a short)
+        packet_size = 1024*16
+        # bits per FSM input symbol
+        bitspersymbol = int(round(math.log(f.I())/math.log(2))) # bits per FSM input symbol
+        # packet size in trellis steps
+        K = packet_size/bitspersymbol
+
+        # TX
+        src = gr.lfsr_32k_source_s()
+        # packet size in shorts
+        src_head = gr.head (gr.sizeof_short, packet_size/16)
+        # unpack shorts to symbols compatible with the FSM input cardinality
+        s2fsmi = gr.packed_to_unpacked_ss(bitspersymbol, gr.GR_MSB_FIRST) 
+        # initial FSM state = 0
+        enc = trellis.encoder_ss(f, 0) 
+        mod = gr.chunks_to_symbols_sc(constellation.points(), 1)
+
+        # CHANNEL
+        add = gr.add_cc()
+        noise = gr.noise_source_c(gr.GR_GAUSSIAN,math.sqrt(N0/2),seed)
+
+        # RX
+        # data preprocessing to generate metrics for Viterbi
+        metrics = trellis.constellation_metrics_cf(constellation.base(), trellis.TRELLIS_EUCLIDEAN) 
+        # Put -1 if the Initial/Final states are not set.
+        va = trellis.viterbi_s(f, K, 0, -1)
+        # pack FSM input symbols to shorts
+        fsmi2s = gr.unpacked_to_packed_ss(bitspersymbol, gr.GR_MSB_FIRST) 
+        # check the output
+        self.dst = gr.check_lfsr_32k_s()
+    
+        self.connect (src, src_head, s2fsmi, enc, mod)
+        self.connect (mod, (add, 0))
+        self.connect (noise, (add, 1))
+        self.connect (add, metrics, va, fsmi2s, self.dst)
+
+
 if __name__ == '__main__':
     gr_unittest.run(test_trellis, "test_trellis.xml")