git.gag.com Git - debian/gnuradio/blob - gr-trellis/src/lib/fsm.cc

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2002 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 #include <cstdio>
  24 #include <string>
  25 #include <iostream>
  26 #include <fstream>
  27 #include <stdexcept>
  28 #include <cmath>
  29 #include "base.h"
  30 #include "fsm.h"
  31
  32
  33 fsm::fsm()
  34 {
  35   d_I=0;
  36   d_S=0;
  37   d_O=0;
  38   d_NS.resize(0);
  39   d_OS.resize(0);
  40   d_PS.resize(0);
  41   d_PI.resize(0);
  42   d_TMi.resize(0);
  43   d_TMl.resize(0);
  44 }
  45
  46 fsm::fsm(const fsm &FSM)
  47 {
  48   d_I=FSM.I();
  49   d_S=FSM.S();
  50   d_O=FSM.O();
  51   d_NS=FSM.NS();
  52   d_OS=FSM.OS();
  53   d_PS=FSM.PS(); // is this going to make a deep copy?
  54   d_PI=FSM.PI();
  55   d_TMi=FSM.TMi();
  56   d_TMl=FSM.TMl();
  57 }
  58
  59 fsm::fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS)
  60 {
  61   d_I=I;
  62   d_S=S;
  63   d_O=O;
  64   d_NS=NS;
  65   d_OS=OS;
  66
  67   generate_PS_PI();
  68   generate_TM();
  69 }
  70
  71 //######################################################################
  72 //# Read an FSM specification from a file.
  73 //# Format (hopefully will become more flexible in the future...):
  74 //# I S O (in the first line)
  75 //# blank line
  76 //# Next state matrix (S lines, each with I integers separated by spaces)
  77 //# blank line
  78 //# output symbol matrix (S lines, each with I integers separated by spaces)
  79 //# optional comments
  80 //######################################################################
  81 fsm::fsm(const char *name)
  82 {
  83   FILE *fsmfile;
  84
  85   if((fsmfile=fopen(name,"r"))==NULL)
  86     throw std::runtime_error ("fsm::fsm(const char *name): file open error\n");
  87     //printf("file open error in fsm()\n");
  88
  89   fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O);
  90   d_NS.resize(d_I*d_S);
  91   d_OS.resize(d_I*d_S);
  92
  93   for(int i=0;i<d_S;i++) {
  94     for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_NS[i*d_I+j]));
  95   }
  96   for(int i=0;i<d_S;i++) {
  97     for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_OS[i*d_I+j]));
  98   }
  99
 100   generate_PS_PI();
 101   generate_TM();
 102 }
 103
 104
 105
 106 //######################################################################
 107 //# Automatically generate the FSM from the generator matrix
 108 //# of a (n,k) binary convolutional code
 109 //######################################################################
 110 fsm::fsm(int k, int n, const std::vector<int> &G)
 111 {
 112
 113   // calculate maximum memory requirements for each input stream
 114   std::vector<int> max_mem_x(k,-1);
 115   int max_mem = -1;
 116   for(int i=0;i<k;i++) {
 117     for(int j=0;j<n;j++) {
 118       int mem = -1;
 119       if(G[i*n+j]!=0)
 120         mem=(int)(log(G[i*n+j])/log(2.0));
 121       if(mem>max_mem_x[i])
 122         max_mem_x[i]=mem;
 123       if(mem>max_mem)
 124         max_mem=mem;
 125     }
 126   }
 127
 128 //printf("max_mem_x\n");
 129 //for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
 130
 131   // calculate total memory requirements to set S
 132   int sum_max_mem = 0;
 133   for(int i=0;i<k;i++)
 134     sum_max_mem += max_mem_x[i];
 135
 136 //printf("sum_max_mem = %d\n",sum_max_mem);
 137
 138   d_I=1<<k;
 139   d_S=1<<sum_max_mem;
 140   d_O=1<<n;
 141
 142   // binary representation of the G matrix
 143   std::vector<std::vector<int> > Gb(k*n);
 144   for(int j=0;j<k*n;j++) {
 145     Gb[j].resize(max_mem+1);
 146     dec2base(G[j],2,Gb[j]);
 147 //printf("Gb\n");
 148 //for(int m=0;m<Gb[j].size();m++) printf("%d ",Gb[j][m]); printf("\n");
 149   }
 150
 151   // alphabet size of each shift register
 152   std::vector<int> bases_x(k);
 153   for(int j=0;j<k ;j++)
 154     bases_x[j] = 1 << max_mem_x[j];
 155 //printf("bases_x\n");
 156 //for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
 157
 158   d_NS.resize(d_I*d_S);
 159   d_OS.resize(d_I*d_S);
 160
 161   std::vector<int> sx(k);
 162   std::vector<int> nsx(k);
 163   std::vector<int> tx(k);
 164   std::vector<std::vector<int> > tb(k);
 165   for(int j=0;j<k;j++)
 166     tb[j].resize(max_mem+1);
 167   std::vector<int> inb(k);
 168   std::vector<int> outb(n);
 169
 170
 171   for(int s=0;s<d_S;s++) {
 172     dec2bases(s,bases_x,sx); // split s into k values, each representing on of the k shift registers
 173 //printf("state = %d \nstates = ",s);
 174 //for(int j=0;j<sx.size();j++) printf("%d ",sx[j]); printf("\n");
 175     for(int i=0;i<d_I;i++) {
 176       dec2base(i,2,inb); // input in binary
 177 //printf("input = %d \ninputs = ",i);
 178 //for(int j=0;j<inb.size();j++) printf("%d ",inb[j]); printf("\n");
 179
 180       // evaluate next state
 181       for(int j=0;j<k;j++)
 182         nsx[j] = (inb[j]*bases_x[j]+sx[j])/2; // next state (for each shift register) MSB first
 183       d_NS[s*d_I+i]=bases2dec(nsx,bases_x); // collect all values into the new state
 184
 185       // evaluate transitions
 186       for(int j=0;j<k;j++)
 187         tx[j] = inb[j]*bases_x[j]+sx[j]; // transition (for each shift register)MSB first
 188       for(int j=0;j<k;j++) {
 189         dec2base(tx[j],2,tb[j]); // transition in binary
 190 //printf("transition = %d \ntransitions = ",tx[j]);
 191 //for(int m=0;m<tb[j].size();m++) printf("%d ",tb[j][m]); printf("\n");
 192       }
 193
 194       // evaluate outputs
 195       for(int nn=0;nn<n;nn++) {
 196         outb[nn] = 0;
 197         for(int j=0;j<k;j++) {
 198           for(int m=0;m<max_mem+1;m++)
 199             outb[nn] = (outb[nn] + Gb[j*n+nn][m]*tb[j][m]) % 2; // careful: polynomial 1+D ir represented as 110, not as 011
 200 //printf("output %d equals %d\n",nn,outb[nn]);
 201         }
 202       }
 203       d_OS[s*d_I+i] = base2dec(outb,2);
 204     }
 205   }
 206
 207   generate_PS_PI();
 208   generate_TM();
 209 }
 210
 211
 212
 213
 214 //######################################################################
 215 //# Automatically generate an FSM specification describing the
 216 //# ISI for a channel
 217 //# of length ch_length and a modulation of size mod_size
 218 //######################################################################
 219 fsm::fsm(int mod_size, int ch_length)
 220 {
 221   d_I=mod_size;
 222   d_S=(int) (pow(1.0*d_I,1.0*ch_length-1)+0.5);
 223   d_O=d_S*d_I;
 224
 225   d_NS.resize(d_I*d_S);
 226   d_OS.resize(d_I*d_S);
 227
 228   for(int s=0;s<d_S;s++) {
 229     for(int i=0;i<d_I;i++) {
 230       int t=i*d_S+s;
 231       d_NS[s*d_I+i] = t/d_I;
 232       d_OS[s*d_I+i] = t;
 233     }
 234   }
 235
 236   generate_PS_PI();
 237   generate_TM();
 238 }
 239
 240
 241 //######################################################################
 242 //# generate the PS and PI tables for later use
 243 //######################################################################
 244 void fsm::generate_PS_PI()
 245 {
 246   d_PS.resize(d_S);
 247   d_PI.resize(d_S);
 248
 249   for(int i=0;i<d_S;i++) {
 250     d_PS[i].resize(d_I*d_S); // max possible size
 251     d_PI[i].resize(d_I*d_S);
 252     int j=0;
 253     for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
 254       if(d_NS[ii*d_I+jj]!=i) continue;
 255       d_PS[i][j]=ii;
 256       d_PI[i][j]=jj;
 257       j++;
 258     }
 259     d_PS[i].resize(j);
 260     d_PI[i].resize(j);
 261   }
 262 }
 263
 264
 265 //######################################################################
 266 //# generate the termination matrices TMl and TMi for later use
 267 //######################################################################
 268 void fsm::generate_TM()
 269 {
 270   d_TMi.resize(d_S*d_S);
 271   d_TMl.resize(d_S*d_S);
 272
 273   for(int i=0;i<d_S*d_S;i++) {
 274     d_TMi[i] = -1; // no meaning
 275     d_TMl[i] = d_S; //infinity: you need at most S-1 steps
 276     if (i/d_S == i%d_S)
 277       d_TMl[i] = 0;
 278   }
 279
 280   for(int s=0;s<d_S;s++) {
 281     bool done = false;
 282     int attempts = 0;
 283     while (done == false && attempts < d_S-1) {
 284       done = find_es(s);
 285       attempts ++;
 286     }
 287     if (done == false) {
 288       //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be disconnected\n");
 289       printf("fsm::generate_TM(): FSM appears to be disconnected\n");
 290       printf("state %d cannot be reached from all other states\n",s);
 291     }
 292   }
 293 }
 294
 295
 296 // find a path from any state to the ending state "es"
 297 bool fsm::find_es(int es)
 298 {
 299   bool done = true;
 300   for(int s=0;s<d_S;s++) {
 301     if(d_TMl[s*d_S+es] < d_S)
 302       continue;
 303     int minl=d_S;
 304     int mini=-1;
 305     for(int i=0;i<d_I;i++) {
 306       if( 1 + d_TMl[d_NS[s*d_I+i]*d_S+es] < minl) {
 307         minl = 1 + d_TMl[d_NS[s*d_I+i]*d_S+es];
 308         mini = i;
 309       }
 310     }
 311     if (mini != -1) {
 312       d_TMl[s*d_S+es]=minl;
 313       d_TMi[s*d_S+es]=mini;
 314     }
 315     else
 316       done = false;
 317   }
 318   return done;
 319 }
 320
 321
 322
 323
 324
 325 //######################################################################
 326 //#  generate trellis representation of FSM as an SVG file
 327 //######################################################################
 328 void fsm::write_trellis_svg( std::string filename ,int number_stages)
 329 {
 330    std::ofstream trellis_fname (filename.c_str());
 331    if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
 332    const int TRELLIS_Y_OFFSET = 30;
 333    const int TRELLIS_X_OFFSET = 20;
 334    const int STAGE_LABEL_Y_OFFSET = 25;
 335    const int STAGE_LABEL_X_OFFSET = 20;
 336    const int STATE_LABEL_Y_OFFSET = 30;
 337    const int STATE_LABEL_X_OFFSET = 5;
 338    const int STAGE_STATE_OFFSETS = 10;
 339 //   std::cout << "################## BEGIN SVG TRELLIS PIC #####################" << std::endl;
 340    trellis_fname << "<svg viewBox = \"0 0 200 200\" version = \"1.1\">" << std::endl;
 341
 342     for( int stage_num = 0;stage_num < number_stages;stage_num ++){
 343     // draw states
 344       for ( int state_num = 0;state_num < d_S ; state_num ++ ) {
 345         trellis_fname << "<circle cx = \"" << stage_num * STAGE_STATE_OFFSETS + TRELLIS_X_OFFSET <<
 346         "\" cy = \"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" r = \"1\"/>" << std::endl;
 347       //draw branches
 348         if(stage_num != number_stages-1){
 349           for( int branch_num = 0;branch_num < d_I; branch_num++){
 350             trellis_fname << "<line x1 =\"" << STAGE_STATE_OFFSETS * stage_num+ TRELLIS_X_OFFSET  << "\" ";
 351             trellis_fname << "y1 =\"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET<< "\" ";
 352             trellis_fname << "x2 =\"" <<  STAGE_STATE_OFFSETS *stage_num + STAGE_STATE_OFFSETS+ TRELLIS_X_OFFSET << "\" ";
 353             trellis_fname << "y2 =\"" << d_NS[d_I * state_num + branch_num] * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" ";
 354             trellis_fname << " stroke-dasharray = \"3," <<  branch_num << "\" ";
 355             trellis_fname << " stroke = \"black\" stroke-width = \"0.3\"/>" << std::endl;
 356           }
 357         }
 358       }
 359     }
 360   // label the stages
 361   trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
 362   for( int stage_num = 0;stage_num < number_stages ;stage_num ++){
 363     trellis_fname << "<text x = \"" << stage_num * STAGE_STATE_OFFSETS + STAGE_LABEL_X_OFFSET <<
 364       "\" y = \""  << STAGE_LABEL_Y_OFFSET  << "\" >" << std::endl;
 365     trellis_fname << stage_num <<  std::endl;
 366     trellis_fname << "</text>" << std::endl;
 367   }
 368   trellis_fname << "</g>" << std::endl;
 369
 370   // label the states
 371   trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
 372   for( int state_num = 0;state_num < d_S ; state_num ++){
 373     trellis_fname << "<text y = \"" << state_num * STAGE_STATE_OFFSETS + STATE_LABEL_Y_OFFSET <<
 374       "\" x = \""  << STATE_LABEL_X_OFFSET  << "\" >" << std::endl;
 375     trellis_fname << state_num <<  std::endl;
 376     trellis_fname << "</text>" << std::endl;
 377   }
 378   trellis_fname << "</g>" << std::endl;
 379
 380
 381   trellis_fname << "</svg>" << std::endl;
 382 //  std::cout << "################## END SVG TRELLIS PIC ##################### " << std::endl;
 383   trellis_fname.close();
 384 }
 385
 386
 387
 388
 389
 390
 391 //######################################################################
 392 //# Write trellis specification to a text files,
 393 //# in the same format used when reading FSM files
 394 //######################################################################
 395 void fsm::write_fsm_txt(std::string filename)
 396 {
 397    std::ofstream trellis_fname (filename.c_str());
 398    if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
 399    trellis_fname << d_I << ' ' << d_S << ' ' << d_O << std::endl;
 400    trellis_fname << std::endl;
 401    for(int i=0;i<d_S;i++) {
 402      for(int j=0;j<d_I;j++)  trellis_fname << d_NS[i*d_I+j] << ' ';
 403      trellis_fname << std::endl;
 404    }
 405    trellis_fname << std::endl;
 406    for(int i=0;i<d_S;i++) {
 407      for(int j=0;j<d_I;j++) trellis_fname << d_OS[i*d_I+j] << ' ';
 408      trellis_fname << std::endl;
 409    }
 410    trellis_fname << std::endl;
 411    trellis_fname.close();
 412 }
 413