3 * Copyright 2002 Free Software Foundation, Inc.
5 * This file is part of GNU Radio
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)
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.
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.
47 fsm::fsm(const fsm &FSM)
54 d_PS=FSM.PS(); // is this going to make a deep copy?
60 fsm::fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS)
72 //######################################################################
73 //# Read an FSM specification from a file.
74 //# Format (hopefully will become more flexible in the future...):
75 //# I S O (in the first line)
77 //# Next state matrix (S lines, each with I integers separated by spaces)
79 //# output symbol matrix (S lines, each with I integers separated by spaces)
81 //######################################################################
82 fsm::fsm(const char *name)
86 if((fsmfile=fopen(name,"r"))==NULL)
87 throw std::runtime_error ("fsm::fsm(const char *name): file open error\n");
88 //printf("file open error in fsm()\n");
90 if(fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O) == EOF) {
91 if(ferror(fsmfile) != 0)
92 throw std::runtime_error ("fsm::fsm(const char *name): file read error\n");
98 for(int i=0;i<d_S;i++) {
99 for(int j=0;j<d_I;j++) {
100 if(fscanf(fsmfile,"%d",&(d_NS[i*d_I+j])) == EOF) {
101 if(ferror(fsmfile) != 0)
102 throw std::runtime_error ("fsm::fsm(const char *name): file read error\n");
106 for(int i=0;i<d_S;i++) {
107 for(int j=0;j<d_I;j++) {
108 if(fscanf(fsmfile,"%d",&(d_OS[i*d_I+j])) == EOF) {
109 if(ferror(fsmfile) != 0)
110 throw std::runtime_error ("fsm::fsm(const char *name): file read error\n");
121 //######################################################################
122 //# Automatically generate the FSM from the generator matrix
123 //# of a (n,k) binary convolutional code
124 //######################################################################
125 fsm::fsm(int k, int n, const std::vector<int> &G)
128 // calculate maximum memory requirements for each input stream
129 std::vector<int> max_mem_x(k,-1);
131 for(int i=0;i<k;i++) {
132 for(int j=0;j<n;j++) {
135 mem=(int)(log(G[i*n+j])/log(2.0));
143 //printf("max_mem_x\n");
144 //for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
146 // calculate total memory requirements to set S
149 sum_max_mem += max_mem_x[i];
151 //printf("sum_max_mem = %d\n",sum_max_mem);
157 // binary representation of the G matrix
158 std::vector<std::vector<int> > Gb(k*n);
159 for(int j=0;j<k*n;j++) {
160 Gb[j].resize(max_mem+1);
161 dec2base(G[j],2,Gb[j]);
163 //for(int m=0;m<Gb[j].size();m++) printf("%d ",Gb[j][m]); printf("\n");
166 // alphabet size of each shift register
167 std::vector<int> bases_x(k);
168 for(int j=0;j<k ;j++)
169 bases_x[j] = 1 << max_mem_x[j];
170 //printf("bases_x\n");
171 //for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
173 d_NS.resize(d_I*d_S);
174 d_OS.resize(d_I*d_S);
176 std::vector<int> sx(k);
177 std::vector<int> nsx(k);
178 std::vector<int> tx(k);
179 std::vector<std::vector<int> > tb(k);
181 tb[j].resize(max_mem+1);
182 std::vector<int> inb(k);
183 std::vector<int> outb(n);
186 for(int s=0;s<d_S;s++) {
187 dec2bases(s,bases_x,sx); // split s into k values, each representing one of the k shift registers
188 //printf("state = %d \nstates = ",s);
189 //for(int j=0;j<sx.size();j++) printf("%d ",sx[j]); printf("\n");
190 for(int i=0;i<d_I;i++) {
191 dec2base(i,2,inb); // input in binary
192 //printf("input = %d \ninputs = ",i);
193 //for(int j=0;j<inb.size();j++) printf("%d ",inb[j]); printf("\n");
195 // evaluate next state
197 nsx[j] = (inb[j]*bases_x[j]+sx[j])/2; // next state (for each shift register) MSB first
198 d_NS[s*d_I+i]=bases2dec(nsx,bases_x); // collect all values into the new state
200 // evaluate transitions
202 tx[j] = inb[j]*bases_x[j]+sx[j]; // transition (for each shift register)MSB first
203 for(int j=0;j<k;j++) {
204 dec2base(tx[j],2,tb[j]); // transition in binary
205 //printf("transition = %d \ntransitions = ",tx[j]);
206 //for(int m=0;m<tb[j].size();m++) printf("%d ",tb[j][m]); printf("\n");
210 for(int nn=0;nn<n;nn++) {
212 for(int j=0;j<k;j++) {
213 for(int m=0;m<max_mem+1;m++)
214 outb[nn] = (outb[nn] + Gb[j*n+nn][m]*tb[j][m]) % 2; // careful: polynomial 1+D ir represented as 110, not as 011
215 //printf("output %d equals %d\n",nn,outb[nn]);
218 d_OS[s*d_I+i] = base2dec(outb,2);
229 //######################################################################
230 //# Automatically generate an FSM specification describing the
231 //# ISI for a channel
232 //# of length ch_length and a modulation of size mod_size
233 //######################################################################
234 fsm::fsm(int mod_size, int ch_length)
237 d_S=(int) (pow(1.0*d_I,1.0*ch_length-1)+0.5);
240 d_NS.resize(d_I*d_S);
241 d_OS.resize(d_I*d_S);
243 for(int s=0;s<d_S;s++) {
244 for(int i=0;i<d_I;i++) {
246 d_NS[s*d_I+i] = t/d_I;
258 //######################################################################
259 //# Automatically generate an FSM specification describing the
260 //# the trellis for a CPM with h=K/P (relatively prime),
261 //# alphabet size M, and frequency pulse duration L symbols
263 //# This FSM is based on the paper by B. Rimoldi
264 //# "A decomposition approach to CPM", IEEE Trans. Info Theory, March 1988
265 //# See also my own notes at http://www.eecs.umich.edu/~anastas/docs/cpm.pdf
266 //######################################################################
267 fsm::fsm(int P, int M, int L)
270 d_S=(int)(pow(1.0*M,1.0*L-1)+0.5)*P;
271 d_O=(int)(pow(1.0*M,1.0*L)+0.5)*P;
273 d_NS.resize(d_I*d_S);
274 d_OS.resize(d_I*d_S);
276 for(int s=0;s<d_S;s++) {
277 for(int i=0;i<d_I;i++) {
280 int ns1= (i*(int)(pow(1.0*M,1.0*(L-1))+0.5)+s1)/M;
285 d_NS[s*d_I+i] = ns1*P+nv;
286 d_OS[s*d_I+i] = i*d_S+s;
303 //######################################################################
304 //# Automatically generate an FSM specification describing the
305 //# the joint trellis of fsm1 and fsm2
306 //######################################################################
307 fsm::fsm(const fsm &FSM1, const fsm &FSM2)
309 d_I=FSM1.I()*FSM2.I();
310 d_S=FSM1.S()*FSM2.S();
311 d_O=FSM1.O()*FSM2.O();
313 d_NS.resize(d_I*d_S);
314 d_OS.resize(d_I*d_S);
316 for(int s=0;s<d_S;s++) {
317 for(int i=0;i<d_I;i++) {
322 d_NS[s*d_I+i] = FSM1.NS()[s1 * FSM1.I() + i1] * FSM2.S() + FSM2.NS()[s2 * FSM2.I() + i2];
323 d_OS[s*d_I+i] = FSM1.OS()[s1 * FSM1.I() + i1] * FSM2.O() + FSM2.OS()[s2 * FSM2.I() + i2];
334 //######################################################################
335 //# Generate a new FSM representing n stages through the original FSM
337 //######################################################################
338 fsm::fsm(const fsm &FSM, int n)
340 d_I=(int) (pow(1.0*FSM.I(),1.0*n)+0.5);
342 d_O=(int) (pow(1.0*FSM.O(),1.0*n)+0.5);
344 d_NS.resize(d_I*d_S);
345 d_OS.resize(d_I*d_S);
347 for(int s=0;s<d_S;s++ ) {
348 for(int i=0;i<d_I;i++ ) {
349 std::vector<int> ii(n);
350 dec2base(i,FSM.I(),ii);
351 std::vector<int> oo(n);
353 for(int k=0;k<n;k++) {
354 oo[k]=FSM.OS()[ns*FSM.I()+ii[k]];
355 ns=FSM.NS()[ns*FSM.I()+ii[k]];
358 d_OS[s*d_I+i]=base2dec(oo,FSM.O());
374 //######################################################################
375 //# generate the PS and PI tables for later use
376 //######################################################################
377 void fsm::generate_PS_PI()
382 for(int i=0;i<d_S;i++) {
383 d_PS[i].resize(d_I*d_S); // max possible size
384 d_PI[i].resize(d_I*d_S);
386 for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
387 if(d_NS[ii*d_I+jj]!=i) continue;
398 //######################################################################
399 //# generate the termination matrices TMl and TMi for later use
400 //######################################################################
401 void fsm::generate_TM()
403 d_TMi.resize(d_S*d_S);
404 d_TMl.resize(d_S*d_S);
406 for(int i=0;i<d_S*d_S;i++) {
407 d_TMi[i] = -1; // no meaning
408 d_TMl[i] = d_S; //infinity: you need at most S-1 steps
413 for(int s=0;s<d_S;s++) {
416 while (done == false && attempts < d_S-1) {
421 //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be disconnected\n");
422 printf("fsm::generate_TM(): FSM appears to be disconnected\n");
423 printf("state %d cannot be reached from all other states\n",s);
429 // find a path from any state to the ending state "es"
430 bool fsm::find_es(int es)
433 for(int s=0;s<d_S;s++) {
434 if(d_TMl[s*d_S+es] < d_S)
438 for(int i=0;i<d_I;i++) {
439 if( 1 + d_TMl[d_NS[s*d_I+i]*d_S+es] < minl) {
440 minl = 1 + d_TMl[d_NS[s*d_I+i]*d_S+es];
445 d_TMl[s*d_S+es]=minl;
446 d_TMi[s*d_S+es]=mini;
458 //######################################################################
459 //# generate trellis representation of FSM as an SVG file
460 //######################################################################
461 void fsm::write_trellis_svg( std::string filename ,int number_stages)
463 std::ofstream trellis_fname (filename.c_str());
464 if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
465 const int TRELLIS_Y_OFFSET = 30;
466 const int TRELLIS_X_OFFSET = 20;
467 const int STAGE_LABEL_Y_OFFSET = 25;
468 const int STAGE_LABEL_X_OFFSET = 20;
469 const int STATE_LABEL_Y_OFFSET = 30;
470 const int STATE_LABEL_X_OFFSET = 5;
471 const int STAGE_STATE_OFFSETS = 10;
472 // std::cout << "################## BEGIN SVG TRELLIS PIC #####################" << std::endl;
473 trellis_fname << "<svg viewBox = \"0 0 200 200\" version = \"1.1\">" << std::endl;
475 for( int stage_num = 0;stage_num < number_stages;stage_num ++){
477 for ( int state_num = 0;state_num < d_S ; state_num ++ ) {
478 trellis_fname << "<circle cx = \"" << stage_num * STAGE_STATE_OFFSETS + TRELLIS_X_OFFSET <<
479 "\" cy = \"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" r = \"1\"/>" << std::endl;
481 if(stage_num != number_stages-1){
482 for( int branch_num = 0;branch_num < d_I; branch_num++){
483 trellis_fname << "<line x1 =\"" << STAGE_STATE_OFFSETS * stage_num+ TRELLIS_X_OFFSET << "\" ";
484 trellis_fname << "y1 =\"" << state_num * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET<< "\" ";
485 trellis_fname << "x2 =\"" << STAGE_STATE_OFFSETS *stage_num + STAGE_STATE_OFFSETS+ TRELLIS_X_OFFSET << "\" ";
486 trellis_fname << "y2 =\"" << d_NS[d_I * state_num + branch_num] * STAGE_STATE_OFFSETS + TRELLIS_Y_OFFSET << "\" ";
487 trellis_fname << " stroke-dasharray = \"3," << branch_num << "\" ";
488 trellis_fname << " stroke = \"black\" stroke-width = \"0.3\"/>" << std::endl;
494 trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
495 for( int stage_num = 0;stage_num < number_stages ;stage_num ++){
496 trellis_fname << "<text x = \"" << stage_num * STAGE_STATE_OFFSETS + STAGE_LABEL_X_OFFSET <<
497 "\" y = \"" << STAGE_LABEL_Y_OFFSET << "\" >" << std::endl;
498 trellis_fname << stage_num << std::endl;
499 trellis_fname << "</text>" << std::endl;
501 trellis_fname << "</g>" << std::endl;
504 trellis_fname << "<g font-size = \"4\" font= \"times\" fill = \"black\">" << std::endl;
505 for( int state_num = 0;state_num < d_S ; state_num ++){
506 trellis_fname << "<text y = \"" << state_num * STAGE_STATE_OFFSETS + STATE_LABEL_Y_OFFSET <<
507 "\" x = \"" << STATE_LABEL_X_OFFSET << "\" >" << std::endl;
508 trellis_fname << state_num << std::endl;
509 trellis_fname << "</text>" << std::endl;
511 trellis_fname << "</g>" << std::endl;
514 trellis_fname << "</svg>" << std::endl;
515 // std::cout << "################## END SVG TRELLIS PIC ##################### " << std::endl;
516 trellis_fname.close();
524 //######################################################################
525 //# Write trellis specification to a text file,
526 //# in the same format used when reading FSM files
527 //######################################################################
528 void fsm::write_fsm_txt(std::string filename)
530 std::ofstream trellis_fname (filename.c_str());
531 if (!trellis_fname) {std::cout << "file not found " << std::endl ; exit(-1);}
532 trellis_fname << d_I << ' ' << d_S << ' ' << d_O << std::endl;
533 trellis_fname << std::endl;
534 for(int i=0;i<d_S;i++) {
535 for(int j=0;j<d_I;j++) trellis_fname << d_NS[i*d_I+j] << ' ';
536 trellis_fname << std::endl;
538 trellis_fname << std::endl;
539 for(int i=0;i<d_S;i++) {
540 for(int j=0;j<d_I;j++) trellis_fname << d_OS[i*d_I+j] << ' ';
541 trellis_fname << std::endl;
543 trellis_fname << std::endl;
544 trellis_fname.close();