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

   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 #ifdef HAVE_CONFIG_H
  24 #include "config.h"
  25 #endif
  26
  27 #include "encoder_convolutional.h"
  28 #include <assert.h>
  29 #include <iostream>
  30
  31 #define DO_TIME_THOUGHPUT 0
  32 #define DO_PRINT_DEBUG_FSM 0
  33
  34 #include <mld/mld_timer.h>
  35
  36 void
  37 encoder_convolutional::encoder_convolutional_init
  38 (int block_size_bits,
  39  int n_code_inputs,
  40  int n_code_outputs,
  41  const std::vector<int>& code_generators,
  42  const std::vector<int>* code_feedback,
  43  bool do_termination,
  44  int start_memory_state,
  45  int end_memory_state)
  46 {
  47   // error checking on the input arguments is done by the trellis class
  48
  49   if (code_feedback)
  50     d_trellis = new code_convolutional_trellis
  51       (block_size_bits,
  52        n_code_inputs,
  53        n_code_outputs,
  54        code_generators,
  55        *code_feedback,
  56        do_termination,
  57        end_memory_state);
  58   else
  59     d_trellis = new code_convolutional_trellis
  60       (block_size_bits,
  61        n_code_inputs,
  62        n_code_outputs,
  63        code_generators,
  64        do_termination,
  65        end_memory_state);
  66
  67   // set the initial FSM state to 'init'
  68
  69   d_fsm_state = fsm_enc_conv_init;
  70   d_n_enc_bits = 0;
  71
  72   // create the class block variables
  73
  74   d_block_size_bits = block_size_bits;
  75   d_n_code_inputs = n_code_inputs;
  76   d_n_code_outputs = n_code_outputs;
  77   d_do_streaming = d_trellis->do_streaming ();
  78   d_do_termination = d_trellis->do_termination ();
  79   d_total_n_delays = d_trellis->total_n_delays ();
  80   d_n_bits_to_term = d_trellis->n_bits_to_term ();
  81
  82   // parse the init state
  83
  84   memory_t t_mask = (memory_t)((1 << d_total_n_delays) - 1);
  85   size_t t_n_states = (1 << d_total_n_delays);
  86   memory_t t_start_memory_state = (memory_t) start_memory_state;
  87
  88   if (t_start_memory_state != (t_start_memory_state & t_mask)) {
  89     std::cout << "encoder_convolutional: Warning: " <<
  90       "provided start memory state (" << start_memory_state <<
  91       ") is out of the state range [0, " <<
  92       (t_n_states-1) << "]; masking off the unused bits.\n";
  93
  94     start_memory_state &= t_mask;
  95   }
  96
  97   d_init_state = start_memory_state;
  98
  99   // reset the inputs and outputs, both to get the correct size() and
 100   // for the sake of zeroing them out.
 101
 102   d_current_inputs.assign (d_n_code_inputs, 0);
 103   d_current_outputs.assign (d_n_code_outputs, 0);
 104 }
 105
 106 void
 107 encoder_convolutional::encode_private
 108 ()
 109 {
 110   struct timeval t_tp;
 111   if (DO_TIME_THOUGHPUT) {
 112     start_timer (&t_tp);
 113   }
 114
 115   // reset buffer indices
 116
 117   d_total_n_enc_bits = 0;
 118
 119   // while there are inputs and outputs left to process ...
 120
 121   while ((d_n_bits_to_input != 0) |
 122          (d_n_bits_to_output != 0) |
 123          (d_fsm_state == fsm_enc_conv_init)) {
 124
 125     // jump to the correct state in the fsm
 126
 127     switch (d_fsm_state) {
 128
 129     case fsm_enc_conv_init:
 130
 131       if (DO_PRINT_DEBUG_FSM)
 132         std::cout << "Starting FSM Doing Init\n";
 133
 134       // copy the init states to the current memory
 135
 136       d_memory = d_init_state;
 137
 138       // if not doing streaming, things to do; else nothing more do
 139
 140       if (d_do_streaming == false) {
 141
 142         // reset the number of encoded bits in this block (which is
 143         // used to compare with the number of bits in the block)
 144
 145         d_n_enc_bits = 0;
 146       }
 147
 148       // move to the 'input' state
 149
 150       d_fsm_state = fsm_enc_conv_doing_input;
 151
 152       if (DO_PRINT_DEBUG_FSM)
 153         std::cout << "FSM State set to Doing Input\n"
 154           "Ending FSM Doing Init\n";
 155
 156       break;
 157
 158     case fsm_enc_conv_doing_input:
 159
 160       if (DO_PRINT_DEBUG_FSM)
 161         std::cout << "Starting FSM Doing Input\n";
 162
 163       // working through the trellis section which requires input bits
 164       // from external sources; loop up to the block size (before
 165       // termination bits, if any), counting down the number of
 166       // available input bits.
 167
 168       encode_loop (d_n_bits_to_input, d_block_size_bits);
 169
 170       // finished this loop; check for jumping to the next state
 171
 172       if ((d_n_enc_bits == d_block_size_bits) & (d_do_streaming == false)) {
 173
 174         // jump to another state, depending on termination requirement
 175
 176         if (d_do_termination == true) {
 177           d_n_enc_bits = 0;
 178           d_fsm_state = fsm_enc_conv_doing_term;
 179
 180           if (DO_PRINT_DEBUG_FSM)
 181             std::cout << "FSM State set to Doing Term\n";
 182
 183         } else {
 184           d_fsm_state = fsm_enc_conv_init;
 185
 186           if (DO_PRINT_DEBUG_FSM)
 187             std::cout << "FSM State set to Init\n";
 188         }
 189       }
 190
 191       if (DO_PRINT_DEBUG_FSM)
 192         std::cout << "Ending FSM Doing Input\n";
 193
 194       break;
 195
 196     case fsm_enc_conv_doing_term:
 197
 198       if (DO_PRINT_DEBUG_FSM)
 199         std::cout << "Starting FSM Doing Term\n";
 200
 201       // terminating the trellis, trying to get to a specific state;
 202       // better get here only when do_termination is true, but check
 203       // just in case; lop up to the max memory, counting down the
 204       // number of output bits left
 205
 206       if (d_do_termination == true) {
 207         if (d_n_enc_bits == 0) {
 208           // first time through this; save the starting termination state
 209           d_term_state = d_memory;
 210         }
 211
 212         encode_loop (d_n_bits_to_output, d_n_bits_to_term);
 213
 214         // finished this loop; check for jumping to the next state
 215
 216         if (d_n_enc_bits == d_n_bits_to_term) {
 217           d_fsm_state = fsm_enc_conv_init;
 218
 219           if (DO_PRINT_DEBUG_FSM)
 220             std::cout << "FSM State set to Init\n";
 221         }
 222       } else {
 223         // should never get here!
 224         assert (0);
 225       }
 226
 227       if (DO_PRINT_DEBUG_FSM)
 228         std::cout << "Ending FSM Doing Term\n";
 229
 230       break;
 231
 232     default:
 233       // better never get here!
 234       assert (0);
 235       break;
 236
 237       // done (switch) with FSM
 238     }
 239
 240     // done (while) there are inputs and outputs
 241   }
 242
 243   if (DO_TIME_THOUGHPUT) {
 244     // compute the throughput for this particular function call
 245     u_long d_t = end_timer (&t_tp);
 246     std::cout << "Completed " << d_total_n_enc_bits <<
 247       " bits in " << d_t << " usec => " <<
 248       1e6*(((double) d_total_n_enc_bits)/((double) d_t)) <<
 249       " b/s\n";
 250   }
 251 }
 252
 253 void
 254 encoder_convolutional::encode_loop
 255 (size_t& which_counter,
 256  size_t how_many)
 257 {
 258   // generic encode_loop
 259
 260   while ((which_counter > 0) & (d_n_enc_bits < how_many)) {
 261
 262     // get the next set of input bits from all streams;
 263     // written into d_current_inputs
 264
 265     get_next_inputs ();
 266
 267     // use the trellis to do the encoding;
 268     // updates the input memory to the new memory state for the given input
 269     // and writes the output bits to the current_outputs
 270
 271     d_trellis->encode_lookup (d_memory, d_current_inputs, d_current_outputs);
 272
 273     // write the bits in d_current_outputs into the output buffer
 274
 275     write_output_bits ();
 276
 277     // increment the number of encoded bits for the current block, and
 278     // the total number of bits for this running of "encode()"
 279
 280     d_n_enc_bits++;
 281     d_total_n_enc_bits++;
 282   }
 283 }
 284
 285 size_t
 286 encoder_convolutional::compute_n_output_bits
 287 (size_t n_input_bits)
 288 {
 289   size_t t_n_output_bits, t_n_input_bits;
 290   t_n_output_bits = t_n_input_bits = n_input_bits;
 291
 292   if (d_do_termination == true) {
 293     // not streaming, doing termination; find the number of bits
 294     // currently available with no required inputs, if any
 295
 296     size_t t_n_blocks, t_n_extra;
 297     t_n_blocks = t_n_extra = 0;
 298
 299     if (d_fsm_state == fsm_enc_conv_doing_term) {
 300
 301       t_n_extra = d_n_bits_to_term - d_n_enc_bits;
 302       t_n_blocks = t_n_input_bits / d_block_size_bits;
 303
 304     } else {
 305       // find the number of blocks which will be completed by the
 306       // additional inputs
 307
 308       t_n_blocks = (d_n_enc_bits + t_n_input_bits) / d_block_size_bits;
 309     }
 310
 311     // add the number of term_bits*blocks to the number of output bits
 312
 313     t_n_output_bits += (t_n_blocks * d_n_bits_to_term);
 314     t_n_output_bits += t_n_extra;
 315   }
 316
 317   return (t_n_output_bits);
 318 }
 319
 320 size_t
 321 encoder_convolutional::compute_n_input_bits
 322 (size_t n_output_bits)
 323 {
 324   size_t t_n_output_bits, t_n_input_bits;
 325   t_n_output_bits = t_n_input_bits = n_output_bits;
 326
 327   if (d_do_termination == true) {
 328
 329     // not streaming, doing termination; find the number of bits
 330     // currently available with no required inputs, if any
 331
 332     size_t n_extra = 0;
 333     if (d_fsm_state == fsm_enc_conv_doing_term) {
 334       n_extra = d_n_bits_to_term - d_n_enc_bits;
 335     }
 336
 337     // check to see if this is enough; return 0 if it is.
 338
 339     if (n_extra >= t_n_output_bits)
 340       return (0);
 341
 342     // remove those which require no input
 343
 344     t_n_output_bits -= n_extra;
 345     t_n_input_bits -= n_extra;
 346
 347     // add into the output bits the number of currently encoded input bits
 348
 349     if (d_fsm_state == fsm_enc_conv_doing_input)
 350       t_n_output_bits += d_n_enc_bits;
 351
 352     // find the number of blocks of data which will create the
 353     // remaining number of output bits, though possibly not the
 354     // termination bits of a final block (done later)
 355
 356     size_t t_n_output_bits_per_block = d_block_size_bits + d_n_bits_to_term;
 357     size_t t_n_blocks = t_n_output_bits / t_n_output_bits_per_block;
 358
 359     // remove the termination bits from the remaining # of input bits
 360
 361     t_n_input_bits -= (t_n_blocks * d_n_bits_to_term);
 362
 363     // do the remaining inputs / outputs create at least 1
 364     // block_size_bits (but less than a full block + termination bits)
 365
 366     t_n_output_bits -= (t_n_blocks * t_n_output_bits_per_block);
 367
 368     if (t_n_output_bits >= d_block_size_bits) {
 369       n_extra = t_n_output_bits - d_block_size_bits;
 370       t_n_input_bits -= n_extra;
 371     }
 372   }
 373
 374   return (t_n_input_bits);
 375 }