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