diff options
Diffstat (limited to 'gr-trellis/include/gnuradio/trellis/fsm.h')
| -rw-r--r-- | gr-trellis/include/gnuradio/trellis/fsm.h | 193 |
1 files changed, 193 insertions, 0 deletions
diff --git a/gr-trellis/include/gnuradio/trellis/fsm.h b/gr-trellis/include/gnuradio/trellis/fsm.h new file mode 100644 index 0000000000..cc8893f1e3 --- /dev/null +++ b/gr-trellis/include/gnuradio/trellis/fsm.h @@ -0,0 +1,193 @@ +/* -*- c++ -*- */ +/* + * Copyright 2002,2011-2012 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_FSM_H +#define INCLUDED_TRELLIS_FSM_H + +#include <gnuradio/trellis/api.h> +#include <vector> +#include <iosfwd> + +namespace gr { + namespace trellis { + + /*! + * \brief Finite State Machine Specification class. + * \ingroup trellis_coding_blk + * + * \details + * 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 TRELLIS_API 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; + + // 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_length 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 FSM 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; } + int O() const { return d_O; } + const std::vector<int> & NS() const { return d_NS; } + const std::vector<int> & OS() const { return d_OS; } + const std::vector< std::vector<int> > & PS() const { return d_PS; } + 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); + }; + + } /* namespace trellis */ +} /* namespace gr */ + +#endif /* INCLUDED_TRELLIS_FSM_H */ |