git.gag.com Git - debian/gnuradio/blob - gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2006 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., 51 Franklin Street,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 #ifndef INCLUDED_DECODER_VITERBI_H
  24 #define INCLUDED_DECODER_VITERBI_H
  25
  26 #include "decoder.h"
  27 #include "encoder_convolutional.h"
  28
  29 class decoder_viterbi : public decoder
  30 {
  31 public:
  32 /*!
  33  * \brief Decode the incoming metrics streams using the Viterbi algorithm.
  34  *
  35  * input: streams of metrics, 2 streams per n_code_outputs - one each for
  36  *     a 0- and 1-bit metric.
  37  *
  38  * output: streams of char, one stream per n_code_inputs, using only
  39  *     the right-most justified bit as the single bit per output item.
  40  *
  41  * sample_precision: precision of the incoming metrics
  42  *     if == 0, then use soft precision (32 bit float);
  43  *     otherwise, use an integer up to 32 bits, already sign-extended
  44  *     to the nearest power-of-2-sized type (char, short, long).
  45  *
  46  * l_encoder: pointer to an encoder class from which to determine the
  47  *     trellis transitions (states and i/o bits).
  48  */
  49
  50   decoder_viterbi (int sample_precision,
  51                    const encoder_convolutional* l_encoder);
  52
  53   virtual ~decoder_viterbi ();
  54
  55 protected:
  56 /*
  57  * state_t: describes a given memory state
  58  *
  59  * d_connections:  a pointer to an array of these structures
  60  *     will be used to describes a given time-bit's memory state;
  61  *     an entry will be referenced via "state_add_to", to find the
  62  *     connections to the next time-bit memory states.  There is
  63  *     one entry per each input bit combination -> 2^#I connections in all.
  64  *     e.g. [0] means the all 0 input;
  65  *     [1] means that input #1 was 1 while all the others were 0;
  66  *     [2] means that input #2 was 1, while all the others were 0;
  67  *     [3] means that inputs #1 and #2 were 1, while the others were 0.
  68  *
  69  * d_max_metric: the maximum metric thus far for this state
  70  *
  71  * d_max_state: the state from which the maximum metric was attained
  72  *
  73  * d_max_input: the input bits from which the maximum metric was attained
  74  */
  75
  76   typedef struct state_t {
  77     struct state_t* d_connections;
  78     float d_max_metric;
  79     int d_max_state_ndx;
  80     int d_max_input;
  81   } state_t, *state_t_ptr;
  82
  83 /*
  84  * state_get_from(v,i,k): use to retrieve a given bit-memory state,
  85  *     from the inputs:
  86  *
  87  * memory_t v: the value from which to retrieve the given state
  88  * size_t i: for which input stream (0 to #I-1)
  89  * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
  90  */
  91
  92   inline memory_t state_get_from (memory_t v,
  93                                   size_t i,
  94                                   size_t k)
  95   {return (((v)>>((i)*(k)))&((1<<(k))-1));};
  96
  97 /*
  98  * state_add_to(s,v,i,k): use to create a given bit-memory state,
  99  *     from the inputs:
 100  *
 101  * memory_t s: the state value to modify
 102  * memory_t v: value to set the state to for this input
 103  * size_t i: for which input stream (0 to #I-1)
 104  * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
 105  */
 106
 107   inline void state_add_to (memory_t s,
 108                             memory_t v,
 109                             size_t i,
 110                             size_t k)
 111   {(s)|=(((v)&((1<<(k))-1))<<((i)*(k)));};
 112
 113 /*
 114  * fsm_dec_viterbi_t: finite state machine for the Viterbi decoder
 115  *
 116  * fsm_dec_viterbi_init: initialize for a new block / block; this is
 117  *     already done at instantiation, so do it only at the end of a
 118  *     block.
 119  *
 120  * fsm_dec_viterbi_doing_up: encoding at the start of a block
 121  *
 122  * fsm_dec_viterbi_doing_middle: doing encoding inside the trellis
 123  *
 124  * fsm_dec_viterbi_doing_term: termination trellis, if requested
 125  */
 126
 127   enum fsm_dec_viterbi_t {
 128     fsm_dec_viterbi_init, fsm_dec_viterbi_doing_up,
 129     fsm_dec_viterbi_doing_middle, fsm_dec_viterbi_doing_term
 130   };
 131
 132   virtual void decode_private ();
 133 #if 0
 134   virtual void decode_loop (size_t* which_counter, size_t how_many);
 135 #endif
 136   virtual void get_next_inputs () {
 137     d_in_buf->read_items ((void*)(&(d_current_inputs[0])));
 138     d_in_buf->increment_indices ();
 139   };
 140   virtual void write_output_bits () {
 141     d_out_buf->write_items ((void*)(&(d_current_outputs[0])));
 142     d_out_buf->increment_indices ();
 143   };
 144
 145   void encode_loop_up ();
 146
 147   virtual void update_traceback__up (size_t from_state_ndx,
 148                                      size_t to_state_ndx,
 149                                      size_t l_input) = 0;
 150   virtual void update_traceback__middle () = 0;
 151   virtual void update_traceback__term () = 0;
 152
 153   void reset_metrics (u_char which);
 154   void zero_metrics (u_char which);
 155
 156   encoder_convolutional* d_encoder;
 157   code_convolutional_trellis* d_trellis;
 158   fsm_dec_viterbi_t d_fsm_state;
 159
 160   size_t d_time_count, d_n_total_inputs_per_stream;
 161   size_t d_n_saved_bits, d_n_saved_bits_start_ndx, d_n_traceback_els;
 162   size_t d_n_states, d_n_input_combinations, d_total_n_delays;
 163   size_t d_states_ndx, d_up_term_ndx;
 164   bool d_do_termination;
 165 #if 1
 166   state_t_ptr d_states[2];
 167   size_t* d_up_term_states_ndx[2];
 168   char **d_save_buffer;
 169 #else
 170   std::vector<state_t> d_states[2];
 171   std::vector<size_t> d_up_term_states_ndx[2];
 172   std::vector<char **> d_save_buffer;  ???
 173 #endif
 174
 175   // "inputs" are the current input symbols as soft-floats, to be
 176   // converted to metrics internally
 177
 178   std::vector<float> d_current_inputs;
 179
 180   // "outputs" are the current output bits, in the LSB (&1) of each "char"
 181
 182   std::vector<char> d_current_outputs;
 183 };
 184
 185 #endif /* INCLUDED_DECODER_VITERBI_H */