git.gag.com Git - debian/gnuradio/blob - gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.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., 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 "code_convolutional_trellis.h"
  28 #include <assert.h>
  29 #include <iostream>
  30
  31 #define DO_TIME_THOUGHPUT 0
  32 #define DO_PRINT_DEBUG 1
  33 #define DO_PRINT_DEBUG_ENCODE 1
  34
  35 #include <mld/mld_timer.h>
  36 #include <mld/n2bs.h>
  37
  38 static const int g_max_block_size_bits = 10000000;
  39 static const int g_max_num_streams = 10;
  40 static const int g_num_bits_per_byte = 8;
  41
  42 /*
  43  * sum_bits_mod2:
  44  * sum the number of set bits, mod 2, for the output bit
  45  */
  46
  47 char
  48 code_convolutional_trellis::sum_bits_mod2
  49 (memory_t in_mem,
  50  size_t max_memory)
  51 {
  52   // there are faster ways to do this, but this works for now; could
  53   // certainly do a single inline asm, which most processors provide
  54   // to deal with summing the bits in an integer.
  55   // this routine can be overridden by another method if desired.
  56
  57   char t_out_bit = (char)(in_mem & 1);
  58   for (size_t r = max_memory; r > 0; r--) {
  59     in_mem >>= 1;
  60     t_out_bit ^= ((char)(in_mem & 1));
  61   }
  62   return (t_out_bit);
  63 }
  64
  65 void
  66 code_convolutional_trellis::code_convolutional_trellis_init
  67 (int block_size_bits,
  68  int n_code_inputs,
  69  int n_code_outputs,
  70  const std::vector<int>& code_generators,
  71  const std::vector<int>* code_feedback,
  72  bool do_termination,
  73  int end_memory_state)
  74 {
  75   // do error checking on the input arguments
  76
  77   // make sure the block length makes sense
  78
  79   if ((block_size_bits < 0) | (block_size_bits > g_max_block_size_bits)) {
  80     std::cerr << "code_convolutional_trellis: " <<
  81       "Requested block length (" << block_size_bits <<
  82       " bits) must be between 0 and " << g_max_block_size_bits <<
  83       " bits, with 0 being a streaming encoder.\n";
  84     assert (0);
  85   }
  86
  87   // check to make sure the number of input streams makes sense
  88
  89   if ((n_code_inputs <= 0) | (n_code_inputs > g_max_num_streams)) {
  90     std::cerr << "code_convolutional_trellis: " <<
  91       "Requested number of input streams (" <<
  92       n_code_inputs << ") must be between 1 and " <<
  93       g_max_num_streams << ".\n";
  94     assert (0);
  95   }
  96
  97   // check to make sure the number of output streams makes sense
  98
  99   if ((n_code_outputs <= 0) | (n_code_outputs > g_max_num_streams)) {
 100     std::cerr << "code_convolutional_trellis: " <<
 101       "Requested number of output streams (" <<
 102       n_code_outputs << ") must be between 1 and " <<
 103       g_max_num_streams << ".\n";
 104     assert (0);
 105   }
 106
 107   // make sure the code_generator is the correct length
 108
 109   if (code_generators.size () !=
 110       ((size_t)(n_code_inputs * n_code_outputs))) {
 111     std::cerr << "code_convolutional_trellis: " <<
 112       "Number of code generator entries (" << code_generators.size () <<
 113       ") is not equal to the product of the number of input and output" <<
 114       " streams (" << (n_code_inputs * n_code_outputs) << ").\n";
 115     assert (0);
 116   }
 117
 118   // check for feedback (== NULL or not)
 119
 120   d_do_feedback = (code_feedback != NULL);
 121
 122   // create the class block variables
 123
 124   d_block_size_bits = block_size_bits;
 125   d_n_code_inputs = n_code_inputs;
 126   d_n_code_outputs = n_code_outputs;
 127   d_do_streaming = (block_size_bits == 0);
 128   d_do_termination = (d_do_streaming == true) ? false : do_termination;
 129
 130   if (DO_PRINT_DEBUG) {
 131     std::cout <<
 132       "d_block_size_bits = " << d_block_size_bits << "\n"
 133       "d_n_code_inputs   = " << d_n_code_inputs << "\n"
 134       "d_n_code_outputs  = " << d_n_code_outputs << "\n"
 135       "d_do_streaming    = " <<
 136       ((d_do_streaming == true) ? "true" : "false") << "\n"
 137       "d_do_termination  = " <<
 138       ((d_do_termination == true) ? "true" : "false") << "\n"
 139       "d_do_feedback     = " <<
 140       ((d_do_feedback == true) ? "true" : "false") << "\n";
 141   }
 142
 143   // allocate the vectors for doing the encoding.  use memory_t (an
 144   // interger type, at least 32 bits) bits to represent memory and the
 145   // code, as it makes the operations quite simple the state vectors.
 146
 147   // d_states is a "matrix" [#input by #outputs] containing indices
 148   // to memory_t's; this is done to make feedback function properly,
 149   // and doesn't effect the computation time for feedforward.  The
 150   // issue is that any code with the same feedback can use the same
 151   // memory - thus reducing the actual number of memories required.
 152   // These overlapping encoders will use the same actual memory, but
 153   // given that there is no way to know a-priori where they are, use
 154   // pointers over the full I/O matrix-space to make sure each I/O
 155   // encoder uses the correct memory.
 156   // reference the matrix using "maoi(i,o)" ... see .h file.
 157
 158   // code generators (feedforward part) are [#inputs x #outputs],
 159   // always - one for each I/O combination.
 160   // reference the matrix using "maoi(i,o)" ... see .h file
 161
 162   d_code_generators.assign (d_n_code_inputs * d_n_code_outputs, 0);
 163
 164   // check the feedback for correctness, before anything else, since
 165   // any feedback impacts the total # of delays in the encoder:
 166   // without feedback, this is the sum of the individual delays max'ed
 167   // over each input (if siao) or output (if soai).
 168
 169   if (d_do_feedback == true) {
 170     memory_t t_OR_all_feedback = 0;
 171     for (size_t n = 0; n < d_n_code_outputs; n++) {
 172       for (size_t m = 0; m < d_n_code_inputs; m++) {
 173         memory_t t_in_code = (*code_feedback)[maoi(m,n)];
 174
 175         // OR this feedback with the overall,
 176         // to check for any delays used at all
 177
 178         t_OR_all_feedback |= t_in_code;
 179       }
 180     }
 181
 182     // check to see if all the feedback entries were either "0" or "1",
 183     // which implies no feedback; warn the user in that case and reset
 184     // the do_feedback parameter to false.
 185
 186     if ((t_OR_all_feedback | 1) == 1) {
 187       std::cout << "code_convolutional_trellis: Warning: " <<
 188         "No feedback is required, ignoring feedback.\n";
 189       d_do_feedback = false;
 190     }
 191   }
 192
 193   // copy over the FF code generators
 194
 195   for (size_t n = 0; n < d_n_code_outputs; n++)
 196     for (size_t m = 0; m < d_n_code_inputs; m++)
 197       d_code_generators[maio(m,n)] = code_generators[maio(m,n)];
 198
 199   // check the input FF (and FB) code generators for correctness, and
 200   // find the minimum memory configuration: combining via a single
 201   // input / all outputs (SIAO), or a single output / all inputs (SOAI).
 202   //
 203   // for FF only, look over both the SOAI and SIAO realizations to
 204   // find the minimum total # of delays, and use that realization
 205   // (SOAI is preferred if total # of delays is equal, since it's much
 206   // simpler to implement).
 207   //
 208   // for FB:
 209   //   for SIAO, check each input row (all outputs for a given input)
 210   //     for unique feedback; duplicate feedback entries can be
 211   //     combined into a single computation to reduce total # of delays.
 212   //   for SOAI: check each output column (all inputs for a given
 213   //     output) for unique feedback; duplicate feedback entries can
 214   //     be combined into a simgle computation (ditto).
 215
 216   // check for SOAI all '0' output
 217
 218   for (size_t n = 0; n < d_n_code_outputs; n++) {
 219     memory_t t_all_inputs_zero = 0;
 220     for (size_t m = 0; m < d_n_code_inputs; m++)
 221       t_all_inputs_zero |= d_code_generators[maio(m,n)];
 222
 223     // check this input to see if all encoders were '0'; this might be
 224     // OK for some codes, but warn the user just in case
 225
 226     if (t_all_inputs_zero == 0) {
 227       std::cout << "code_convolutional_trellis: Warning:"
 228         "Output " << n+1 << " (of " << d_n_code_outputs <<
 229         ") will always be 0.\n";
 230     }
 231   }
 232
 233   // check for SIAO all '0' input
 234
 235   for (size_t m = 0; m < d_n_code_inputs; m++) {
 236     memory_t t_all_outputs_zero = 0;
 237     for (size_t n = 0; n < d_n_code_outputs; n++)
 238       t_all_outputs_zero |= d_code_generators[maio(m,n)];
 239
 240     // check this input to see if all encoders were '0'; this might be
 241     // OK for some codes, but warn the user just in case
 242
 243     if (t_all_outputs_zero == 0) {
 244       std::cout << "code_convolutional_trellis: Warning:"
 245         "Input " << m+1 << " (of " << d_n_code_inputs <<
 246         ") will not be used; all encoders are '0'.\n";
 247     }
 248   }
 249
 250   // check and compute memory requirements in order to determine which
 251   // realization uses the least memory; create and save findings to
 252   // not have to re-do these computations later.
 253
 254   // single output, all inputs (SOAI) realization:
 255   // reset the global parameters
 256
 257   d_code_feedback.assign (d_n_code_inputs * d_n_code_outputs, 0);
 258   d_n_delays.assign (d_n_code_inputs * d_n_code_outputs, 0);
 259   d_io_num.assign (d_n_code_inputs * d_n_code_outputs, 0);
 260   d_states_ndx.assign (d_n_code_inputs * d_n_code_outputs, 0);
 261   d_max_delay = d_total_n_delays = d_n_memories = 0;
 262   d_do_encode_soai = true;
 263
 264   for (size_t n = 0; n < d_n_code_outputs; n++) {
 265     size_t t_max_mem = 0;
 266     size_t t_n_unique_fb_prev_start = d_n_memories;
 267
 268     for (size_t m = 0; m < d_n_code_inputs; m++) {
 269       get_memory_requirements (m, n, t_max_mem,
 270                                t_n_unique_fb_prev_start, code_feedback);
 271       if (d_do_feedback == false) {
 272         d_states_ndx[maio(m,n)] = n;
 273       }
 274     }
 275     if (d_do_feedback == false) {
 276       // not feedback; just store memory requirements for this output
 277       d_total_n_delays += t_max_mem;
 278       d_n_delays[n] = t_max_mem;
 279       d_io_num[n] = n;
 280     }
 281   }
 282   if (d_do_feedback == false) {
 283     d_n_memories = d_n_code_outputs;
 284   }
 285
 286   // store the parameters for SOAI
 287
 288   std::vector<size_t> t_fb_generators_soai, t_n_delays_soai, t_io_num_soai;
 289   std::vector<size_t> t_states_ndx_soai;
 290   size_t t_max_delay_soai, t_total_n_delays_soai, t_n_memories_soai;
 291
 292   t_fb_generators_soai.assign (d_code_feedback.size (), 0);
 293   t_fb_generators_soai = d_code_feedback;
 294   t_n_delays_soai.assign (d_n_delays.size (), 0);
 295   t_n_delays_soai = d_n_delays;
 296   t_io_num_soai.assign (d_io_num.size (), 0);
 297   t_io_num_soai = d_io_num;
 298   t_states_ndx_soai.assign (d_states_ndx.size (), 0);
 299   t_states_ndx_soai = d_states_ndx;
 300
 301   t_n_memories_soai = d_n_memories;
 302   t_total_n_delays_soai = d_total_n_delays;
 303   t_max_delay_soai = d_max_delay;
 304
 305   // single input, all outputs (SIAO) realization
 306   // reset the global parameters
 307
 308   d_code_feedback.assign (d_n_code_inputs * d_n_code_outputs, 0);
 309   d_n_delays.assign (d_n_code_inputs * d_n_code_outputs, 0);
 310   d_io_num.assign (d_n_code_inputs * d_n_code_outputs, 0);
 311   d_states_ndx.assign (d_n_code_inputs * d_n_code_outputs, 0);
 312   d_max_delay = d_total_n_delays = d_n_memories = 0;
 313   d_do_encode_soai = false;
 314
 315   for (size_t m = 0; m < d_n_code_inputs; m++) {
 316     size_t t_max_mem = 0;
 317     size_t t_n_unique_fb_prev_start = d_n_memories;
 318
 319     for (size_t n = 0; n < d_n_code_outputs; n++) {
 320       get_memory_requirements (m, n, t_max_mem,
 321                                t_n_unique_fb_prev_start, code_feedback);
 322       if (d_do_feedback == false) {
 323         d_states_ndx[maio(m,n)] = m;
 324       }
 325     }
 326     if (d_do_feedback == false) {
 327       // not feedback; just store memory requirements for this output
 328       d_total_n_delays += t_max_mem;
 329       d_n_delays[m] = t_max_mem;
 330       d_io_num[m] = m;
 331     }
 332   }
 333   if (d_do_feedback == false) {
 334     d_n_memories = d_n_code_inputs;
 335   }
 336
 337   if (DO_PRINT_DEBUG) {
 338     std::cout <<
 339       "  t_total_n_delays_siao  = " << d_total_n_delays << "\n"
 340       "  t_total_n_delays_soai  = " << t_total_n_delays_soai << "\n";
 341   }
 342
 343   // pick which realization to use; soai is preferred since it's faster
 344   // ... but unfortunately it's also less likely
 345
 346   if (d_total_n_delays < t_total_n_delays_soai) {
 347     // use siao
 348     // nothing else to do, since the global variables already hold
 349     // the correct values.
 350   } else {
 351     // use soai
 352     d_do_encode_soai = true;
 353     d_code_feedback = t_fb_generators_soai;
 354     d_n_delays = t_n_delays_soai;
 355     d_io_num = t_io_num_soai;
 356     d_states_ndx = t_states_ndx_soai;
 357     d_n_memories = t_n_memories_soai;
 358     d_total_n_delays = t_total_n_delays_soai;
 359     d_max_delay = t_max_delay_soai;
 360   }
 361
 362   // make sure the block length makes sense, #2
 363
 364   if ((d_do_streaming == false) & (d_block_size_bits < d_max_delay)) {
 365     std::cerr << "code_convolutional_trellis: " <<
 366       "Requested block length (" << d_block_size_bits <<
 367       " bit" << (d_block_size_bits > 1 ? "s" : "") <<
 368       ") must be at least 1 memory length (" << d_max_delay <<
 369       " bit" << (d_max_delay > 1 ? "s" : "") <<
 370       " for this code) when doing block coding.\n";
 371     assert (0);
 372   }
 373
 374   // check & mask off the init states
 375
 376   d_n_states = (1 << d_total_n_delays);
 377   d_n_input_combinations = (1 << d_n_code_inputs);
 378
 379   memory_t t_mask = (memory_t)((2 << d_total_n_delays) - 1);
 380
 381   if (end_memory_state & t_mask) {
 382     std::cout << "code_convolutional_trellis: Warning: " <<
 383       "provided end memory state out (" << end_memory_state <<
 384       ") is out of the state range [0, " <<
 385       (d_n_states-1) << "]; masking off the unused bits.\n";
 386
 387     end_memory_state &= t_mask;
 388   }
 389
 390   // create the max_mem_mask to be used in encoding
 391
 392   d_max_mem_masks.assign (d_n_memories, 0);
 393
 394   for (size_t m = 0; m < d_n_memories; m++) {
 395     if (d_n_delays[m] == sizeof (memory_t) * g_num_bits_per_byte)
 396       d_max_mem_masks[m] = ((memory_t) -1);
 397     else
 398       d_max_mem_masks[m] = (memory_t)((2 << (d_n_delays[m])) - 1);
 399   }
 400
 401   if (DO_PRINT_DEBUG) {
 402     std::cout <<
 403       "  d_n_memories      = " << d_n_memories << "\n"
 404       "  d_total_n_delays  = " << d_total_n_delays << "\n"
 405       "  d_max_delay       = " << d_max_delay << "\n"
 406       "  d_do_encode_soai  = " <<
 407       ((d_do_encode_soai == true) ? "true" : "false") << "\n";
 408   }
 409
 410   // zero the memories
 411
 412   d_memory.assign (d_n_memories, 0);
 413
 414   // create the inputs and outputs buffers
 415
 416   d_current_inputs.assign (d_n_code_inputs, 0);
 417   d_current_outputs.assign (d_n_code_outputs, 0);
 418
 419   // create the trellis for this code:
 420
 421   create_trellis ();
 422
 423   if (d_do_termination == true) {
 424
 425     // create the termination lookup table
 426
 427     create_termination_table (end_memory_state);
 428   }
 429 }
 430
 431 void
 432 code_convolutional_trellis::get_memory_requirements
 433 (size_t m,   // input number
 434  size_t n,   // output number
 435  size_t& t_max_mem,
 436  size_t& t_n_unique_fb_prev_start,
 437  const std::vector<int>* code_feedback)
 438 {
 439   size_t t_in_code = d_code_generators[maio(m,n)];
 440
 441   // find the memory requirement for this code generator
 442
 443   size_t t_code_mem_ff = max_bit_position (t_in_code);
 444
 445   // check to see if this is bigger than any others in this row/column
 446
 447   if (t_code_mem_ff > t_max_mem)
 448     t_max_mem = t_code_mem_ff;
 449
 450   if (DO_PRINT_DEBUG) {
 451     std::cout << "c_g[" << m << "][" << n << "]{" <<
 452       maio(m,n) << "} = " << n2bs(t_in_code, 8) <<
 453       ", code_mem = " << t_code_mem_ff;
 454   }
 455
 456   // check the feedback portion, if it exists;
 457   // for soai, check all the inputs which generate this output for
 458   // uniqueness; duplicate entries can be combined to reduce total
 459   // # of memories as well as required computations.
 460
 461   if (d_do_feedback == true) {
 462     if (DO_PRINT_DEBUG) {
 463       std::cout << "\n";
 464     }
 465
 466     // get the FB code; AND off the LSB for correct functionality
 467     // during internal computations.
 468
 469     t_in_code = ((memory_t)((*code_feedback)[maio(m,n)]));
 470     t_in_code &= ((memory_t)(-2));
 471
 472     // find the memory requirement
 473
 474     size_t t_code_mem_fb = max_bit_position (t_in_code);
 475
 476     if (DO_PRINT_DEBUG) {
 477       std::cout << "c_f[" << m << "][" << n << "]{" <<
 478         maio(m,n) << "} = " << n2bs(t_in_code, 8) <<
 479         ", code_mem = " << t_code_mem_fb;
 480     }
 481
 482     // check to see if this feedback is unique
 483
 484     size_t l_n_unique_fb = t_n_unique_fb_prev_start;
 485     while (l_n_unique_fb < d_n_memories) {
 486       if (d_code_feedback[l_n_unique_fb] == t_in_code)
 487         break;
 488       l_n_unique_fb++;
 489     }
 490     if (l_n_unique_fb == d_n_memories) {
 491
 492       // this is a unique feedback;
 493
 494       d_code_feedback[l_n_unique_fb] = t_in_code;
 495       d_n_delays[l_n_unique_fb] = t_code_mem_fb;
 496
 497       // increase the number of unique feedback codes
 498
 499       d_n_memories++;
 500
 501       // store memory requirements for this output
 502
 503       if (t_max_mem < t_code_mem_fb)
 504         t_max_mem = t_code_mem_fb;
 505       d_total_n_delays += t_max_mem;
 506
 507       if (DO_PRINT_DEBUG) {
 508         std::cout << ",  uq # " << l_n_unique_fb <<
 509           ", tot_mem = " << d_total_n_delays;
 510       }
 511     } else {
 512       // not a unique feedback, but the FF might require more memory
 513
 514       if (DO_PRINT_DEBUG) {
 515         std::cout << ", !uq # " << l_n_unique_fb <<
 516           " = " << d_n_delays[l_n_unique_fb];
 517       }
 518
 519       if (d_n_delays[l_n_unique_fb] < t_code_mem_ff) {
 520         d_total_n_delays += (t_code_mem_ff - d_n_delays[l_n_unique_fb]);
 521         d_n_delays[l_n_unique_fb] = t_code_mem_ff;
 522
 523         if (DO_PRINT_DEBUG) {
 524           std::cout << " => " << d_n_delays[l_n_unique_fb] <<
 525             ", tot_mem = " << d_total_n_delays;
 526         }
 527       }
 528     }
 529     d_io_num[l_n_unique_fb] = ((d_do_encode_soai == true) ? n : m);
 530     d_states_ndx[maio(m,n)] = l_n_unique_fb;
 531   }
 532   if (DO_PRINT_DEBUG) {
 533     std::cout << "\n";
 534   }
 535   if (d_max_delay < t_max_mem)
 536     d_max_delay = t_max_mem;
 537 }
 538
 539 void
 540 code_convolutional_trellis::create_trellis
 541 ()
 542 {
 543   if (DO_PRINT_DEBUG_ENCODE) {
 544     std::cout << "c_t: # states = " << d_n_states <<
 545       ", d_n_input_combinations = " << d_n_input_combinations << "\n";
 546   }
 547
 548   // first dimension is the number of states
 549
 550   d_trellis.resize (d_n_states);
 551
 552   // second dimension (one per first dimension) is the number of input
 553   // combinations
 554
 555   for (size_t m = 0; m < d_n_states; m++) {
 556     d_trellis[m].resize (d_n_input_combinations);
 557     for (size_t n = 0; n < d_n_input_combinations; n++) {
 558       connection_t_ptr t_connection = &(d_trellis[m][n]);
 559       t_connection->d_output_bits.resize (d_n_code_outputs);
 560     }
 561   }
 562
 563   // fill in the trellis
 564
 565   for (size_t m = 0; m < d_n_states; m++) {
 566     for (size_t n = 0; n < d_n_input_combinations; n++) {
 567       connection_t_ptr t_connection = &(d_trellis[m][n]);
 568       encode_single (m, n, t_connection->d_to_state,
 569                      t_connection->d_output_bits);
 570       if (DO_PRINT_DEBUG_ENCODE) {
 571         std::cout << "set d_t[" << n2bs(m,d_total_n_delays) << "][" <<
 572           n2bs(n,d_n_code_inputs) << "] : to_st = " <<
 573           n2bs(t_connection->d_to_state,d_total_n_delays) << "\n";
 574       }
 575     }
 576   }
 577 }
 578
 579 void
 580 code_convolutional_trellis::demux_state
 581 (memory_t in_state,
 582  std::vector<memory_t>& memories)
 583 {
 584   // de-mux bits for the given memory state;
 585   // copy them into the provided vector;
 586   // assumes state bits start after the LSB (not at &1)
 587
 588   memories.resize (d_n_memories);
 589   if (DO_PRINT_DEBUG_ENCODE) {
 590     std::cout << "in_st = " << n2bs(in_state,d_total_n_delays) << " ->\n";
 591   }
 592   for (size_t m = 0; m < d_n_memories; m++) {
 593     memories[m] = (in_state << 1) & d_max_mem_masks[m];
 594     in_state >>= d_n_delays[m];
 595     if (DO_PRINT_DEBUG_ENCODE) {
 596       std::cout << "  #d = " << d_n_delays[m] << ", mem[" << m << "] = " <<
 597         n2bs(memories[m], d_n_delays[m]+1) << "\n";
 598     }
 599   }
 600 }
 601
 602 memory_t
 603 code_convolutional_trellis::mux_state
 604 (const std::vector<memory_t>& memories)
 605 {
 606   // mux bits for the given memory states in d_memory
 607   // assumes state bits start after the LSB (not at &1)
 608   memory_t t_state = 0;
 609   size_t shift = 0;
 610   for (size_t m = 0; m < d_n_memories; m++) {
 611     t_state |= (memories[m] >> 1) << shift;
 612     shift += d_n_delays[m];
 613     if (DO_PRINT_DEBUG_ENCODE) {
 614       std::cout << "  #d = " << d_n_delays[m] << ", mem[" << m << "] = " <<
 615         n2bs(memories[m], d_n_delays[m]+1) << " -> st = " <<
 616         n2bs(t_state, d_total_n_delays) << "\n";
 617     }
 618   }
 619   return (t_state);
 620 }
 621
 622 void
 623 code_convolutional_trellis::demux_inputs
 624 (memory_t inputs,
 625  std::vector<char>& in_vec)
 626 {
 627   for (size_t m = 0; m < d_n_code_inputs; m++, inputs >>= 1) {
 628     in_vec[m] = (char)(inputs & 1);
 629   }
 630 }
 631
 632 memory_t
 633 code_convolutional_trellis::mux_inputs
 634 (const std::vector<char>& in_vec)
 635 {
 636   size_t bit_shift = 0;
 637   memory_t inputs = 0;
 638   for (size_t m = 0; m < in_vec.size(); m++, bit_shift++) {
 639     inputs |= (((memory_t)(in_vec[m]&1)) << bit_shift);
 640   }
 641   return (inputs);
 642 }
 643
 644 void
 645 code_convolutional_trellis::encode_single
 646 (memory_t in_state,
 647  size_t inputs,
 648  memory_t& out_state,
 649  std::vector<char>& out_bits)
 650 {
 651   // set input parameters
 652
 653   demux_state (in_state, d_memory);
 654   demux_inputs (inputs, d_current_inputs);
 655
 656   // call the correct function to do the work
 657
 658   if (d_do_encode_soai == true) {
 659     if (d_do_feedback == true) {
 660       encode_single_soai_fb ();
 661     } else {
 662       encode_single_soai ();
 663     }
 664   } else {
 665     if (d_do_feedback == true) {
 666       encode_single_siao_fb ();
 667     } else {
 668       encode_single_siao ();
 669     }
 670   }
 671
 672   // retrieve the output parameters
 673
 674   out_state = mux_state (d_memory);
 675   out_bits = d_current_outputs;
 676 }
 677
 678 void
 679 code_convolutional_trellis::encode_lookup
 680 (memory_t& state,
 681  const std::vector<char>& inputs,
 682  std::vector<char>& out_bits)
 683 {
 684   if (DO_PRINT_DEBUG_ENCODE) {
 685     std::cout << "using d_t[" << state << "][" << mux_inputs(inputs) <<
 686       "] = ";
 687     std::cout.flush ();
 688   }
 689
 690   connection_t_ptr t_connection = &(d_trellis[state][mux_inputs(inputs)]);
 691
 692   if (DO_PRINT_DEBUG_ENCODE) {
 693     std::cout << t_connection << ": to_state = "
 694               << t_connection->d_to_state << "\n";
 695   }
 696
 697   state = t_connection->d_to_state;
 698   out_bits = t_connection->d_output_bits;
 699 }
 700
 701 void
 702 code_convolutional_trellis::get_termination_inputs
 703 (memory_t term_start_state,
 704  size_t bit_num,
 705  std::vector<char>& inputs)
 706 {
 707   inputs.resize (d_n_code_inputs);
 708   for (size_t m = 0; m < d_n_code_inputs; m++) {
 709     inputs[m] = ((d_term_inputs[term_start_state][m]) >> bit_num) & 1;
 710   }
 711 }
 712
 713 void
 714 code_convolutional_trellis::create_termination_table
 715 (memory_t end_memory_state)
 716 {
 717   // somewhat involved, but basically start with the terminating state
 718   // and work backwards d_total_n_delays, then create a
 719   // std::vector<memory_t> of length n_states, once per path required
 720   // to get from the given state to the desired termination state.
 721   //
 722   // each entry represents the bits required to terminate that
 723   // particular state, listed in order from LSB for the first input
 724   // bit to the MSB for the last input bit.
 725
 726 #if 0
 727   // create a reverse trellis
 728   // it's temporary, just for doing the termination, so just do it locally
 729
 730   trellis_t t_trellis;
 731
 732   // first dimension is the number of states
 733
 734   t_trellis.resize (d_n_states);
 735
 736   // second dimension (one per first dimension) is the number of input
 737   // combinations
 738
 739   for (size_t m = 0; m < d_n_states; m++) {
 740     t_trellis[m].resize (d_n_input_combinations);
 741   }
 742
 743   std::vector<char> outputs (d_n_code_outputs);
 744   memory_t to_state;
 745
 746   // fill in the trellis
 747
 748   for (memory_t m = 0; m < d_n_states; m++) {
 749     for (memory_t n = 0; n < d_n_input_combinations; n++) {
 750       encode_single (m, n, to_state, outputs);
 751
 752       connection_t_ptr t_connection = &(t_trellis[to_state][n]);
 753       t_connection->d_to_state = m;
 754 #if 0
 755       t_connection->d_output_bits.resize (d_n_code_outputs);
 756       t_connection->d_output_bits = outputs;
 757 #endif
 758     }
 759   }
 760
 761   // create the output vectors
 762
 763   term_input_t t_term_inputs;
 764   t_term_inputs.resize (d_n_states);
 765   for (size_t m = 0; m < d_n_states; m++) {
 766     t_term_inputs[m].assign (d_n_code_inputs, 0);
 767   }
 768
 769
 770   std::vector<memory_t> t_used_states;
 771   t_used_states.assign (d_n_states, 0);
 772
 773   // setup the first state
 774
 775   t_states[0] = end_memory_state;
 776   size_t n_states = 1;
 777
 778   for (size_t m = 0; m < d_total_n_delays; m++) {
 779     for (size_t n = 0; n < n_states; n++) {
 780       memory_t t_end_state = t_states[n];
 781       for (size_t p = 0; p < d_n_code_inputs; p++) {
 782         connection_t_ptr t_connection = &(t_trellis[t_end_state][p]);
 783         memory_t_ptr t_mem = &(t_term_inputs[t_end_state][p]);
 784
 785
 786
 787
 788     }
 789   }
 790
 791   t_inputs[0] = t_trellis
 792 #endif
 793 }
 794
 795 void
 796 code_convolutional_trellis::encode_single_soai
 797 ()
 798 {
 799   // single-output, all inputs; no feedback
 800
 801   if (DO_PRINT_DEBUG) {
 802     std::cout << "Starting encode_single_soai.\n";
 803   }
 804
 805   // shift memories down by 1 bit to make room for feedback; no
 806   // masking required.
 807
 808   for (size_t p = 0; p < d_n_memories; p++) {
 809     if (DO_PRINT_DEBUG) {
 810       std::cout << "m_i[" << p << "] = " <<
 811         n2bs(d_memory[p], 1+d_n_delays[p]);
 812     }
 813
 814     d_memory[p] >>= 1;
 815
 816     if (DO_PRINT_DEBUG) {
 817       std::cout << "  >>= 1 -> " <<
 818         n2bs(d_memory[p], 1+d_n_delays[p]) << "\n";
 819     }
 820   }
 821
 822   // for each input bit, if that bit's a '1', then XOR the code
 823   // generators into the correct state's memory.
 824
 825   for (size_t m = 0; m < d_n_code_inputs; m++) {
 826     if (DO_PRINT_DEBUG) {
 827       std::cout << "c_i[" << m << "] = " <<
 828         n2bs(d_current_inputs[m],1);
 829     }
 830     if (d_current_inputs[m] == 1) {
 831       if (DO_PRINT_DEBUG) {
 832         std::cout << "\n";
 833       }
 834       for (size_t n = 0; n < d_n_code_outputs; n++) {
 835         if (DO_PRINT_DEBUG) {
 836           std::cout << "m_i[s_ndx[" << m << "][" << n << "] == " <<
 837             d_states_ndx[maio(m,n)] << "] = " <<
 838             n2bs(d_memory[d_states_ndx[maio(m,n)]],
 839                  1+d_n_delays[d_states_ndx[maio(m,n)]]);
 840         }
 841
 842         d_memory[d_states_ndx[maio(m,n)]] ^= d_code_generators[maio(m,n)];
 843
 844         if (DO_PRINT_DEBUG) {
 845           std::cout << " ^= c_g[][] == " <<
 846             n2bs(d_code_generators[maio(m,n)],
 847                  1+d_n_delays[d_states_ndx[maio(m,n)]]) <<
 848             " -> " << n2bs(d_memory[d_states_ndx[maio(m,n)]],
 849                            1+d_n_delays[d_states_ndx[maio(m,n)]]) << "\n";
 850         }
 851       }
 852     } else if (DO_PRINT_DEBUG) {
 853       std::cout << " ... nothing to do\n";
 854     }
 855   }
 856
 857   for (size_t p = 0; p < d_n_code_outputs; p++) {
 858     d_current_outputs[p] = 0;
 859   }
 860
 861   // create the output bits, by XOR'ing the individual unique
 862   // memory(ies) into the correct output bit
 863
 864   for (size_t p = 0; p < d_n_memories; p++) {
 865     d_current_outputs[d_io_num[p]] ^= ((char)(d_memory[p] & 1));
 866   }
 867
 868   if (DO_PRINT_DEBUG) {
 869     std::cout << "ending encode_single_soai.\n";
 870   }
 871 }
 872
 873 void
 874 code_convolutional_trellis::encode_single_soai_fb
 875 ()
 876 {
 877   // single-output, all inputs; with feedback
 878
 879   if (DO_PRINT_DEBUG) {
 880     std::cout << "Starting encode_single_soai_fb.\n";
 881   }
 882
 883   // shift memories down by 1 bit to make room for feedback; no
 884   // masking required.
 885
 886   for (size_t p = 0; p < d_n_memories; p++) {
 887     if (DO_PRINT_DEBUG) {
 888       std::cout << "m_i[" << p << "] = " << d_memory[p];
 889     }
 890
 891     d_memory[p] >>= 1;
 892
 893     if (DO_PRINT_DEBUG) {
 894       std::cout << " -> " << d_memory[p] << "\n";
 895     }
 896   }
 897
 898   // for each input bit, if that bit's a '1', then XOR the code
 899   // generators into the correct state's memory.
 900
 901   for (size_t m = 0; m < d_n_code_inputs; m++) {
 902     if (d_current_inputs[m] == 1) {
 903       for (size_t n = 0; n < d_n_code_outputs; n++) {
 904         d_memory[d_states_ndx[maio(m,n)]] ^= d_code_generators[maio(m,n)];
 905       }
 906     }
 907   }
 908
 909   for (size_t p = 0; p < d_n_code_outputs; p++) {
 910     d_current_outputs[p] = 0;
 911   }
 912
 913   // create the output bits, by XOR'ing the individual unique
 914   // memory(ies) into the correct output bit
 915
 916   for (size_t p = 0; p < d_n_memories; p++) {
 917     d_current_outputs[d_io_num[p]] ^= ((char)(d_memory[p] & 1));
 918   }
 919
 920   // now that the output bits are fully created, XOR the FB back
 921   // into the memories; the feedback bits have the LSB (&1) masked
 922   // off already so that it doesn't contribute.
 923
 924   for (size_t p = 0; p < d_n_memories; p++) {
 925     if (d_current_outputs[d_io_num[p]] == 1) {
 926       d_memory[p] ^= d_code_feedback[p];
 927     }
 928   }
 929
 930   if (DO_PRINT_DEBUG) {
 931     std::cout << "ending encode_single_soai.\n";
 932   }
 933 }
 934
 935 void
 936 code_convolutional_trellis::encode_single_siao
 937 ()
 938 {
 939   // single input, all outputs; no feedback
 940
 941   if (DO_PRINT_DEBUG) {
 942     std::cout << "starting encode_single_siao.\n";
 943   }
 944
 945   // update the memories with the current input bits;
 946
 947   // for each unique memory (1 per input), shift the delays and mask
 948   // off the extra high bits; then XOR in the input bit.
 949
 950   for (size_t p = 0; p < d_n_memories; p++) {
 951     d_memory[p] |= ((memory_t)(d_current_inputs[d_io_num[p]]));
 952   }
 953
 954   // create the output bits: for each output, loop over all inputs,
 955   // find the output bits for each encoder, and XOR each together
 956   // then sum (would usually be sum then XOR, but they're mutable in
 957   // base-2 and it's faster this way).
 958
 959   for (size_t n = 0; n < d_n_code_outputs; n++) {
 960     memory_t t_mem = 0;
 961     for (size_t m = 0; m < d_n_code_inputs; m++) {
 962       t_mem ^= ((d_memory[d_states_ndx[maio(m,n)]]) &
 963                 d_code_generators[maio(m,n)]);
 964     }
 965     d_current_outputs[n] = sum_bits_mod2 (t_mem, d_max_delay);
 966   }
 967
 968   // post-shift & mask the memory to guarantee that output
 969   // state is in the correct bit positions (1 up, not the LSB)
 970
 971   for (size_t p = 0; p < d_n_memories; p++) {
 972     d_memory[p] = (d_memory[p] << 1) & d_max_mem_masks[p];
 973   }
 974
 975   if (DO_PRINT_DEBUG) {
 976     std::cout << "ending encode_single_siao.\n";
 977   }
 978 }
 979
 980 void
 981 code_convolutional_trellis::encode_single_siao_fb
 982 ()
 983 {
 984   // single input, all outputs; with feedback
 985
 986   if (DO_PRINT_DEBUG) {
 987     std::cout << "starting encode_single_siao_fb.\n";
 988   }
 989
 990   // update the memories with the current input bits;
 991
 992   // for each unique memory (1 per input), shift the delays and mask
 993   // off the extra high bits; then XOR in the input bit.
 994   // with FB: find the feedback bit, and OR it into the input bit's slot;
 995
 996   for (size_t p = 0; p < d_n_memories; p++) {
 997     memory_t t_mem = d_memory[p];
 998     memory_t t_fb = t_mem & d_code_feedback[p];
 999     char t_fb_bit = sum_bits_mod2 (t_fb, d_max_delay);
1000     t_mem |= ((memory_t) t_fb_bit);
1001     d_memory[p] = t_mem ^ ((memory_t)(d_current_inputs[d_io_num[p]]));
1002   }
1003
1004   // create the output bits: for each output, loop over all inputs,
1005   // find the output bits for each encoder, and XOR each together
1006   // then sum (would usually be sum then XOR, but they're mutable in
1007   // base-2 and it's faster this way).
1008
1009   for (size_t n = 0; n < d_n_code_outputs; n++) {
1010     memory_t t_mem = 0;
1011     for (size_t m = 0; m < d_n_code_inputs; m++) {
1012       t_mem ^= ((d_memory[d_states_ndx[maio(m,n)]]) &
1013                 d_code_generators[maio(m,n)]);
1014     }
1015     d_current_outputs[n] = sum_bits_mod2 (t_mem, d_max_delay);
1016   }
1017
1018   // post-shift & mask the memory to guarantee that output
1019   // state is in the correct bit positions (1 up, not the LSB)
1020
1021   for (size_t p = 0; p < d_n_memories; p++) {
1022     d_memory[p] = (d_memory[p] << 1) & d_max_mem_masks[p];
1023   }
1024
1025   if (DO_PRINT_DEBUG) {
1026     std::cout << "ending encode_loop_siao_fb.\n";
1027   }
1028 }