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 2, 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 <stdexcept>
  25 #include <cmath>
  26 #include "base.h"
  27 #include "fsm.h"
  28
  29
  30 fsm::fsm()
  31 {
  32   d_I=0;
  33   d_S=0;
  34   d_O=0;
  35   d_NS.resize(0);
  36   d_OS.resize(0);
  37   d_PS.resize(0);
  38   d_PI.resize(0);
  39   d_TMi.resize(0);
  40   d_TMl.resize(0);
  41 }
  42
  43 fsm::fsm(const fsm &FSM)
  44 {
  45   d_I=FSM.I();
  46   d_S=FSM.S();
  47   d_O=FSM.O();
  48   d_NS=FSM.NS();
  49   d_OS=FSM.OS();
  50   d_PS=FSM.PS();
  51   d_PI=FSM.PI();
  52   d_TMi=FSM.TMi();
  53   d_TMl=FSM.TMl();
  54 }
  55
  56 fsm::fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS)
  57 {
  58   d_I=I;
  59   d_S=S;
  60   d_O=O;
  61   d_NS=NS;
  62   d_OS=OS;
  63
  64   generate_PS_PI();
  65   generate_TM();
  66 }
  67
  68 //######################################################################
  69 //# Read an FSM specification from a file.
  70 //# Format (hopefully will become more flexible in the future...):
  71 //# I S O (in the first line)
  72 //# blank line
  73 //# Next state matrix (S lines, each with I integers separated by spaces)
  74 //# blank line
  75 //# output symbol matrix (S lines, each with I integers separated by spaces)
  76 //# optional comments
  77 //######################################################################
  78 fsm::fsm(const char *name)
  79 {
  80   FILE *fsmfile;
  81
  82   if((fsmfile=fopen(name,"r"))==NULL)
  83     throw std::runtime_error ("fsm::fsm(const char *name): file open error\n");
  84     //printf("file open error in fsm()\n");
  85
  86   fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O);
  87   d_NS.resize(d_I*d_S);
  88   d_OS.resize(d_I*d_S);
  89
  90   for(int i=0;i<d_S;i++) {
  91     for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_NS[i*d_I+j]));
  92   }
  93   for(int i=0;i<d_S;i++) {
  94     for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_OS[i*d_I+j]));
  95   }
  96
  97   generate_PS_PI();
  98   generate_TM();
  99 }
 100
 101
 102
 103
 104 //######################################################################
 105 //# Automatically generate the FSM from the generator matrix
 106 //# of a (n,k) binary convolutional code
 107 //######################################################################
 108 fsm::fsm(int k, int n, const std::vector<int> &G)
 109 {
 110
 111   // calculate maximum memory requirements for each input stream
 112   std::vector<int> max_mem_x(k,-1);
 113   int max_mem = -1;
 114   for(int i=0;i<k;i++) {
 115     for(int j=0;j<n;j++) {
 116       int mem = -1;
 117       if(G[i*n+j]!=0)
 118         mem=(int)(log(G[i*n+j])/log(2.0));
 119       if(mem>max_mem_x[i])
 120         max_mem_x[i]=mem;
 121       if(mem>max_mem)
 122         max_mem=mem;
 123     }
 124   }
 125
 126 //printf("max_mem_x\n");
 127 //for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
 128
 129   // calculate total memory requirements to set S
 130   int sum_max_mem = 0;
 131   for(int i=0;i<k;i++)
 132     sum_max_mem += max_mem_x[i];
 133
 134 //printf("sum_max_mem = %d\n",sum_max_mem);
 135
 136   d_I=1<<k;
 137   d_S=1<<sum_max_mem;
 138   d_O=1<<n;
 139
 140   // binary representation of the G matrix
 141   std::vector<std::vector<int> > Gb(k*n);
 142   for(int j=0;j<k*n;j++) {
 143     Gb[j].resize(max_mem+1);
 144     dec2base(G[j],2,Gb[j]);
 145 //printf("Gb\n");
 146 //for(int m=0;m<Gb[j].size();m++) printf("%d ",Gb[j][m]); printf("\n");
 147   }
 148
 149   // alphabet size of each shift register
 150   std::vector<int> bases_x(k);
 151   for(int j=0;j<k ;j++)
 152     bases_x[j] = 1 << max_mem_x[j];
 153 //printf("bases_x\n");
 154 //for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
 155
 156   d_NS.resize(d_I*d_S);
 157   d_OS.resize(d_I*d_S);
 158
 159   std::vector<int> sx(k);
 160   std::vector<int> nsx(k);
 161   std::vector<int> tx(k);
 162   std::vector<std::vector<int> > tb(k);
 163   for(int j=0;j<k;j++)
 164     tb[j].resize(max_mem+1);
 165   std::vector<int> inb(k);
 166   std::vector<int> outb(n);
 167
 168
 169   for(int s=0;s<d_S;s++) {
 170     dec2bases(s,bases_x,sx); // split s into k values, each representing on of the k shift registers
 171 //printf("state = %d \nstates = ",s);
 172 //for(int j=0;j<sx.size();j++) printf("%d ",sx[j]); printf("\n");
 173     for(int i=0;i<d_I;i++) {
 174       dec2base(i,2,inb); // input in binary
 175 //printf("input = %d \ninputs = ",i);
 176 //for(int j=0;j<inb.size();j++) printf("%d ",inb[j]); printf("\n");
 177
 178       // evaluate next state
 179       for(int j=0;j<k;j++)
 180         nsx[j] = (inb[j]*bases_x[j]+sx[j])/2; // next state (for each shift register) MSB first
 181       d_NS[s*d_I+i]=bases2dec(nsx,bases_x); // collect all values into the new state
 182
 183       // evaluate transitions
 184       for(int j=0;j<k;j++)
 185         tx[j] = inb[j]*bases_x[j]+sx[j]; // transition (for each shift register)MSB first
 186       for(int j=0;j<k;j++) {
 187         dec2base(tx[j],2,tb[j]); // transition in binary
 188 //printf("transition = %d \ntransitions = ",tx[j]);
 189 //for(int m=0;m<tb[j].size();m++) printf("%d ",tb[j][m]); printf("\n");
 190       }
 191
 192       // evaluate outputs
 193       for(int nn=0;nn<n;nn++) {
 194         outb[nn] = 0;
 195         for(int j=0;j<k;j++) {
 196           for(int m=0;m<max_mem+1;m++)
 197             outb[nn] = (outb[nn] + Gb[j*n+nn][m]*tb[j][m]) % 2; // careful: polynomial 1+D ir represented as 110, not as 011
 198 //printf("output %d equals %d\n",nn,outb[nn]);
 199         }
 200       }
 201       d_OS[s*d_I+i] = base2dec(outb,2);
 202     }
 203   }
 204
 205   generate_PS_PI();
 206   generate_TM();
 207 }
 208
 209
 210
 211
 212 //######################################################################
 213 //# Automatically generate an FSM specification describing the
 214 //# ISI for a channel
 215 //# of length ch_length and a modulation of size mod_size
 216 //######################################################################
 217 fsm::fsm(int mod_size, int ch_length)
 218 {
 219   d_I=mod_size;
 220   d_S=(int) (pow(1.0*d_I,1.0*ch_length-1)+0.5);
 221   d_O=d_S*d_I;
 222
 223   d_NS.resize(d_I*d_S);
 224   d_OS.resize(d_I*d_S);
 225
 226   for(int s=0;s<d_S;s++) {
 227     for(int i=0;i<d_I;i++) {
 228       int t=i*d_S+s;
 229       d_NS[s*d_I+i] = t/d_I;
 230       d_OS[s*d_I+i] = t;
 231     }
 232   }
 233
 234   generate_PS_PI();
 235   generate_TM();
 236 }
 237
 238
 239 //######################################################################
 240 //# generate the PS and PI tables for later use
 241 //######################################################################
 242 void fsm::generate_PS_PI()
 243 {
 244   d_PS.resize(d_I*d_S);
 245   d_PI.resize(d_I*d_S);
 246
 247   for(int i=0;i<d_S;i++) {
 248     int j=0;
 249     for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
 250       if(d_NS[ii*d_I+jj]!=i) continue;
 251       d_PS[i*d_I+j]=ii;
 252       d_PI[i*d_I+j]=jj;
 253       j++;
 254     }
 255   }
 256 }
 257
 258
 259 //######################################################################
 260 //# generate the termination matrices TMl and TMi for later use
 261 //######################################################################
 262 void fsm::generate_TM()
 263 {
 264   d_TMi.resize(d_S*d_S);
 265   d_TMl.resize(d_S*d_S);
 266
 267   for(int i=0;i<d_S*d_S;i++) {
 268     d_TMi[i] = -1; // no meaning
 269     d_TMl[i] = d_S; //infinity: you need at most S-1 steps
 270     if (i/d_S == i%d_S)
 271       d_TMl[i] = 0;
 272   }
 273
 274   for(int s=0;s<d_S;s++) {
 275     bool done = false;
 276     int attempts = 0;
 277     while (done == false && attempts < d_S-1) {
 278       done = find_es(s);
 279       attempts ++;
 280     }
 281     if (done == false)
 282       //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be disconnected\n");
 283       printf("fsm::generate_TM(): FSM appears to be disconnected\n");
 284   }
 285 }
 286
 287
 288 // find a path from any state to the ending state "es"
 289 bool fsm::find_es(int es)
 290 {
 291   bool done = true;
 292   for(int s=0;s<d_S;s++) {
 293     if(d_TMl[s*d_S+es] < d_S)
 294       continue;
 295     int minl=d_S;
 296     int mini=-1;
 297     for(int i=0;i<d_I;i++) {
 298       if( 1 + d_TMl[d_NS[s*d_I+i]*d_S+es] < minl) {
 299         minl = 1 + d_TMl[d_NS[s*d_I+i]*d_S+es];
 300         mini = i;
 301       }
 302     }
 303     if (mini != -1) {
 304       d_TMl[s*d_S+es]=minl;
 305       d_TMi[s*d_S+es]=mini;
 306     }
 307     else
 308       done = false;
 309   }
 310   return done;
 311 }
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323