← Back to branch summary

~ubuntu-branches/ubuntu/trusty/gnuradio/trusty

« back to all changes in this revision

Viewing changes to gr-trellis/src/lib/fsm.cc

  • Committer: Bazaar Package Importer
  • Author(s): Kamal Mostafa
  • Date: 2010-03-13 07:46:01 UTC
  • mfrom: (2.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20100313074601-zjsa893a87bozyh7
Tags: 3.2.2.dfsg-1ubuntu1
https://launchpad.net/bugs/260406
* Fix build for Ubuntu lucid (LP: #260406)
  - add binary package dep for libusrp0, libusrp2-0: adduser
  - debian/rules clean: remove pre-built Qt moc files

Show diffs side-by-side

added added

removed removed

Lines of Context:
gr-trellis/src/lib/fsm.cc
21
21
 */
22
22
 
23
23
#include <cstdio>
 
24
#include <string>
 
25
#include <iostream>
 
26
#include <fstream>
24
27
#include <stdexcept>
25
28
#include <cmath>
 
29
#include <stdlib.h>
26
30
#include "base.h"
27
31
#include "fsm.h"
28
32
 
47
51
  d_O=FSM.O();
48
52
  d_NS=FSM.NS();
49
53
  d_OS=FSM.OS();
50
 
  d_PS=FSM.PS();
 
54
  d_PS=FSM.PS(); // is this going to make a deep copy?
51
55
  d_PI=FSM.PI();
52
56
  d_TMi=FSM.TMi();
53
57
  d_TMl=FSM.TMl();
100
104
 
101
105
 
102
106
 
103
 
 
104
107
//######################################################################
105
108
//# Automatically generate the FSM from the generator matrix
106
109
//# of a (n,k) binary convolutional code
167
170
 
168
171
 
169
172
  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
 
173
    dec2bases(s,bases_x,sx); // split s into k values, each representing one of the k shift registers
171
174
//printf("state = %d \nstates = ",s);
172
175
//for(int j=0;j<sx.size();j++) printf("%d ",sx[j]); printf("\n");
173
176
    for(int i=0;i<d_I;i++) {
236
239
}
237
240
 
238
241
 
 
242
 
 
243
 
 
244
//######################################################################
 
245
//# Automatically generate an FSM specification describing the 
 
246
//# the trellis for a CPM with h=K/P (relatively prime), 
 
247
//# alphabet size M, and frequency pulse duration L symbols
 
248
//#
 
249
//# This FSM is based on the paper by B. Rimoldi
 
250
//# "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
 
251
//# See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
 
252
//######################################################################
 
253
fsm::fsm(int P, int M, int L)
 
254
{
 
255
  d_I=M;
 
256
  d_S=(int)(pow(1.0*M,1.0*L-1)+0.5)*P;
 
257
  d_O=(int)(pow(1.0*M,1.0*L)+0.5)*P;
 
258
 
 
259
  d_NS.resize(d_I*d_S);
 
260
  d_OS.resize(d_I*d_S);
 
261
  int nv;
 
262
  for(int s=0;s<d_S;s++) {
 
263
    for(int i=0;i<d_I;i++) {
 
264
      int s1=s/P;
 
265
      int v=s%P;
 
266
      int ns1= (i*(int)(pow(1.0*M,1.0*(L-1))+0.5)+s1)/M;
 
267
      if (L==1)
 
268
        nv=(i+v)%P;
 
269
      else
 
270
        nv=(s1%M+v)%P;
 
271
      d_NS[s*d_I+i] = ns1*P+nv;
 
272
      d_OS[s*d_I+i] = i*d_S+s;
 
273
    }
 
274
  }
 
275
 
 
276
  generate_PS_PI();
 
277
  generate_TM();
 
278
}
 
279
 
 
280
 
 
281
 
 
282
 
 
283
 
 
284
 
 
285
 
 
286
 
 
287
 
 
288
 
 
289
//######################################################################
 
290
//# Automatically generate an FSM specification describing the 
 
291
//# the joint trellis of fsm1 and fsm2
 
292
//######################################################################
 
293
fsm::fsm(const fsm &FSM1, const fsm &FSM2)
 
294
{
 
295
  d_I=FSM1.I()*FSM2.I();
 
296
  d_S=FSM1.S()*FSM2.S();
 
297
  d_O=FSM1.O()*FSM2.O();
 
298
 
 
299
  d_NS.resize(d_I*d_S);
 
300
  d_OS.resize(d_I*d_S);
 
301
 
 
302
  for(int s=0;s<d_S;s++) {
 
303
    for(int i=0;i<d_I;i++) {
 
304
      int s1=s/FSM2.S();
 
305
      int s2=s%FSM2.S();
 
306
      int i1=i/FSM2.I();
 
307
      int i2=i%FSM2.I();
 
308
      d_NS[s*d_I+i] = FSM1.NS()[s1 * FSM1.I() + i1] * FSM2.S() + FSM2.NS()[s2 * FSM2.I() + i2];
 
309
      d_OS[s*d_I+i] = FSM1.OS()[s1 * FSM1.I() + i1] * FSM2.O() + FSM2.OS()[s2 * FSM2.I() + i2];
 
310
    }
 
311
  }
 
312
 
 
313
  generate_PS_PI();
 
314
  generate_TM();
 
315
}
 
316
 
 
317
 
 
318
 
 
319
 
 
320
//######################################################################
 
321
//# Generate a new FSM representing n stages through the original FSM
 
322
//# AKA radix-n FSM
 
323
//######################################################################
 
324
fsm::fsm(const fsm &FSM, int n)
 
325
{
 
326
  d_I=(int) (pow(1.0*FSM.I(),1.0*n)+0.5);
 
327
  d_S=FSM.S();
 
328
  d_O=(int) (pow(1.0*FSM.O(),1.0*n)+0.5);
 
329
 
 
330
  d_NS.resize(d_I*d_S);
 
331
  d_OS.resize(d_I*d_S);
 
332
 
 
333
  for(int s=0;s<d_S;s++ ) {
 
334
    for(int i=0;i<d_I;i++ ) {
 
335
      std::vector<int> ii(n);
 
336
      dec2base(i,FSM.I(),ii);
 
337
      std::vector<int> oo(n);
 
338
      int ns=s;
 
339
      for(int k=0;k<n;k++) {
 
340
        oo[k]=FSM.OS()[ns*FSM.I()+ii[k]];
 
341
        ns=FSM.NS()[ns*FSM.I()+ii[k]];
 
342
      }
 
343
      d_NS[s*d_I+i]=ns;
 
344
      d_OS[s*d_I+i]=base2dec(oo,FSM.O());
 
345
    }
 
346
  }
 
347
 
 
348
  generate_PS_PI();
 
349
  generate_TM();
 
350
}
 
351
 
 
352
 
 
353
 
 
354
 
 
355
 
 
356
 
 
357
 
 
358
 
 
359
 
239
360
//######################################################################
240
361
//# generate the PS and PI tables for later use
241
362
//######################################################################
242
363
void fsm::generate_PS_PI()
243
364
{
244
 
  d_PS.resize(d_I*d_S);
245
 
  d_PI.resize(d_I*d_S);
 
365
  d_PS.resize(d_S);
 
366
  d_PI.resize(d_S);
246
367
 
247
368
  for(int i=0;i<d_S;i++) {
 
369
    d_PS[i].resize(d_I*d_S); // max possible size
 
370
    d_PI[i].resize(d_I*d_S);
248
371
    int j=0;
249
372
    for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
250
373
      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;
 
374
      d_PS[i][j]=ii;
 
375
      d_PI[i][j]=jj;
253
376
      j++;
254
377
    }
 
378
    d_PS[i].resize(j);
 
379
    d_PI[i].resize(j);
255
380
  }
256
381
}
257
382
 
278
403
      done = find_es(s);
279
404
      attempts ++;
280
405
    }
