added support for irregular FSMs

git-svn-id: http://gnuradio.org/svn/gnuradio/trunk@4371 221aa14e-8319-0410-a670-987f0aec2ac5

13 files changed, 89 insertions, 83 deletions

diff --git a/gr-trellis/src/lib/fsm.cc b/gr-trellis/src/lib/fsm.cc
index 22f7772b3..6e3933894 100644
--- a/gr-trellis/src/lib/fsm.cc
+++ b/gr-trellis/src/lib/fsm.cc
@@ -47,7 +47,7 @@ fsm::fsm(const fsm &FSM)
   d_O=FSM.O();
   d_NS=FSM.NS();
   d_OS=FSM.OS();
-  d_PS=FSM.PS();
+  d_PS=FSM.PS(); // is this going to make a deep copy?
   d_PI=FSM.PI();
   d_TMi=FSM.TMi();
   d_TMl=FSM.TMl();
@@ -241,17 +241,21 @@ fsm::fsm(int mod_size, int ch_length)
 //######################################################################
 void fsm::generate_PS_PI()
 {
-  d_PS.resize(d_I*d_S);
-  d_PI.resize(d_I*d_S);
+  d_PS.resize(d_S);
+  d_PI.resize(d_S);
 
   for(int i=0;i<d_S;i++) {
+    d_PS[i].resize(d_I*d_S); // max possible size
+    d_PI[i].resize(d_I*d_S);
     int j=0;
     for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
       if(d_NS[ii*d_I+jj]!=i) continue;
-      d_PS[i*d_I+j]=ii;
-      d_PI[i*d_I+j]=jj;
+      d_PS[i][j]=ii;
+      d_PI[i][j]=jj;
       j++;
     }
+    d_PS[i].resize(j);
+    d_PI[i].resize(j);
   }
 }
 
@@ -278,9 +282,11 @@ void fsm::generate_TM()
       done = find_es(s);
       attempts ++;
     }
-    if (done == false)
+    if (done == false) {
       //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be disconnected\n");
       printf("fsm::generate_TM(): FSM appears to be disconnected\n");
+      printf("state %d cannot be reached from all other states\n",s);
+    }
   }
 }
 
diff --git a/gr-trellis/src/lib/fsm.h b/gr-trellis/src/lib/fsm.h
index 4b0453a72..66b1f1cc8 100644
--- a/gr-trellis/src/lib/fsm.h
+++ b/gr-trellis/src/lib/fsm.h
@@ -35,8 +35,8 @@ private:
   int d_O;
   std::vector<int> d_NS;
   std::vector<int> d_OS;
-  std::vector<int> d_PS;
-  std::vector<int> d_PI;
+  std::vector< std::vector<int> > d_PS;
+  std::vector< std::vector<int> > d_PI;
   std::vector<int> d_TMi;
   std::vector<int> d_TMl;
   void generate_PS_PI ();
@@ -54,8 +54,8 @@ public:
   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<int> & PS () const { return d_PS; }
-  const std::vector<int> & PI () const { return d_PI; }
+  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; }
 };
diff --git a/gr-trellis/src/lib/fsm.i b/gr-trellis/src/lib/fsm.i
index 470da0eca..cec45fce3 100644
--- a/gr-trellis/src/lib/fsm.i
+++ b/gr-trellis/src/lib/fsm.i
@@ -27,8 +27,8 @@ private:
   int d_O;
   std::vector<int> d_NS;
   std::vector<int> d_OS;
-  std::vector<int> d_PS;
-  std::vector<int> d_PI;
+  std::vector< std::vector<int> > d_PS;
+  std::vector< std::vector<int> > d_PI;
   std::vector<int> d_TMi;
   std::vector<int> d_TMl;
   void generate_PS_PI ();
@@ -45,8 +45,8 @@ public:
   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<int> & PS () const { return d_PS; }
