git.gag.com Git - debian/gnuradio/blob - gr-trellis/src/lib/trellis_viterbi_s.cc

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2004 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio
   6  *
   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)
  10  * any later version.
  11  *
  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.
  16  *
  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.
  21  */
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include "config.h"
  25 #endif
  26
  27 #include <trellis_viterbi_s.h>
  28 #include <gr_io_signature.h>
  29 #include <assert.h>
  30 #include <iostream>
  31
  32 static const float INF = 1.0e9;
  33
  34 trellis_viterbi_s_sptr
  35 trellis_make_viterbi_s (
  36     const fsm &FSM,
  37     int K,
  38     int S0,
  39     int SK)
  40 {
  41   return trellis_viterbi_s_sptr (new trellis_viterbi_s (FSM,K,S0,SK));
  42 }
  43
  44 trellis_viterbi_s::trellis_viterbi_s (
  45     const fsm &FSM,
  46     int K,
  47     int S0,
  48     int SK)
  49   : gr_block ("viterbi_s",
  50                           gr_make_io_signature (1, -1, sizeof (float)),
  51                           gr_make_io_signature (1, -1, sizeof (short))),
  52   d_FSM (FSM),
  53   d_K (K),
  54   d_S0 (S0),
  55   d_SK (SK),
  56   d_trace(FSM.S()*K)
  57 {
  58     set_relative_rate (1.0 / ((double) d_FSM.O()));
  59     set_output_multiple (d_K);
  60 }
  61
  62
  63 void
  64 trellis_viterbi_s::forecast (int noutput_items, gr_vector_int &ninput_items_required)
  65 {
  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;
  71   }
  72 }
  73
  74
  75
  76
  77 void viterbi_algorithm(int I, int S, 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,
  82              int K,
  83              int S0,int SK,
  84              const float *in, short *out,
  85              std::vector<int> &trace)
  86 {
  87   std::vector<float> alpha(S*2);
  88   int alphai;
  89   float norm,mm,minm;
  90   int minmi;
  91   int st;
  92
  93
  94   if(S0<0) { // initial state not specified
  95       for(int i=0;i<S;i++) alpha[0*S+i]=0;
  96   }
  97   else {
  98       for(int i=0;i<S;i++) alpha[0*S+i]=INF;
  99       alpha[0*S+S0]=0.0;
 100   }
 101
 102   alphai=0;
 103   for(int k=0;k<K;k++) {
 104       norm=INF;
 105       for(int j=0;j<S;j++) { // for each next state do ACS
 106           minm=INF;
 107           minmi=0;
 108           for(int i=0;i<I;i++) {
 109               int i0 = j*I+i;
 110               if((mm=alpha[alphai*S+PS[i0]]+in[k*O+OS[PS[i0]*I+PI[i0]]])<minm)
 111                   minm=mm,minmi=i;
 112           }
 113           trace[k*S+j]=minmi;
 114           alpha[((alphai+1)%2)*S+j]=minm;
 115           if(minm<norm) norm=minm;
 116       }
 117       for(int j=0;j<S;j++)
 118           alpha[((alphai+1)%2)*S+j]-=norm; // normalize total metrics so they do not explode
 119       alphai=(alphai+1)%2;
 120   }
 121
 122   if(SK<0) { // final state not specified
 123       minm=INF;
 124       minmi=0;
 125       for(int i=0;i<S;i++)
 126           if((mm=alpha[alphai*S+i])<minm) minm=mm,minmi=i;
 127       st=minmi;
 128   }
 129   else {
 130       st=SK;
 131   }
 132
 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];
 136       st=PS[i0];
 137   }
 138
 139 }
 140
 141
 142
 143
 144
 145
 146 int
 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)
 151 {
 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;
 156
 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);
 162     }
 163   }
 164
 165   consume_each (d_FSM.O() * noutput_items );
 166   return noutput_items;
 167 }