diff options
Diffstat (limited to 'gr-trellis')
| -rw-r--r-- | gr-trellis/src/lib/Makefile.am | 4 | ||||
| -rw-r--r-- | gr-trellis/src/lib/Makefile.swig.gen | 2 | ||||
| -rw-r--r-- | gr-trellis/src/lib/fsm.cc | 2 | ||||
| -rw-r--r-- | gr-trellis/src/lib/fsm.h | 102 | ||||
| -rw-r--r-- | gr-trellis/src/lib/trellis.i | 12 | ||||
| -rw-r--r-- | gr-trellis/src/lib/trellis_calc_metric.h | 2 | ||||
| -rw-r--r-- | gr-trellis/src/lib/trellis_constellation_metrics_cf.cc | 92 | ||||
| -rw-r--r-- | gr-trellis/src/lib/trellis_constellation_metrics_cf.h | 61 | ||||
| -rw-r--r-- | gr-trellis/src/lib/trellis_constellation_metrics_cf.i (renamed from gr-trellis/src/lib/trellis_metric_type.h) | 16 | ||||
| -rwxr-xr-x | gr-trellis/src/python/qa_trellis.py | 119 |
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") |