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 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., 59 Temple Place - Suite 330,
20 * Boston, MA 02111-1307, USA.
27 #include <trellis_viterbi_s.h>
28 #include <gr_io_signature.h>
32 static const float INF = 1.0e9;
34 trellis_viterbi_s_sptr
35 trellis_make_viterbi_s (
41 return trellis_viterbi_s_sptr (new trellis_viterbi_s (FSM,K,S0,SK));
44 trellis_viterbi_s::trellis_viterbi_s (
49 : gr_block ("viterbi_s",
50 gr_make_io_signature (1, -1, sizeof (float)),
51 gr_make_io_signature (1, -1, sizeof (short))),
58 set_relative_rate (1.0 / ((double) d_FSM.O()));
59 set_output_multiple (d_K);
64 trellis_viterbi_s::forecast (int noutput_items, gr_vector_int &ninput_items_required)
66 assert (noutput_items % d_K == 0);
67 int input_required = d_FSM.O() * noutput_items ;
68 unsigned ninputs = ninput_items_required.size();
69 for (unsigned int i = 0; i < ninputs; i++) {
70 ninput_items_required[i] = input_required;
77 void viterbi_algorithm(const int I, const int S, const int O,
78 const std::vector<int> &NS,
79 const std::vector<int> &OS,
80 const std::vector<int> &PS,
81 const std::vector<int> &PI,
83 const int S0,const int SK,
84 const float *in, short *out,
85 std::vector<int> &trace)
87 std::vector<float> alpha(S*2);
94 if(S0<0) { // initial state not specified
95 for(int i=0;i<S;i++) alpha[0*S+i]=0;
98 for(int i=0;i<S;i++) alpha[0*S+i]=INF;
103 for(int k=0;k<K;k++) {
105 for(int j=0;j<S;j++) { // for each next state do ACS
108 for(int i=0;i<I;i++) {
110 if((mm=alpha[alphai*S+PS[i0]]+in[k*O+OS[PS[i0]*I+PI[i0]]])<minm)
114 alpha[((alphai+1)%2)*S+j]=minm;
115 if(minm<norm) norm=minm;
118 alpha[((alphai+1)%2)*S+j]-=norm; // normalize total metrics so they do not explode
122 if(SK<0) { // final state not specified
126 if((mm=trace[(K-1)*S+i])<minm) minm=mm,minmi=i;
133 for(int k=K-1;k>=0;k--) { // traceback
134 int i0=st*I+trace[k*S+st];
135 out[k]= (short) PI[i0];
147 trellis_viterbi_s::general_work (int noutput_items,
148 gr_vector_int &ninput_items,
149 gr_vector_const_void_star &input_items,
150 gr_vector_void_star &output_items)
152 assert (input_items.size() == output_items.size());
153 int nstreams = input_items.size();
154 assert (noutput_items % d_K == 0);
155 int nblocks = noutput_items / d_K;
157 for (int m=0;m<nstreams;m++) {
158 const float *in = (const float *) input_items[m];
159 short *out = (short *) output_items[m];
160 for (int n=0;n<nblocks;n++) {
161 viterbi_algorithm(d_FSM.I(),d_FSM.S(),d_FSM.O(),d_FSM.NS(),d_FSM.OS(),d_FSM.PS(),d_FSM.PI(),d_K,d_S0,d_SK,&(in[n*d_K*d_FSM.O()]),&(out[n*d_K]),d_trace);
165 consume_each (d_FSM.O() * noutput_items );
166 return noutput_items;