GNU Radio 3.6.5.1 C++ API
fsm.h
Go to the documentation of this file.
1 /* -*- c++ -*- */
2 /*
3  * Copyright 2002,2011 Free Software Foundation, Inc.
4  *
5  * This file is part of GNU Radio
6  *
7  * GNU Radio is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 3, or (at your option)
10  * any later version.
11  *
12  * GNU Radio is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with GNU Radio; see the file COPYING. If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street,
20  * Boston, MA 02110-1301, USA.
21  */
22 
23 #ifndef INCLUDED_TRELLIS_FSM_H
24 #define INCLUDED_TRELLIS_FSM_H
25 
26 #include <trellis_api.h>
27 #include <vector>
28 #include <iosfwd>
29 
30 /*!
31  * \brief Finite State Machine Specification class.
32  * \ingroup trellis_coding_blk
33  *
34  * An instance of this class represents a finite state machine specification (FSMS)
35  * rather than the FSM itself. It particular the state of the FSM
36  * is not stored within an instance of this class.
37  */
39 private:
40  // Input alphabet cardinality.
41  int d_I;
42  // Number of states.
43  int d_S;
44  // Output alphabet cardinality.
45  int d_O;
46  // NS means Next State.
47  // next_state = d_NS[current_state * d_I + input_symbol]
48  std::vector<int> d_NS;
49  // OS means Output Symbol.
50  // output_symbol = d_OS[current_state * d_I + input_symbol]
51  std::vector<int> d_OS;
52  // PS means Previous State.
53  std::vector< std::vector<int> > d_PS;
54  // PI means Previous Input Symbol.
55  // d_PS[current_state][k] and d_PI[current_state][k], is a pair of the form
56  // (previous_state, previous_input_symbol) that could have produced the
57  // current state.
58  std::vector< std::vector<int> > d_PI;
59  // TM means Termination matrix.
60  // d_TMl[s*d_S+es] is the shortest number of steps to get from state s to
61  // state es.
62  std::vector<int> d_TMl;
63  // d_TMi[s*d_S+es] is the input symbol required to set off on the shortest
64  // path from state s to es.
65  std::vector<int> d_TMi;
66  void generate_PS_PI ();
67  void generate_TM ();
68  bool find_es(int es);
69 public:
70  /*!
71  * \brief Constructor to create an uninitialized FSMS.
72  */
73  fsm();
74  /*!
75  * \brief Constructor to copy an FSMS.
76  */
77  fsm(const fsm &FSM);
78  /*!
79  * \brief Constructor to to create an FSMS.
80  *
81  * \param I The number of possible input symbols.
82  * \param S The number of possible FSM states.
83  * \param O The number of possible output symbols.
84  * \param NS A mapping from (current state, input symbol) to next state.
85  * next_state = NS[current_state * I + input_symbol]
86  * \param OS A mapping from (current state, input symbol) to output symbol.
87  * output_symbol = OS[current_state * I + input_symbol]
88  *
89  */
90  fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS);
91  /*!
92  * \brief Constructor to create an FSMS from file contents.
93  *
94  * \param name filename
95  *
96  */
97  fsm(const char *name);
98  /*!
99  * \brief Creates an FSMS from the generator matrix of a (n, k) binary convolutional code.
100  *
101  * \param k ???
102  * \param n ???
103  * \param G ???
104  *
105  */
106  fsm(int k, int n, const std::vector<int> &G);
107  /*!
108  * \brief Creates an FSMS describing ISI.
109  *
110  * \param mod_size modulation size
111  * \param ch_length channel length
112  *
113  */
114  fsm(int mod_size, int ch_length);
115  /*!
116  * \brief Creates an FSMS describing the trellis for a CPM.
117  *
118  * \param P ???? h=K/P (relatively prime)
119  * \param M alphabet size
120  * \param L pulse duration
121  *
122  * This FSM is based on the paper by B. Rimoldi
123  * "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
124  * See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
125  */
126  fsm(int P, int M, int L);
127  /*!
128  * \brief Creates an FSMS describing the joint trellis of two FSMs.
129  *
130  * \param FSM1 first FSMS
131  * \param FSM2 second FSMS
132  */
133  fsm(const fsm &FSM1, const fsm &FSM2);
134  /*!
135  * \brief Creates an FSMS representing n stages through the originial FSM (AKA radix-n FSM).
136  *
137  * \param FSM Original FSMs
138  * \param n Number of stages.
139  */
140  fsm(const fsm &FSM, int n);
141  int I () const { return d_I; }
142  int S () const { return d_S; }
143  int O () const { return d_O; }
144  const std::vector<int> & NS () const { return d_NS; }
145  const std::vector<int> & OS () const { return d_OS; }
146  const std::vector< std::vector<int> > & PS () const { return d_PS; }
147  const std::vector< std::vector<int> > & PI () const { return d_PI; }
148  const std::vector<int> & TMi () const { return d_TMi; }
149  const std::vector<int> & TMl () const { return d_TMl; }
150  /*!
151  * \brief Creates an svg image of the trellis representation.
152  *
153  * \param filename filename
154  * \param number_stages ????
155  *
156  */
157  void write_trellis_svg(std::string filename ,int number_stages);
158  /*!
159  * \brief Write the FSMS to a file.
160  *
161  * \param filename filename
162  *
163  */
164  void write_fsm_txt(std::string filename);
165 };
166 
167 #endif