X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=gr-trellis%2Fsrc%2Flib%2Ffsm.cc;h=5950b56b9d2ae612fad5597e66bf4e3d1707eab0;hb=a72819e861caaabdea0ac41f5f5e387cb61d3513;hp=2cf1a6d5abb64b2aedacbc4368e2556b625ce4e0;hpb=319caa5a3882142be42e03b0f20488730f5d208e;p=debian%2Fgnuradio

diff --git a/gr-trellis/src/lib/fsm.cc b/gr-trellis/src/lib/fsm.cc
index 2cf1a6d5..5950b56b 100644
--- a/gr-trellis/src/lib/fsm.cc
+++ b/gr-trellis/src/lib/fsm.cc
@@ -6,7 +6,7 @@
  *
  * GNU Radio is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2, or (at your option)
+ * the Free Software Foundation; either version 3, or (at your option)
  * any later version.
  *
  * GNU Radio is distributed in the hope that it will be useful,
@@ -16,13 +16,17 @@
  *
  * You should have received a copy of the GNU General Public License
  * along with GNU Radio; see the file COPYING.  If not, write to
- * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
  */
 
 #include <cstdio>
+#include <string>
+#include <iostream>
+#include <fstream>
 #include <stdexcept>
 #include <cmath>
+#include <stdlib.h>
 #include "base.h"
 #include "fsm.h"
 
@@ -47,7 +51,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();
@@ -82,16 +86,30 @@ fsm::fsm(const char *name)
   if((fsmfile=fopen(name,"r"))==NULL) 
     throw std::runtime_error ("fsm::fsm(const char *name): file open error\n");
     //printf("file open error in fsm()\n");
+
+  if(fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O) == EOF) {
+    if(ferror(fsmfile) != 0)
+      throw std::runtime_error ("fsm::fsm(const char *name): file read error\n");
+  }
   
-  fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O);
   d_NS.resize(d_I*d_S);
   d_OS.resize(d_I*d_S);
 
   for(int i=0;i<d_S;i++) {
-    for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_NS[i*d_I+j]));
+    for(int j=0;j<d_I;j++) {
+      if(fscanf(fsmfile,"%d",&(d_NS[i*d_I+j])) == EOF) {
+	if(ferror(fsmfile) != 0)
+	  throw std::runtime_error ("fsm::fsm(const char *name): file read error\n");
+      }
+    }
   }
   for(int i=0;i<d_S;i++) {
-    for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_OS[i*d_I+j]));
+    for(int j=0;j<d_I;j++) {
+      if(fscanf(fsmfile,"%d",&(d_OS[i*d_I+j])) == EOF) {
+	if(ferror(fsmfile) != 0)
+	  throw std::runtime_error ("fsm::fsm(const char *name): file read error\n");
+      }
+    }
   }
  
   generate_PS_PI();
@@ -100,7 +118,6 @@ fsm::fsm(const char *name)
 
 
 
-
 //######################################################################
 //# Automatically generate the FSM from the generator matrix
 //# of a (n,k) binary convolutional code
