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., 59 Temple Place - Suite 330,
  20  * Boston, MA 02111-1307, 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                    encoder_convolutional* l_encoder);
  52
  53   virtual ~decoder_viterbi ();
  54
  55 protected:
  56   struct state_t;
  57
  58 /*
  59  * connection_t: describes an output connection from the current
  60  *     time-bit memory state to the next time-bit memory state
  61  *
  62  * d_to: state pointer to which this connection going
  63  *
  64  * d_to_ndx: index of the "to" state
  65  *
  66  * d_output_bits: what are the output bits, coverted into
  67  *     1->+1.0, 0->-1.0, for this connection
  68  */
  69
  70   typedef struct connection_t {
  71     struct state_t *d_to;
  72     int d_to_ndx;
  73     float* d_output_bits;
  74   } connection_t, *connection_t_ptr;
  75
  76 /*
  77  * state_t: describes a given memory state
  78  *
  79  * d_connections:  a pointer to an array of these structures
  80  *     will be used to describes a given time-bit's memory state;
  81  *     an entry will be referenced via "state_add_to", to find the
  82  *     connections to the next time-bit memory states.  There is
  83  *     one entry per each input bit combination -> 2^#I connections in all.
  84  *     e.g. [0] means the all 0 input;
  85  *     [1] means that input #1 was 1 while all the others were 0;
  86  *     [2] means that input #2 was 1, while all the others were 0;
  87  *     [3] means that inputs #1 and #2 were 1, while the others were 0.
  88  *
  89  * d_max_metric: the maximum metric thus far for this state
  90  *
  91  * d_max_state: the state from which the maximum metric was attained
  92  *
  93  * d_max_input: the input bits from which the maximum metric was attained
  94  */
  95
  96   typedef struct state_t {
  97     connection_t_ptr d_connections;
  98     float d_max_metric;
  99     int d_max_state_ndx;
 100     int d_max_input;
 101   } state_t, *state_t_ptr;
 102
 103 /*
 104  * state_get_from(v,i,k): use to retrieve a given bit-memory state,
 105  *     from the inputs:
 106  *
 107  * memory_t v: the value from which to retrieve the given state
 108  * size_t i: for which input stream (0 to #I-1)
 109  * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
 110  */
 111
 112   inline memory_t state_get_from (memory_t v,
 113                                   size_t i,
 114                                   size_t k)
 115   {return (((v)>>((i)*(k)))&((1<<(k))-1));};
 116
 117 /*
 118  * state_add_to(s,v,i,k): use to create a given bit-memory state,
 119  *     from the inputs:
 120  *
 121  * memory_t s: the state value to modify
 122  * memory_t v: value to set the state to for this input
 123  * size_t i: for which input stream (0 to #I-1)
 124  * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
 125  */
 126
 127   inline void state_add_to (memory_t s,
 128                             memory_t v,
 129                             size_t i,
 130                             size_t k)
 131   {(s)|=(((v)&((1<<(k))-1))<<((i)*(k)));};
 132
 133 /*
 134  * fsm_dec_viterbi_t: finite state machine for the Viterbi decoder
 135  *
 136  * fsm_dec_viterbi_init: initialize for a new block / block; this is
 137  *     already done at instantiation, so do it only at the end of a
 138  *     block.
 139  *
 140  * fsm_dec_viterbi_doing_up: encoding at the start of a block
 141  *
 142  * fsm_dec_viterbi_doing_middle: doing encoding inside the trellis
 143  *
 144  * fsm_dec_viterbi_doing_term: termination trellis, if requested
 145  */
 146
 147   enum fsm_dec_viterbi_t {
 148     fsm_dec_viterbi_init, fsm_dec_viterbi_doing_up,
 149     fsm_dec_viterbi_doing_middle, fsm_dec_viterbi_doing_term
 150   };
 151
 152   virtual void decode_private (const char** in_buf, char** out_buf);
 153   virtual char get_next_input (const char** in_buf, size_t code_input_n);
 154 #if 0
 155   virtual void decode_loop (const char** in_buf, char** out_buf,
 156                             size_t* which_counter, size_t how_many);
 157
 158   virtual char get_next_input__up (const char** in_buf,
 159                                       size_t code_input_n) = 0;
 160   virtual char get_next_input__middle (const char** in_buf,
 161                                           size_t code_input_n) = 0;
 162   virtual char get_next_input__term (size_t code_input_n) = 0;
 163 #endif
 164   virtual void increment_input_indices (bool while_decoding) = 0;
 165   virtual void increment_output_indices (bool while_decoding) = 0;
 166   virtual void update_traceback__up (size_t from_state_ndx,
 167                                      size_t to_state_ndx,
 168                                      size_t l_input) = 0;
 169   virtual void update_traceback__middle () = 0;
 170   virtual void update_traceback__term () = 0;
 171
 172   void reset_metrics (u_char which);
 173   void zero_metrics (u_char which);
 174
 175   encoder_convolutional* d_encoder;
 176   fsm_dec_viterbi_t d_fsm_state;
 177   size_t d_max_memory, d_total_memory;
 178   size_t d_time_count, d_n_total_inputs_per_stream;
 179   size_t d_n_saved_bits, d_n_saved_bits_start_ndx, d_n_traceback_els;
 180   size_t d_n_states, d_n_input_combinations;
 181   size_t d_states_ndx, d_up_term_ndx;
 182   bool d_do_streaming, d_do_termination;
 183   std::vector<memory_t> d_init_states, d_term_states;
 184   char **d_save_buffer;
 185   state_t_ptr d_states[2];
 186   size_t* d_up_term_states_ndx[2];
 187 };
 188
 189 #endif /* INCLUDED_DECODER_VITERBI_H */