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 2, 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.
43 fsm::fsm(const fsm &FSM)
56 fsm::fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS)
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)
73 //# Next state matrix (S lines, each with I integers separated by spaces)
75 //# output symbol matrix (S lines, each with I integers separated by spaces)
77 //######################################################################
78 fsm::fsm(const char *name)
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");
86 fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O);
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]));
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]));
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)
111 // calculate maximum memory requirements for each input stream
112 std::vector<int> max_mem_x(k,-1);
114 for(int i=0;i<k;i++) {
115 for(int j=0;j<n;j++) {
118 mem=(int)(log(G[i*n+j])/log(2.0));
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");
129 // calculate total memory requirements to set S
132 sum_max_mem += max_mem_x[i];
134 //printf("sum_max_mem = %d\n",sum_max_mem);
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]);
146 //for(int m=0;m<Gb[j].size();m++) printf("%d ",Gb[j][m]); printf("\n");
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");
156 d_NS.resize(d_I*d_S);
157 d_OS.resize(d_I*d_S);
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);
164 tb[j].resize(max_mem+1);
165 std::vector<int> inb(k);
166 std::vector<int> outb(n);
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");
178 // evaluate next state
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
183 // evaluate transitions
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");
193 for(int nn=0;nn<n;nn++) {
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]);
201 d_OS[s*d_I+i] = base2dec(outb,2);
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)
220 d_S=(int) (pow(1.0*d_I,1.0*ch_length-1)+0.5);
223 d_NS.resize(d_I*d_S);
224 d_OS.resize(d_I*d_S);
226 for(int s=0;s<d_S;s++) {
227 for(int i=0;i<d_I;i++) {
229 d_NS[s*d_I+i] = t/d_I;
239 //######################################################################
240 //# generate the PS and PI tables for later use
241 //######################################################################
242 void fsm::generate_PS_PI()
244 d_PS.resize(d_I*d_S);
245 d_PI.resize(d_I*d_S);
247 for(int i=0;i<d_S;i++) {
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;
259 //######################################################################
260 //# generate the termination matrices TMl and TMi for later use
261 //######################################################################
262 void fsm::generate_TM()
264 d_TMi.resize(d_S*d_S);
265 d_TMl.resize(d_S*d_S);
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
274 for(int s=0;s<d_S;s++) {
277 while (done == false && attempts < d_S-1) {
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");
288 // find a path from any state to the ending state "es"
289 bool fsm::find_es(int es)
292 for(int s=0;s<d_S;s++) {
293 if(d_TMl[s*d_S+es] < d_S)
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];
304 d_TMl[s*d_S+es]=minl;
305 d_TMi[s*d_S+es]=mini;