GNU Radio Manual and C++ API Reference  3.7.9.2
The Free & Open Software Radio Ecosystem
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
fsm.h
Go to the documentation of this file.
1 /* -*- c++ -*- */
2 /*
3  * Copyright 2002,2011-2012 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 <gnuradio/trellis/api.h>
27 #include <vector>
28 #include <iosfwd>
29 
30 namespace gr {
31  namespace trellis {
32 
33  /*!
34  * \brief Finite State Machine Specification class.
35  * \ingroup trellis_coding_blk
36  *
37  * \details
38  * An instance of this class represents a finite state machine
39  * specification (FSMS) rather than the FSM itself. It particular
40  * the state of the FSM is not stored within an instance of this
41  * class.
42  */
44  {
45  private:
46  // Input alphabet cardinality.
47  int d_I;
48 
49  // Number of states.
50  int d_S;
51 
52  // Output alphabet cardinality.
53  int d_O;
54 
55  // NS means Next State.
56  // next_state = d_NS[current_state * d_I + input_symbol]
57  std::vector<int> d_NS;
58 
59  // OS means Output Symbol.
60  // output_symbol = d_OS[current_state * d_I + input_symbol]
61  std::vector<int> d_OS;
62 
63  // PS means Previous State.
64  std::vector< std::vector<int> > d_PS;
65 
66  // PI means Previous Input Symbol.
67  // d_PS[current_state][k] and d_PI[current_state][k], is a pair of the form
68  // (previous_state, previous_input_symbol) that could have produced the
69  // current state.
70  std::vector< std::vector<int> > d_PI;
71 
72  // TM means Termination matrix.
73  // d_TMl[s*d_S+es] is the shortest number of steps to get from state s to
74  // state es.
75  std::vector<int> d_TMl;
76 
77  // d_TMi[s*d_S+es] is the input symbol required to set off on the shortest
78  // path from state s to es.
79  std::vector<int> d_TMi;
80  void generate_PS_PI ();
81  void generate_TM ();
82  bool find_es(int es);
83 
84  public:
85  /*!
86  * \brief Constructor to create an uninitialized FSMS.
87  */
88  fsm();
89 
90  /*!
91  * \brief Constructor to copy an FSMS.
92  */
93  fsm(const fsm &FSM);
94 
95  /*!
96  * \brief Constructor to to create an FSMS.
97  *
98  * \param I The number of possible input symbols.
99  * \param S The number of possible FSM states.
100  * \param O The number of possible output symbols.
101  * \param NS A mapping from (current state, input symbol) to next state.
102  * next_state = NS[current_state * I + input_symbol]
103  * \param OS A mapping from (current state, input symbol) to output symbol.
104  * output_symbol = OS[current_state * I + input_symbol]
105  *
106  */
107  fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS);
108 
109  /*!
110  * \brief Constructor to create an FSMS from file contents.
111  *
112  * \param name filename
113  *
114  */
115  fsm(const char *name);
116 
117  /*!
118  * \brief Creates an FSMS from the generator matrix of a (n, k) binary convolutional code.
119  *
120  * \param k ???
121  * \param n ???
122  * \param G ???
123  *
124  */
125  fsm(int k, int n, const std::vector<int> &G);
126 
127  /*!
128  * \brief Creates an FSMS describing ISI.
129  *
130  * \param mod_size modulation size
131  * \param ch_length channel length
132  *
133  */
134  fsm(int mod_size, int ch_length);
135 
136  /*!
137  * \brief Creates an FSMS describing the trellis for a CPM.
138  *
139  * \param P ???? h=K/P (relatively prime)
140  * \param M alphabet size
141  * \param L pulse duration
142  *
143  * This FSM is based on the paper by B. Rimoldi
144  * "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
145  * See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
146  */
147  fsm(int P, int M, int L);
148 
149  /*!
150  * \brief Creates an FSMS describing the joint trellis of two FSMs.
151  *
152  * \param FSM1 first FSMS
153  * \param FSM2 second FSMS
154  */
155  fsm(const fsm &FSM1, const fsm &FSM2);
156 
157 
158  /*!
159  * \brief Creates an FSMS describing the trellis of two serially concatenated FSMs.
160  *
161  * \param FSMo outer FSMS
162  * \param FSMi inner FSMS
163  * \param serial set it to true to distinguish from the previous constructor
164  */
165  fsm(const fsm &FSMo, const fsm &FSMi, bool serial);
166 
167  /*!
168  * \brief Creates an FSMS representing n stages through the originial FSM (AKA radix-n FSM).
169  *
170  * \param FSM Original FSMs
171  * \param n Number of stages.
172  */
173  fsm(const fsm &FSM, int n);
174  int I() const { return d_I; }
175  int S() const { return d_S; }
176  int O() const { return d_O; }
177  const std::vector<int> & NS() const { return d_NS; }
178  const std::vector<int> & OS() const { return d_OS; }
179  const std::vector< std::vector<int> > & PS() const { return d_PS; }
180  const std::vector< std::vector<int> > & PI() const { return d_PI; }
181  const std::vector<int> & TMi() const { return d_TMi; }
182  const std::vector<int> & TMl() const { return d_TMl; }
183 
184  /*!
185  * \brief Creates an svg image of the trellis representation.
186  *
187  * \param filename filename
188  * \param number_stages ????
189  */
190  void write_trellis_svg(std::string filename ,int number_stages);
191 
192  /*!
193  * \brief Write the FSMS to a file.
194  *
195  * \param filename filename
196  */
197  void write_fsm_txt(std::string filename);
198  };
199 
200  } /* namespace trellis */
201 } /* namespace gr */
202 
203 #endif /* INCLUDED_TRELLIS_FSM_H */
const std::vector< int > & NS() const
Definition: fsm.h:177
const std::vector< int > & TMl() const
Definition: fsm.h:182
const std::vector< std::vector< int > > & PS() const
Definition: fsm.h:179
const std::vector< int > & TMi() const
Definition: fsm.h:181
const std::vector< int > & OS() const
Definition: fsm.h:178
int I() const
Definition: fsm.h:174
Include this header to use the message passing features.
Definition: logger.h:131
const std::vector< std::vector< int > > & PI() const
Definition: fsm.h:180
#define TRELLIS_API
Definition: gr-trellis/include/gnuradio/trellis/api.h:30
int S() const
Definition: fsm.h:175
int O() const
Definition: fsm.h:176
Finite State Machine Specification class.
Definition: fsm.h:43
#define S(x)
Definition: rpcserver_thrift.h:37