@@ -167,7 +184,7 @@ fsm::fsm(int k, int n, const std::vector<int> &G)
 
 
   for(int s=0;s<d_S;s++) {
-    dec2bases(s,bases_x,sx); // split s into k values, each representing on of the k shift registers
+    dec2bases(s,bases_x,sx); // split s into k values, each representing one of the k shift registers
 //printf("state = %d \nstates = ",s);
 //for(int j=0;j<sx.size();j++) printf("%d ",sx[j]); printf("\n");
     for(int i=0;i<d_I;i++) {
@@ -236,22 +253,144 @@ fsm::fsm(int mod_size, int ch_length)
 }
 
 
+
+
+//######################################################################
+//# Automatically generate an FSM specification describing the 
+//# the trellis for a CPM with h=K/P (relatively prime), 
+//# alphabet size M, and frequency pulse duration L symbols
+//#
+//# This FSM is based on the paper by B. Rimoldi
+//# "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
+//# See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
+//######################################################################
+fsm::fsm(int P, int M, int L)
+{
+  d_I=M;
+  d_S=(int)(pow(1.0*M,1.0*L-1)+0.5)*P;
+  d_O=(int)(pow(1.0*M,1.0*L)+0.5)*P;
+
+  d_NS.resize(d_I*d_S);
+  d_OS.resize(d_I*d_S);
+  int nv;
+  for(int s=0;s<d_S;s++) {
+    for(int i=0;i<d_I;i++) {
+      int s1=s/P;
+      int v=s%P;
+      int ns1= (i*(int)(pow(1.0*M,1.0*(L-1))+0.5)+s1)/M;
+      if (L==1)
+        nv=(i+v)%P;
+      else
+        nv=(s1%M+v)%P;
+      d_NS[s*d_I+i] = ns1*P+nv;
+      d_OS[s*d_I+i] = i*d_S+s;
+    }
+  }
+
+  generate_PS_PI();
+  generate_TM();
+}
+
+
+
+
+
+
+
+
+
+
+//######################################################################
+//# Automatically generate an FSM specification describing the 
+//# the joint trellis of fsm1 and fsm2
+//######################################################################
+fsm::fsm(const fsm &FSM1, const fsm &FSM2)
+{
+  d_I=FSM1.I()*FSM2.I();
+  d_S=FSM1.S()*FSM2.S();
+  d_O=FSM1.O()*FSM2.O();
+
+  d_NS.resize(d_I*d_S);
+  d_OS.resize(d_I*d_S);
+
+  for(int s=0;s<d_S;s++) {
+    for(int i=0;i<d_I;i++) {
+      int s1=s/FSM2.S();
+      int s2=s%FSM2.S();
+      int i1=i/FSM2.I();
+      int i2=i%FSM2.I();
+      d_NS[s*d_I+i] = FSM1.NS()[s1 * FSM1.I() + i1] * FSM2.S() + FSM2.NS()[s2 * FSM2.I() + i2];
+      d_OS[s*d_I+i] = FSM1.OS()[s1 * FSM1.I() + i1] * FSM2.O() + FSM2.OS()[s2 * FSM2.I() + i2];
+    }
+  }
+
+  generate_PS_PI();
+  generate_TM();
+}
+
+
+
+
+//######################################################################
+//# Generate a new FSM representing n stages through the original FSM
+//# AKA radix-n FSM
+//######################################################################
+fsm::fsm(const fsm &FSM, int n)
+{
+  d_I=(int) (pow(1.0*FSM.I(),1.0*n)+0.5);
+  d_S=FSM.S();
+  d_O=(int) (pow(1.0*FSM.O(),1.0*n)+0.5);
+
+  d_NS.resize(d_I*d_S);
+  d_OS.resize(d_I*d_S);
+
+  for(int s=0;s<d_S;s++ ) {
+    for(int i=0;i<d_I;i++ ) {
+      std::vector<int> ii(n);
+      dec2base(i,FSM.I(),ii);
+      std::vector<int> oo(n);
+      int ns=s;
+      for(int k=0;k<n;k++) {
+        oo[k]=FSM.OS()[ns*FSM.I()+ii[k]];
+        ns=FSM.NS()[ns*FSM.I()+ii[k]];
+      }
+      d_NS[s*d_I+i]=ns;
+      d_OS[s*d_I+i]=base2dec(oo,FSM.O());
+    }
+  }
+
+  generate_PS_PI();
+  generate_TM();
+}
+
+
+
+
+
+
+
+
+
 //######################################################################
 //# generate the PS and PI tables for later use
 //######################################################################
 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 +417,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);
+    }
   }
 }
 
@@ -314,10 +455,92 @@ bool fsm::find_es(int es)
 
 
 
