3 * Copyright 2004 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.
27 #include <trellis_siso_f.h>
28 #include <gr_io_signature.h>
33 static const float INF = 1.0e9;
43 trellis_siso_type_t SISO_TYPE)
45 return trellis_siso_f_sptr (new trellis_siso_f (FSM,K,S0,SK,POSTI,POSTO,SISO_TYPE));
48 trellis_siso_f::trellis_siso_f (
55 trellis_siso_type_t SISO_TYPE)
57 gr_make_io_signature (1, -1, sizeof (float)),
58 gr_make_io_signature (1, -1, sizeof (float))),
65 d_SISO_TYPE (SISO_TYPE)//,
66 //d_alpha(FSM.S()*(K+1)),
67 //d_beta(FSM.S()*(K+1))
70 if (d_POSTI && d_POSTO)
71 multiple = d_FSM.I()+d_FSM.O();
77 throw std::runtime_error ("Not both POSTI and POSTO can be false.");
78 //printf("constructor: Multiple = %d\n",multiple);
79 set_output_multiple (d_K*multiple);
80 //what is the meaning of relative rate for a block with 2 inputs?
81 //set_relative_rate ( multiple / ((double) d_FSM.I()) );
82 // it turns out that the above gives problems in the scheduler, so
83 // let's try (assumption O>I)
84 //set_relative_rate ( multiple / ((double) d_FSM.O()) );
85 // I am tempted to automate like this
86 if(d_FSM.I() <= d_FSM.O())
87 set_relative_rate ( multiple / ((double) d_FSM.O()) );
89 set_relative_rate ( multiple / ((double) d_FSM.I()) );
94 trellis_siso_f::forecast (int noutput_items, gr_vector_int &ninput_items_required)
97 if (d_POSTI && d_POSTO)
98 multiple = d_FSM.I()+d_FSM.O();
100 multiple = d_FSM.I();
102 multiple = d_FSM.O();
104 throw std::runtime_error ("Not both POSTI and POSTO can be false.");
105 //printf("forecast: Multiple = %d\n",multiple);
106 assert (noutput_items % (d_K*multiple) == 0);
107 int input_required1 = d_FSM.I() * (noutput_items/multiple) ;
108 int input_required2 = d_FSM.O() * (noutput_items/multiple) ;
109 //printf("forecast: Output requirements: %d\n",noutput_items);
110 //printf("forecast: Input requirements: %d %d\n",input_required1,input_required2);
111 unsigned ninputs = ninput_items_required.size();
112 assert(ninputs % 2 == 0);
113 for (unsigned int i = 0; i < ninputs/2; i++) {
114 ninput_items_required[2*i] = input_required1;
115 ninput_items_required[2*i+1] = input_required2;
119 inline float min(float a, float b)
121 return a <= b ? a : b;
124 inline float min_star(float a, float b)
126 return (a <= b ? a : b)-log(1+exp(a <= b ? a-b : b-a));
129 void siso_algorithm(int I, int S, int O,
130 const std::vector<int> &NS,
131 const std::vector<int> &OS,
132 const std::vector< std::vector<int> > &PS,
133 const std::vector< std::vector<int> > &PI,
136 bool POSTI, bool POSTO,
137 float (*p2mymin)(float,float),
138 const float *priori, const float *prioro, float *post//,
139 //std::vector<float> &alpha,
140 //std::vector<float> &beta
144 std::vector<float> alpha(S*(K+1));
145 std::vector<float> beta(S*(K+1));
148 if(S0<0) { // initial state not specified
149 for(int i=0;i<S;i++) alpha[0*S+i]=0;
152 for(int i=0;i<S;i++) alpha[0*S+i]=INF;
156 for(int k=0;k<K;k++) { // forward recursion
158 for(int j=0;j<S;j++) {
160 for(unsigned int i=0;i<PS[j].size();i++) {
162 mm=alpha[k*S+PS[j][i]]+priori[k*I+PI[j][i]]+prioro[k*O+OS[PS[j][i]*I+PI[j][i]]];
163 minm=(*p2mymin)(minm,mm);
165 alpha[(k+1)*S+j]=minm;
166 if(minm<norm) norm=minm;
169 alpha[(k+1)*S+j]-=norm; // normalize total metrics so they do not explode
172 if(SK<0) { // final state not specified
173 for(int i=0;i<S;i++) beta[K*S+i]=0;
176 for(int i=0;i<S;i++) beta[K*S+i]=INF;
180 for(int k=K-1;k>=0;k--) { // backward recursion
182 for(int j=0;j<S;j++) {
184 for(int i=0;i<I;i++) {
186 mm=beta[(k+1)*S+NS[i0]]+priori[k*I+i]+prioro[k*O+OS[i0]];
187 minm=(*p2mymin)(minm,mm);
190 if(minm<norm) norm=minm;
193 beta[k*S+j]-=norm; // normalize total metrics so they do not explode
199 for(int k=0;k<K;k++) { // input combining
201 for(int i=0;i<I;i++) {
203 for(int j=0;j<S;j++) {
204 mm=alpha[k*S+j]+prioro[k*O+OS[j*I+i]]+beta[(k+1)*S+NS[j*I+i]];
205 minm=(*p2mymin)(minm,mm);
207 post[k*(I+O)+i]=minm;
208 if(minm<norm) norm=minm;
211 post[k*(I+O)+i]-=norm; // normalize metrics
215 for(int k=0;k<K;k++) { // output combining
217 for(int n=0;n<O;n++) {
219 for(int j=0;j<S;j++) {
220 for(int i=0;i<I;i++) {
221 mm= (n==OS[j*I+i] ? alpha[k*S+j]+priori[k*I+i]+beta[(k+1)*S+NS[j*I+i]] : INF);
222 minm=(*p2mymin)(minm,mm);
225 post[k*(I+O)+I+n]=minm;
226 if(minm<norm) norm=minm;
229 post[k*(I+O)+I+n]-=norm; // normalize metrics
234 for(int k=0;k<K;k++) { // input combining
236 for(int i=0;i<I;i++) {
238 for(int j=0;j<S;j++) {
239 mm=alpha[k*S+j]+prioro[k*O+OS[j*I+i]]+beta[(k+1)*S+NS[j*I+i]];
240 minm=(*p2mymin)(minm,mm);
243 if(minm<norm) norm=minm;
246 post[k*I+i]-=norm; // normalize metrics
251 for(int k=0;k<K;k++) { // output combining
253 for(int n=0;n<O;n++) {
255 for(int j=0;j<S;j++) {
256 for(int i=0;i<I;i++) {
257 mm= (n==OS[j*I+i] ? alpha[k*S+j]+priori[k*I+i]+beta[(k+1)*S+NS[j*I+i]] : INF);
258 minm=(*p2mymin)(minm,mm);
262 if(minm<norm) norm=minm;
265 post[k*O+n]-=norm; // normalize metrics
269 throw std::runtime_error ("Not both POSTI and POSTO can be false.");
279 trellis_siso_f::general_work (int noutput_items,
280 gr_vector_int &ninput_items,
281 gr_vector_const_void_star &input_items,
282 gr_vector_void_star &output_items)
284 assert (input_items.size() == 2*output_items.size());
285 int nstreams = output_items.size();
286 //printf("general_work:Streams: %d\n",nstreams);
288 if (d_POSTI && d_POSTO)
289 multiple = d_FSM.I()+d_FSM.O();
291 multiple = d_FSM.I();
293 multiple = d_FSM.O();
295 throw std::runtime_error ("Not both POSTI and POSTO can be false.");
297 assert (noutput_items % (d_K*multiple) == 0);
298 int nblocks = noutput_items / (d_K*multiple);
299 //printf("general_work:Blocks: %d\n",nblocks);
300 //for(int i=0;i<ninput_items.size();i++)
301 //printf("general_work:Input items available: %d\n",ninput_items[i]);
303 float (*p2min)(float, float) = NULL;
304 if(d_SISO_TYPE == TRELLIS_MIN_SUM)
306 else if(d_SISO_TYPE == TRELLIS_SUM_PRODUCT)
310 for (int m=0;m<nstreams;m++) {
311 const float *in1 = (const float *) input_items[2*m];
312 const float *in2 = (const float *) input_items[2*m+1];
313 float *out = (float *) output_items[m];
314 for (int n=0;n<nblocks;n++) {
315 siso_algorithm(d_FSM.I(),d_FSM.S(),d_FSM.O(),
316 d_FSM.NS(),d_FSM.OS(),d_FSM.PS(),d_FSM.PI(),
320 &(in1[n*d_K*d_FSM.I()]),&(in2[n*d_K*d_FSM.O()]),
321 &(out[n*d_K*multiple])//,
327 for (unsigned int i = 0; i < input_items.size()/2; i++) {
328 consume(2*i,d_FSM.I() * noutput_items / multiple );
329 consume(2*i+1,d_FSM.O() * noutput_items / multiple );
332 return noutput_items;