GNU Radio 3.7.1 C++ API
fsm.h
Go to the documentation of this file.
00001 /* -*- c++ -*- */
00002 /*
00003  * Copyright 2002,2011-2012 Free Software Foundation, Inc.
00004  *
00005  * This file is part of GNU Radio
00006  *
00007  * GNU Radio is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 3, or (at your option)
00010  * any later version.
00011  *
00012  * GNU Radio is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with GNU Radio; see the file COPYING.  If not, write to
00019  * the Free Software Foundation, Inc., 51 Franklin Street,
00020  * Boston, MA 02110-1301, USA.
00021  */
00022 
00023 #ifndef INCLUDED_TRELLIS_FSM_H
00024 #define INCLUDED_TRELLIS_FSM_H
00025 
00026 #include <gnuradio/trellis/api.h>
00027 #include <vector>
00028 #include <iosfwd>
00029 
00030 namespace gr {
00031   namespace trellis {
00032 
00033     /*!
00034      * \brief  Finite State Machine Specification class.
00035      * \ingroup trellis_coding_blk
00036      *
00037      * \details
00038      * An instance of this class represents a finite state machine
00039      * specification (FSMS) rather than the FSM itself.  It particular
00040      * the state of the FSM is not stored within an instance of this
00041      * class.
00042      */
00043     class TRELLIS_API fsm
00044     {
00045     private:
00046       // Input alphabet cardinality.
00047       int d_I;
00048 
00049       // Number of states.
00050       int d_S;
00051 
00052       // Output alphabet cardinality.
00053       int d_O;
00054 
00055       // NS means Next State.
00056       // next_state = d_NS[current_state * d_I + input_symbol]
00057       std::vector<int> d_NS;
00058 
00059       // OS means Output Symbol.
00060       // output_symbol = d_OS[current_state * d_I + input_symbol]
00061       std::vector<int> d_OS;
00062 
00063       // PS means Previous State.
00064       std::vector< std::vector<int> > d_PS;
00065 
00066       // PI means Previous Input Symbol.
00067       // d_PS[current_state][k] and d_PI[current_state][k], is a pair of the form
00068       // (previous_state, previous_input_symbol) that could have produced the
00069       // current state.
00070       std::vector< std::vector<int> > d_PI;
00071 
00072       // TM means Termination matrix.
00073       // d_TMl[s*d_S+es] is the shortest number of steps to get from state s to
00074       // state es.
00075       std::vector<int> d_TMl;
00076 
00077       // d_TMi[s*d_S+es] is the input symbol required to set off on the shortest
00078       // path from state s to es.
00079       std::vector<int> d_TMi;
00080       void generate_PS_PI ();
00081       void generate_TM ();
00082       bool find_es(int es);
00083 
00084     public:
00085       /*!
00086        * \brief Constructor to create an uninitialized FSMS.
00087        */
00088       fsm();
00089 
00090       /*!
00091        * \brief Constructor to copy an FSMS.
00092        */
00093       fsm(const fsm &FSM);
00094 
00095       /*!
00096        * \brief Constructor to to create an FSMS.
00097        *
00098        * \param I               The number of possible input symbols.
00099        * \param S           The number of possible FSM states.
00100        * \param O           The number of possible output symbols.
00101        * \param NS          A mapping from (current state, input symbol) to next state.
00102        *                    next_state = NS[current_state * I + input_symbol]
00103        * \param OS          A mapping from (current state, input symbol) to output symbol.
00104        *                    output_symbol = OS[current_state * I + input_symbol]
00105        *
00106        */
00107       fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS);
00108 
00109       /*!
00110        * \brief Constructor to create an FSMS from file contents.
00111        *
00112        * \param name        filename
00113        *
00114        */
00115       fsm(const char *name);
00116 
00117       /*!
00118        * \brief Creates an FSMS from the generator matrix of a (n, k) binary convolutional code.
00119        *
00120        * \param k      ???
00121        * \param n      ???
00122        * \param G      ???
00123        *
00124        */
00125       fsm(int k, int n, const std::vector<int> &G);
00126 
00127       /*!
00128        * \brief Creates an FSMS describing ISI.
00129        *
00130        * \param mod_size    modulation size
00131        * \param ch_length   channel length
00132        *
00133        */
00134       fsm(int mod_size, int ch_length);
00135 
00136       /*!
00137        * \brief Creates an FSMS describing the trellis for a CPM.
00138        *
00139        * \param P    ???? h=K/P (relatively prime)
00140        * \param M    alphabet size
00141        * \param L    pulse duration
00142        *
00143        * This FSM is based on the paper by B. Rimoldi
00144        * "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
00145        * See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
00146        */
00147       fsm(int P, int M, int L);
00148 
00149       /*!
00150        * \brief Creates an FSMS describing the joint trellis of two FSMs.
00151        *
00152        * \param FSM1  first FSMS
00153        * \param FSM2  second FSMS
00154        */
00155       fsm(const fsm &FSM1, const fsm &FSM2);
00156 
00157       /*!
00158        * \brief Creates an FSMS representing n stages through the originial FSM (AKA radix-n FSM).
00159        *
00160        * \param FSM      Original FSMs
00161        * \param n        Number of stages.
00162        */
00163       fsm(const fsm &FSM, int n);
00164       int I() const { return d_I; }
00165       int S() const { return d_S; }
00166       int O() const { return d_O; }
00167       const std::vector<int> & NS() const { return d_NS; }
00168       const std::vector<int> & OS() const { return d_OS; }
00169       const std::vector< std::vector<int> > & PS() const { return d_PS; }
00170       const std::vector< std::vector<int> > & PI() const { return d_PI; }
00171       const std::vector<int> & TMi() const { return d_TMi; }
00172       const std::vector<int> & TMl() const { return d_TMl; }
00173 
00174       /*!
00175        * \brief Creates an svg image of the trellis representation.
00176        *
00177        * \param filename         filename
00178        * \param number_stages    ????
00179        */
00180       void write_trellis_svg(std::string filename ,int number_stages);
00181 
00182       /*!
00183        * \brief Write the FSMS to a file.
00184        *
00185        * \param filename   filename
00186        */
00187       void write_fsm_txt(std::string filename);
00188     };
00189 
00190   } /* namespace trellis */
00191 } /* namespace gr */
00192 
00193 #endif /* INCLUDED_TRELLIS_FSM_H */