+//######################################################################
+//#  generate trellis representation of FSM as an SVG file
+//######################################################################
+void fsm::write_trellis_svg( std::string filename ,int number_stages)
+{
+   std::ofstream trellis_fname (filename.c_str());
+   if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
+   const int TRELLIS_Y_OFFSET = 30;
+   const int TRELLIS_X_OFFSET = 20;
+   const int STAGE_LABEL_Y_OFFSET = 25;
+   const int STAGE_LABEL_X_OFFSET = 20;
+   const int STATE_LABEL_Y_OFFSET = 30;
+   const int STATE_LABEL_X_OFFSET = 5;
+   const int STAGE_STATE_OFFSETS = 10;
+//   std::cout << "################## BEGIN SVG TRELLIS PIC #####################" << std::endl;
+   trellis_fname << "<svg viewBox = \"0 0 200 200\" version = \"1.1\">" << std::endl;
+
+    for( int stage_num = 0;stage_num < number_stages;stage_num ++){
+    // draw states
+      for ( int state_num = 0;state_num < d_S ; state_num ++ ) {
+        trellis_fname << "<circle cx = \"" << stage_num * STAGE_STATE_OFFSETS + TRELLIS_X_OFFSET << 
+        "\" cy = \"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" r = \"1\"/>" << std::endl;
+      //draw branches
+        if(stage_num != number_stages-1){
+          for( int branch_num = 0;branch_num < d_I; branch_num++){
+            trellis_fname << "<line x1 =\"" << STAGE_STATE_OFFSETS * stage_num+ TRELLIS_X_OFFSET  << "\" ";
+            trellis_fname << "y1 =\"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET<< "\" ";
+            trellis_fname << "x2 =\"" <<  STAGE_STATE_OFFSETS *stage_num + STAGE_STATE_OFFSETS+ TRELLIS_X_OFFSET << "\" ";
+            trellis_fname << "y2 =\"" << d_NS[d_I * state_num + branch_num] * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" ";
+            trellis_fname << " stroke-dasharray = \"3," <<  branch_num << "\" ";
+            trellis_fname << " stroke = \"black\" stroke-width = \"0.3\"/>" << std::endl;
+          }
+        }
+      }
+    }
+  // label the stages
+  trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
+  for( int stage_num = 0;stage_num < number_stages ;stage_num ++){
+    trellis_fname << "<text x = \"" << stage_num * STAGE_STATE_OFFSETS + STAGE_LABEL_X_OFFSET << 
+      "\" y = \""  << STAGE_LABEL_Y_OFFSET  << "\" >" << std::endl;
+    trellis_fname << stage_num <<  std::endl;
+    trellis_fname << "</text>" << std::endl;
+  }
+  trellis_fname << "</g>" << std::endl;
+
+  // label the states
+  trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
+  for( int state_num = 0;state_num < d_S ; state_num ++){
+    trellis_fname << "<text y = \"" << state_num * STAGE_STATE_OFFSETS + STATE_LABEL_Y_OFFSET << 
+      "\" x = \""  << STATE_LABEL_X_OFFSET  << "\" >" << std::endl;
+    trellis_fname << state_num <<  std::endl;
+    trellis_fname << "</text>" << std::endl;
+  }
+  trellis_fname << "</g>" << std::endl;
+
 
+  trellis_fname << "</svg>" << std::endl;
+//  std::cout << "################## END SVG TRELLIS PIC ##################### " << std::endl;
+  trellis_fname.close();
+}
 
 
 
 
 
 
+//######################################################################
+//# Write trellis specification to a text file,
+//# in the same format used when reading FSM files
+//######################################################################
+void fsm::write_fsm_txt(std::string filename)
+{
+   std::ofstream trellis_fname (filename.c_str());
+   if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
+   trellis_fname << d_I << ' ' << d_S << ' ' << d_O << std::endl;
+   trellis_fname << std::endl;
+   for(int i=0;i<d_S;i++) {
+     for(int j=0;j<d_I;j++)  trellis_fname << d_NS[i*d_I+j] << ' ';
+     trellis_fname << std::endl;
+   }
+   trellis_fname << std::endl;
+   for(int i=0;i<d_S;i++) {
+     for(int j=0;j<d_I;j++) trellis_fname << d_OS[i*d_I+j] << ' ';
+     trellis_fname << std::endl;
+   }
+   trellis_fname << std::endl;
+   trellis_fname.close();
+}
+