281
 
    if (done == false)
 
406
    if (done == false) {
282
407
      //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be disconnected\n");
283
408
      printf("fsm::generate_TM(): FSM appears to be disconnected\n");
 
409
      printf("state %d cannot be reached from all other states\n",s);
 
410
    }
284
411
  }
285
412
}
286
413
 
314
441
 
315
442
 
316
443
 
317
 
 
318
 
 
319
 
 
320
 
 
321
 
 
322
 
 
 
444
//######################################################################
 
445
//#  generate trellis representation of FSM as an SVG file
 
446
//######################################################################
 
447
void fsm::write_trellis_svg( std::string filename ,int number_stages)
 
448
{
 
449
   std::ofstream trellis_fname (filename.c_str());
 
450
   if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
 
451
   const int TRELLIS_Y_OFFSET = 30;
 
452
   const int TRELLIS_X_OFFSET = 20;
 
453
   const int STAGE_LABEL_Y_OFFSET = 25;
 
454
   const int STAGE_LABEL_X_OFFSET = 20;
 
455
   const int STATE_LABEL_Y_OFFSET = 30;
 
456
   const int STATE_LABEL_X_OFFSET = 5;
 
457
   const int STAGE_STATE_OFFSETS = 10;
 
458
//   std::cout << "################## BEGIN SVG TRELLIS PIC #####################" << std::endl;
 
459
   trellis_fname << "<svg viewBox = \"0 0 200 200\" version = \"1.1\">" << std::endl;
 
460
 
 
461
    for( int stage_num = 0;stage_num < number_stages;stage_num ++){
 
462
    // draw states
 
463
      for ( int state_num = 0;state_num < d_S ; state_num ++ ) {
 
464
        trellis_fname << "<circle cx = \"" << stage_num * STAGE_STATE_OFFSETS + TRELLIS_X_OFFSET << 
 
465
        "\" cy = \"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" r = \"1\"/>" << std::endl;
 
466
      //draw branches
 
467
        if(stage_num != number_stages-1){
 
468
          for( int branch_num = 0;branch_num < d_I; branch_num++){
 
469
            trellis_fname << "<line x1 =\"" << STAGE_STATE_OFFSETS * stage_num+ TRELLIS_X_OFFSET  << "\" ";
 
470
            trellis_fname << "y1 =\"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET<< "\" ";
 
471
            trellis_fname << "x2 =\"" <<  STAGE_STATE_OFFSETS *stage_num + STAGE_STATE_OFFSETS+ TRELLIS_X_OFFSET << "\" ";
 
472
            trellis_fname << "y2 =\"" << d_NS[d_I * state_num + branch_num] * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" ";
 
473
            trellis_fname << " stroke-dasharray = \"3," <<  branch_num << "\" ";
 
474
            trellis_fname << " stroke = \"black\" stroke-width = \"0.3\"/>" << std::endl;
 
475
          }
 
476
        }
 
477
      }
 
478
    }
 
479
  // label the stages
 
480
  trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
 
481
  for( int stage_num = 0;stage_num < number_stages ;stage_num ++){
 
482
    trellis_fname << "<text x = \"" << stage_num * STAGE_STATE_OFFSETS + STAGE_LABEL_X_OFFSET << 
 
483
      "\" y = \""  << STAGE_LABEL_Y_OFFSET  << "\" >" << std::endl;
 
484
    trellis_fname << stage_num <<  std::endl;
 
485
    trellis_fname << "</text>" << std::endl;
 
486
  }
 
487
  trellis_fname << "</g>" << std::endl;
 
488
 
 
489
  // label the states
 
490
  trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
 
491
  for( int state_num = 0;state_num < d_S ; state_num ++){
 
492
    trellis_fname << "<text y = \"" << state_num * STAGE_STATE_OFFSETS + STATE_LABEL_Y_OFFSET << 
 
493
      "\" x = \""  << STATE_LABEL_X_OFFSET  << "\" >" << std::endl;
 
494
    trellis_fname << state_num <<  std::endl;
 
495
    trellis_fname << "</text>" << std::endl;
 
496
  }
 
497
  trellis_fname << "</g>" << std::endl;
 
498
 
 
499
 
 
500
  trellis_fname << "</svg>" << std::endl;
 
501
//  std::cout << "################## END SVG TRELLIS PIC ##################### " << std::endl;
 
502
  trellis_fname.close();
 
503
}
 
504
 
 
505
 
 
506
 
 
507
 
 
508
 
 
509
 
 
510
//######################################################################
 
511
//# Write trellis specification to a text file,
 
512
//# in the same format used when reading FSM files
 
513
//######################################################################
 
514
void fsm::write_fsm_txt(std::string filename)
 
515
{
 
516
   std::ofstream trellis_fname (filename.c_str());
 
517
   if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
 
518
   trellis_fname << d_I << ' ' << d_S << ' ' << d_O << std::endl;
 
519
   trellis_fname << std::endl;
 
520
   for(int i=0;i<d_S;i++) {
 
521
     for(int j=0;j<d_I;j++)  trellis_fname << d_NS[i*d_I+j] << ' ';
 
522
     trellis_fname << std::endl;
 
523
   }
 
524
   trellis_fname << std::endl;
 
525
   for(int i=0;i<d_S;i++) {
 
526
     for(int j=0;j<d_I;j++) trellis_fname << d_OS[i*d_I+j] << ' ';
 
527
     trellis_fname << std::endl;
 
528
   }
 
529
   trellis_fname << std::endl;
 
530
   trellis_fname.close();
 
531
}
323
532