-  const std::vector<int> & PI () const { return d_PI; }
+  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; }
 };
diff --git a/gr-trellis/src/lib/trellis_siso_combined_f.cc b/gr-trellis/src/lib/trellis_siso_combined_f.cc
index 9ad0ae241..293c42e15 100644
--- a/gr-trellis/src/lib/trellis_siso_combined_f.cc
+++ b/gr-trellis/src/lib/trellis_siso_combined_f.cc
@@ -138,8 +138,8 @@ inline float min_star(float a, float b)
 void siso_algorithm_combined(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              bool POSTI, bool POSTO,
@@ -171,9 +171,9 @@ void siso_algorithm_combined(int I, int S, int O,
       norm=INF;
       for(int j=0;j<S;j++) {
           minm=INF;
-          for(int i=0;i<I;i++) {
+          for(int i=0;i<PS[j].size();i++) {
               int i0 = j*I+i;
-              mm=alpha[k*S+PS[i0]]+priori[k*I+PI[i0]]+prioro[k*O+OS[PS[i0]*I+PI[i0]]];
+              mm=alpha[k*S+PS[j][i]]+priori[k*I+PI[j][i]]+prioro[k*O+OS[PS[j][i]*I+PI[j][i]]];
               minm=(*p2mymin)(minm,mm);
           }
           alpha[(k+1)*S+j]=minm;
diff --git a/gr-trellis/src/lib/trellis_siso_f.cc b/gr-trellis/src/lib/trellis_siso_f.cc
index b3d18c2b7..9fe503eea 100644
--- a/gr-trellis/src/lib/trellis_siso_f.cc
+++ b/gr-trellis/src/lib/trellis_siso_f.cc
@@ -129,8 +129,8 @@ inline float min_star(float a, float b)
 void siso_algorithm(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              bool POSTI, bool POSTO,
@@ -157,9 +157,9 @@ void siso_algorithm(int I, int S, int O,
       norm=INF;
       for(int j=0;j<S;j++) {
           minm=INF;
-          for(int i=0;i<I;i++) {
-              int i0 = j*I+i;
-              mm=alpha[k*S+PS[i0]]+priori[k*I+PI[i0]]+prioro[k*O+OS[PS[i0]*I+PI[i0]]];
+          for(int i=0;i<PS[j].size();i++) {
+              //int i0 = j*I+i;
+              mm=alpha[k*S+PS[j][i]]+priori[k*I+PI[j][i]]+prioro[k*O+OS[PS[j][i]*I+PI[j][i]]];
               minm=(*p2mymin)(minm,mm);
           }
           alpha[(k+1)*S+j]=minm;
diff --git a/gr-trellis/src/lib/trellis_viterbi_X.cc.t b/gr-trellis/src/lib/trellis_viterbi_X.cc.t
index 3cf602ff1..e3d385b1c 100644
--- a/gr-trellis/src/lib/trellis_viterbi_X.cc.t
+++ b/gr-trellis/src/lib/trellis_viterbi_X.cc.t
@@ -77,8 +77,8 @@ void
 void viterbi_algorithm(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              const float *in, @TYPE@ *out)//,
@@ -106,9 +106,9 @@ void viterbi_algorithm(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
-              int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+in[k*O+OS[PS[i0]*I+PI[i0]]])<minm)
+          for(int i=0;i<PS[j].size();i++) {
+              //int i0 = j*I+i;
+              if((mm=alpha[alphai*S+PS[j][i]]+in[k*O+OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -132,9 +132,9 @@ void viterbi_algorithm(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (@TYPE@) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (@TYPE@) PI[st][i0];
+      st=PS[st][i0];
   }
 
 }
diff --git a/gr-trellis/src/lib/trellis_viterbi_b.cc b/gr-trellis/src/lib/trellis_viterbi_b.cc
index e30f51388..01c75381c 100644
--- a/gr-trellis/src/lib/trellis_viterbi_b.cc
+++ b/gr-trellis/src/lib/trellis_viterbi_b.cc
@@ -77,8 +77,8 @@ trellis_viterbi_b::forecast (int noutput_items, gr_vector_int &ninput_items_requ
 void viterbi_algorithm(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              const float *in, unsigned char *out)//,
@@ -106,9 +106,9 @@ void viterbi_algorithm(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
-              int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+in[k*O+OS[PS[i0]*I+PI[i0]]])<minm)
+          for(int i=0;i<PS[j].size();i++) {
+              //int i0 = j*I+i;
+              if((mm=alpha[alphai*S+PS[j][i]]+in[k*O+OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -132,9 +132,9 @@ void viterbi_algorithm(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (unsigned char) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (unsigned char) PI[st][i0];
+      st=PS[st][i0];
   }
 
 }
diff --git a/gr-trellis/src/lib/trellis_viterbi_combined_X.cc.t b/gr-trellis/src/lib/trellis_viterbi_combined_X.cc.t
index e693c1d68..33f629099 100644
--- a/gr-trellis/src/lib/trellis_viterbi_combined_X.cc.t
+++ b/gr-trellis/src/lib/trellis_viterbi_combined_X.cc.t
@@ -86,8 +86,8 @@ void
 void viterbi_algorithm_combined(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              int D,
@@ -119,9 +119,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
+          for(int i=0;i<PS[j].size();i++) {
               int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+metric[OS[PS[i0]*I+PI[i0]]])<minm)
+              if((mm=alpha[alphai*S+PS[j][i]]+metric[OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -145,9 +145,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (@TYPE@) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (@TYPE@) PI[st][i0];
+      st=PS[st][i0];
   }
   
   delete [] metric;
diff --git a/gr-trellis/src/lib/trellis_viterbi_combined_b.cc b/gr-trellis/src/lib/trellis_viterbi_combined_b.cc
index 73e98ffed..62d877f6a 100644
--- a/gr-trellis/src/lib/trellis_viterbi_combined_b.cc
+++ b/gr-trellis/src/lib/trellis_viterbi_combined_b.cc
@@ -86,8 +86,8 @@ trellis_viterbi_combined_b::forecast (int noutput_items, gr_vector_int &ninput_i
 void viterbi_algorithm_combined(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              int D,
@@ -119,9 +119,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
+          for(int i=0;i<PS[j].size();i++) {
               int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+metric[OS[PS[i0]*I+PI[i0]]])<minm)
+              if((mm=alpha[alphai*S+PS[j][i]]+metric[OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -145,9 +145,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (unsigned char) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (unsigned char) PI[st][i0];
+      st=PS[st][i0];
   }
   
   delete [] metric;
diff --git a/gr-trellis/src/lib/trellis_viterbi_combined_i.cc b/gr-trellis/src/lib/trellis_viterbi_combined_i.cc
index 754decb57..37a035500 100644
--- a/gr-trellis/src/lib/trellis_viterbi_combined_i.cc
+++ b/gr-trellis/src/lib/trellis_viterbi_combined_i.cc
@@ -86,8 +86,8 @@ trellis_viterbi_combined_i::forecast (int noutput_items, gr_vector_int &ninput_i
 void viterbi_algorithm_combined(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              int D,
@@ -119,9 +119,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
+          for(int i=0;i<PS[j].size();i++) {
               int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+metric[OS[PS[i0]*I+PI[i0]]])<minm)
+              if((mm=alpha[alphai*S+PS[j][i]]+metric[OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -145,9 +145,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (int) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (int) PI[st][i0];
+      st=PS[st][i0];
   }
   
   delete [] metric;
diff --git a/gr-trellis/src/lib/trellis_viterbi_combined_s.cc b/gr-trellis/src/lib/trellis_viterbi_combined_s.cc
index 24c1e56b5..c332dd0d5 100644
--- a/gr-trellis/src/lib/trellis_viterbi_combined_s.cc
+++ b/gr-trellis/src/lib/trellis_viterbi_combined_s.cc
@@ -86,8 +86,8 @@ trellis_viterbi_combined_s::forecast (int noutput_items, gr_vector_int &ninput_i
 void viterbi_algorithm_combined(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              int D,
@@ -119,9 +119,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
+          for(int i=0;i<PS[j].size();i++) {
               int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+metric[OS[PS[i0]*I+PI[i0]]])<minm)
+              if((mm=alpha[alphai*S+PS[j][i]]+metric[OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -145,9 +145,9 @@ void viterbi_algorithm_combined(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (short) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (short) PI[st][i0];
+      st=PS[st][i0];
   }
   
   delete [] metric;
diff --git a/gr-trellis/src/lib/trellis_viterbi_i.cc b/gr-trellis/src/lib/trellis_viterbi_i.cc
index b81df8f13..f5d61173b 100644
--- a/gr-trellis/src/lib/trellis_viterbi_i.cc
+++ b/gr-trellis/src/lib/trellis_viterbi_i.cc
@@ -77,8 +77,8 @@ trellis_viterbi_i::forecast (int noutput_items, gr_vector_int &ninput_items_requ
 void viterbi_algorithm(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              const float *in, int *out)//,
@@ -106,9 +106,9 @@ void viterbi_algorithm(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
-              int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+in[k*O+OS[PS[i0]*I+PI[i0]]])<minm)
+          for(int i=0;i<PS[j].size();i++) {
+              //int i0 = j*I+i;
+              if((mm=alpha[alphai*S+PS[j][i]]+in[k*O+OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -132,9 +132,9 @@ void viterbi_algorithm(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (int) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (int) PI[st][i0];
+      st=PS[st][i0];
   }
 
 }
diff --git a/gr-trellis/src/lib/trellis_viterbi_s.cc b/gr-trellis/src/lib/trellis_viterbi_s.cc
index e352a2604..ccdd11558 100644
--- a/gr-trellis/src/lib/trellis_viterbi_s.cc
+++ b/gr-trellis/src/lib/trellis_viterbi_s.cc
@@ -77,8 +77,8 @@ trellis_viterbi_s::forecast (int noutput_items, gr_vector_int &ninput_items_requ
 void viterbi_algorithm(int I, int S, int O, 
              const std::vector<int> &NS,
              const std::vector<int> &OS,
-             const std::vector<int> &PS,
-             const std::vector<int> &PI,
+             const std::vector< std::vector<int> > &PS,
+             const std::vector< std::vector<int> > &PI,
              int K,
              int S0,int SK,
              const float *in, short *out)//,
@@ -106,9 +106,9 @@ void viterbi_algorithm(int I, int S, int O,
       for(int j=0;j<S;j++) { // for each next state do ACS
           minm=INF;
           minmi=0;
-          for(int i=0;i<I;i++) {
-              int i0 = j*I+i;
-              if((mm=alpha[alphai*S+PS[i0]]+in[k*O+OS[PS[i0]*I+PI[i0]]])<minm)
+          for(int i=0;i<PS[j].size();i++) {
+              //int i0 = j*I+i;
+              if((mm=alpha[alphai*S+PS[j][i]]+in[k*O+OS[PS[j][i]*I+PI[j][i]]])<minm)
                   minm=mm,minmi=i;
           }
           trace[k*S+j]=minmi;
@@ -132,9 +132,9 @@ void viterbi_algorithm(int I, int S, int O,
   }
 
   for(int k=K-1;k>=0;k--) { // traceback
-      int i0=st*I+trace[k*S+st];
-      out[k]= (short) PI[i0];
-      st=PS[i0];
+      int i0=trace[k*S+st];
+      out[k]= (short) PI[st][i0];
+      st=PS[st][i0];
   }
 
 }