[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Commit-gnuradio] gr-error-correcting-codes/src/lib/libecc encode...
From: |
Michael Dickens |
Subject: |
[Commit-gnuradio] gr-error-correcting-codes/src/lib/libecc encode... |
Date: |
Wed, 05 Jul 2006 20:57:44 +0000 |
CVSROOT: /sources/gnuradio
Module name: gr-error-correcting-codes
Changes by: Michael Dickens <michaelld> 06/07/05 20:57:44
Added files:
src/lib/libecc : encoder_convolutional.cc
encoder_convolutional.h
encoder_convolutional_ic8_ic8.cc
encoder_convolutional_ic8_ic8.h
Log message:
Adding (back) encoder files.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc?cvsroot=gnuradio&rev=1.3
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h?cvsroot=gnuradio&rev=1.3
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.cc?cvsroot=gnuradio&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.h?cvsroot=gnuradio&rev=1.1
Patches:
Index: encoder_convolutional.cc
===================================================================
RCS file: encoder_convolutional.cc
diff -N encoder_convolutional.cc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder_convolutional.cc 5 Jul 2006 20:57:44 -0000 1.3
@@ -0,0 +1,730 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2006 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <encoder_convolutional.h>
+#include <assert.h>
+#include <iostream>
+
+#define DO_TIME_THOUGHPUT 1
+#define DO_PRINT_DEBUG 1
+
+#if DO_TIME_THOUGHPUT
+#include <mld/mld_timer.h>
+#endif
+#if DO_PRINT_DEBUG
+#include <mld/n2bs.h>
+#endif
+
+static const int g_max_frame_size_bits = 10000000;
+static const int g_max_num_streams = 10;
+
+void encoder_convolutional::encoder_convolutional_init
+(int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ bool do_termination,
+ int start_memory_state,
+ int end_memory_state)
+{
+ // do error checking on the input arguments
+
+ // make sure the frame length makes sense
+
+ if ((frame_size_bits < 0) | (frame_size_bits > g_max_frame_size_bits)) {
+ std::cerr << "encoder_convolutional: " <<
+ "Requested frame length (" << frame_size_bits <<
+ " bits) must be between 0 and " << g_max_frame_size_bits <<
+ " bits, with 0 being a streaming encoder.\n";
+ assert (0);
+ }
+
+ // check to make sure the number of input streams makes sense
+
+ if ((n_code_inputs <= 0) | (n_code_inputs > g_max_num_streams)) {
+ std::cerr << "encoder_convolutional: " <<
+ "Requested number of input streams (" <<
+ n_code_inputs << ") must be between 1 and " <<
+ g_max_num_streams << ".\n";
+ assert (0);
+ }
+
+ // check to make sure the number of output streams makes sense
+
+ if ((n_code_outputs <= 0) | (n_code_outputs > g_max_num_streams)) {
+ std::cerr << "encoder_convolutional: " <<
+ "Requested number of output streams (" <<
+ n_code_outputs << ") must be between 1 and " <<
+ g_max_num_streams << ".\n";
+ assert (0);
+ }
+
+ // make sure the code_generator is the correct length
+
+ if (code_generators.size () !=
+ ((size_t)(n_code_inputs * n_code_outputs))) {
+ std::cerr << "encoder_convolutional: " <<
+ "Number of code generator entries (" << code_generators.size () <<
+ ") is not equal to the product of the number of input and output" <<
+ " streams (" << (n_code_inputs * n_code_outputs) << ").\n";
+ assert (0);
+ }
+
+ // create the class frame variables
+
+ d_frame_size_bits = frame_size_bits;
+ d_n_code_inputs = n_code_inputs;
+ d_n_code_outputs = n_code_outputs;
+ d_do_streaming = (frame_size_bits == 0);
+ d_do_termination = (d_do_streaming == true) ? false : do_termination;
+
+ // allocate the vectors for doing the encoding. use memory_t (an
+ // interger type, at least 32 bits) bits to represent memory and the
+ // code, as it makes the operations quite simple the state vectors.
+
+ // d_states is a "matrix" [#input by #outputs] containing pointers
+ // to memory_t's; this is done to make feedback function properly,
+ // and doesn't effect the computation time for feedforward. The
+ // issue is that any code with the same feedback can use the same
+ // memory - thus reducing the actual number of memories required.
+ // These overlapping encoders will use the same actual memory, but
+ // given that there is no way to know a-priori where they are, use
+ // pointers over the full I/O matrix-space to make sure each I/O
+ // encoder uses the correct memory.
+ // reference the matrix using "maio(i,o)" ... see .h file.
+
+ d_states.assign (d_n_code_inputs * d_n_code_outputs, NULL);
+
+ // code generators (feedforward part) are [#inputs x #outputs],
+ // always - one for each I/O combination.
+ // reference the matrix using "maio(i,o)" ... see .h file
+
+ d_code_generators.assign (d_n_code_inputs * d_n_code_outputs, 0);
+
+ // for now, assign the feedback to the "1" for each code - meaning
+ // no feedback. Set the variable for feedback to "false".
+ // reference the matrix using "maio(i,o)" ... see .h file
+
+ d_code_feedback.assign (d_n_code_inputs * d_n_code_outputs, 1);
+ d_do_feedback = false;
+
+ // check the input code_generator for correctness & find the memory order
+ // t_max_mem will be the mamimum number of memories used by the generator
+
+ size_t t_max_mem = 0;
+
+ // loop over all input streams first, output streams second
+
+ for (size_t n = 0; n < d_n_code_outputs; n++) {
+ memory_t t_all_inputs_zero = 0;
+ for (size_t m = 0; m < d_n_code_inputs; m++) {
+ size_t t_in_code = d_code_generators[maio(m,n)] =
+ code_generators[maio(m,n)];
+
+ // check that not all codes for this input are 0
+
+ t_all_inputs_zero |= t_in_code;
+
+ // find the memory requirement for this code generator
+
+ size_t t_code_mem = 0;
+ while (t_in_code != 0) {
+ t_in_code >>= 1;
+ t_code_mem++;
+ }
+ if (t_code_mem > t_max_mem)
+ t_max_mem = t_code_mem;
+ }
+
+ // check this input to make sure all encoders were not '0'
+
+ if (t_all_inputs_zero == 0) {
+ std::cerr << "encoder_convolutional: " <<
+ "At least 1 generator code for output " << n+1 <<
+ " must be non-0.\n";
+ assert (0);
+ }
+ }
+
+ // store the maximum memory order (e.g. "2" -> D^2)
+
+ d_max_memory = t_max_mem - 1;
+
+ // make sure the frame length makes sense, #2
+
+ if ((d_frame_size_bits != 0) & (d_frame_size_bits < d_max_memory)) {
+ std::cerr << "encoder_convolutional: " <<
+ "Requested frame length (" << d_frame_size_bits <<
+ " bit" << (d_frame_size_bits > 1 ? "s" : "") <<
+ ") must be at least 1 memory length (" << d_max_memory <<
+ " bit" << (d_max_memory > 1 ? "s" : "") <<
+ " for this code) when doing block coding.\n";
+ assert (0);
+ }
+
+ // create the memory mask for this code generator
+
+ d_max_mem_mask = (2 << d_max_memory) - 1;
+
+// FIXME: STILL NEED TO parse START AND END MEMORY STATES;
+
+ // set the initial FSM state to 'init'
+
+ d_fsm_state = fsm_enc_conv_init;
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "Encoder:\n Mask = " <<
+ n2bs (d_max_mem_mask, d_max_memory+2) <<
+ "\n Max_Mem = " << d_max_memory << "\n.";
+ }
+
+ // by default no Feedback;
+ // setup for that from here down:
+ // 1 memory per input; same for init and term states;
+
+ d_n_memories = d_n_code_inputs;
+ d_memory.assign (d_n_code_inputs, 0);
+ d_init_states.assign (d_n_code_inputs, 0);
+ d_term_states.assign (d_n_code_inputs, 0);
+
+ // assign input numbers, one per memory
+
+ for (size_t n = 0; n < d_n_code_inputs; n++)
+ d_input_num[n] = n;
+
+ // assign d_states' pointers correctly
+ // loop over all I/O streams
+
+ for (size_t n = 0; n < d_n_code_outputs; n++)
+ for (size_t m = 0; m < d_n_code_inputs; m++)
+ d_states[maio(m,n)] = &(d_memory[m]);
+}
+
+encoder_convolutional::encoder_convolutional
+(int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ std::vector<int> &code_feedback,
+ bool do_termination,
+ int start_memory_state,
+ int end_memory_state)
+{
+ // call the general init routine, to parse inputs; deal with
+ // feedback after this parsing.
+
+ encoder_convolutional_init
+ (frame_size_bits,
+ n_code_inputs,
+ n_code_outputs,
+ code_generators,
+ do_termination,
+ start_memory_state,
+ end_memory_state);
+
+ // need to check the code_feedback to make sure it's valid; need to
+ // update the "d_max_memory" and comment back to the user if
+ // feedback is longer than feedforward. Otherwise, everything else
+ // is done by the super-class.
+
+ d_do_feedback = true;
+
+ // resize the memory and states to the max size, worst case
+
+ d_memory.assign (d_n_code_inputs * d_n_code_outputs, 0);
+ d_init_states.assign (d_n_code_inputs * d_n_code_outputs, 0);
+ d_term_states.assign (d_n_code_inputs * d_n_code_outputs, 0);
+ d_code_feedback.assign (d_n_code_inputs * d_n_code_outputs, 0);
+ d_input_num.assign (d_n_code_inputs * d_n_code_outputs, 0);
+
+ // check the code_feedback for correctness & find the memory order
+ // t_max_mem will be the mamimum number of memories used by the
+ // feedback; code_feedback will be in "input" first order, which is
+ // what is required internally.
+
+ size_t t_max_mem = d_n_memories = 0;
+ memory_t t_all_inputs_one = 0;
+
+ for (size_t n = 0; n < d_n_code_outputs; n++) {
+ size_t t_n_unique_fb_prev_start = d_n_memories;
+
+ for (size_t m = 0; m < d_n_code_inputs; m++) {
+ size_t t_save_code = code_feedback[maio(m,n)];
+ size_t t_in_code = t_save_code;
+
+ // check to make sure (code & 1) == 1; can't do this type of
+ // convolutional encoder without it!
+
+ if ((t_in_code & 1) != 1) {
+ std::cerr << "encoder_convolutional: " <<
+ "All feedback codes must contain a '1' for the least "
+ "significant bit.\n";
+ assert (0);
+ }
+
+ // find if this feedback is unique for this input;
+
+ size_t l_n_unique_fb = t_n_unique_fb_prev_start;
+ while (l_n_unique_fb < d_n_memories) {
+ if (d_code_feedback[l_n_unique_fb] == t_save_code)
+ break;
+ l_n_unique_fb++;
+ }
+ if (l_n_unique_fb == d_n_memories) {
+
+ // this is a unique feedback;
+ // create new entries for it in d_code_feedback and d_input_num
+
+ d_code_feedback[l_n_unique_fb] = t_save_code;
+ d_input_num[l_n_unique_fb] = m;
+
+ // update the "or" of all unique memories
+
+ t_all_inputs_one |= t_save_code;
+
+ // find the memory requirement for this code feedback
+
+ size_t t_code_mem = 0;
+ t_in_code = t_save_code;
+ while (t_in_code != 0) {
+ t_in_code >>= 1;
+ t_code_mem++;
+ }
+ if (t_code_mem > t_max_mem)
+ t_max_mem = t_code_mem;
+
+ // increase the number of unique feedback codes
+
+ d_n_memories++;
+ }
+
+ // create the new entry in d_states
+
+ d_states[maio(m,n)] = &(d_memory[l_n_unique_fb]);
+ }
+ }
+
+ // check to see if all the feedback entries were "1", which implies
+ // no feedback; warn the user in that case.
+
+ if (t_all_inputs_one == 1) {
+ std::cout << "encoder_convolutional: Warning: " <<
+ "No feedback is required, use of the non-feedback constructor "
+ "will provide higher throughput.\n";
+ }
+
+ // check to see if the feedback's memory requirements are greater
+ // than the feedforward's; warn the user (not sure why, but it seems
+ // like a good idea).
+
+ if (--t_max_mem > d_max_memory) {
+ std::cout << "encoder_convolutional: Warning: " <<
+ "Feedback using more memory than feedforward.\n";
+ d_max_memory = t_max_mem;
+
+ // make sure the frame length makes sense, #2
+
+ if ((d_do_streaming == true) & (d_frame_size_bits < d_max_memory)) {
+ std::cerr << "encoder_convolutional: " <<
+ "Requested frame length (" << d_frame_size_bits <<
+ " bit" << (d_frame_size_bits > 1 ? "s" : "") <<
+ ") must be at least 1 memory length (" << d_max_memory <<
+ " bit" << (d_max_memory > 1 ? "s" : "") <<
+ " for this code) when doing block coding.\n";
+ assert (0);
+ }
+
+ // create the memory mask for this code generator
+
+ d_max_mem_mask = (2 << d_max_memory) - 1;
+ }
+}
+
+void
+encoder_convolutional::encode_private
+(const char** in_buf,
+ char** out_buf)
+{
+#if DO_TIME_THOUGHPUT
+ struct timeval t_tp;
+ start_timer (&t_tp);
+#endif
+
+ // reset buffer indices
+
+ d_total_n_enc_bits = d_in_buf_ndx = d_out_buf_ndx =
+ d_in_bit_shift = d_out_bit_shift = 0;
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "Beginning this encode() call; starting parameters.\n";
+ std::cout << "d_n_input_bits_left = " << d_n_input_bits_left << '\n';
+ std::cout << "d_n_output_bits_left = " << d_n_output_bits_left << '\n';
+ }
+
+ // while there are inputs and outputs left to process ...
+
+ while ((d_n_input_bits_left != 0) & (d_n_output_bits_left != 0)) {
+
+ // jump to the correct state in the fsm
+
+ switch (d_fsm_state) {
+
+ case fsm_enc_conv_init:
+
+ // copy the init states to the current memory
+
+ d_memory = d_init_states;
+
+ // if not doing streaming, things to do; else nothing more do
+
+ if (d_do_streaming == false) {
+
+ // reset the number of encoded bits in this block (which is
+ // used to compare with the number of bits in the frame)
+
+ d_n_enc_bits = 0;
+ }
+
+ // move to the 'input' state
+
+ d_fsm_state = fsm_enc_conv_doing_input;
+ break;
+
+ case fsm_enc_conv_doing_input:
+
+ // working through the trellis section which requires input bits
+ // from external sources; loop up to the frame size (before
+ // termination bits, if any), counting down the number of
+ // available input bits.
+
+ encode_loop (in_buf, out_buf, &d_n_input_bits_left, d_frame_size_bits);
+
+ // finished this loop; check for jumping to the next state
+
+ if ((d_n_enc_bits == d_frame_size_bits) & (d_do_streaming == false)) {
+
+ // jump to another state, depending on termination requirement
+
+ if (d_do_termination == true) {
+ d_n_enc_bits = 0;
+ d_fsm_state = fsm_enc_conv_doing_term;
+ } else {
+ d_fsm_state = fsm_enc_conv_init;
+ }
+ }
+ break;
+
+ case fsm_enc_conv_doing_term:
+
+ // terminating the trellis, trying to get to a specific state;
+ // better get here only when do_termination is true, but check
+ // just in case; lop up to the max memory, counting down the
+ // number of output bits left
+
+ if (d_do_termination == false) {
+ encode_loop (in_buf, out_buf, &d_n_output_bits_left, d_max_memory);
+
+ // finished this loop; check for jumping to the next state
+
+ if (d_n_enc_bits == d_max_memory)
+ d_fsm_state = fsm_enc_conv_init;
+
+ } else {
+ // should never get here!
+ assert (0);
+ }
+ break;
+
+ default:
+ // better never get here!
+ assert (0);
+ break;
+
+ // done (switch) with FSM
+ }
+
+ // done (while) there are inputs and outputs
+ }
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "Done with this encode() call; ending parameters.\n"
+ "d_in_bit_shift = " << d_in_bit_shift << "\n"
+ "d_out_bit_shift = " << d_out_bit_shift << "\n"
+ "d_in_buf_ndx = " << d_in_buf_ndx << "\n"
+ "d_out_buf_ndx = " << d_out_buf_ndx << "\n"
+ "d_n_input_bits_left = " << d_n_input_bits_left << "\n"
+ "d_n_output_bits_left = " << d_n_output_bits_left << "\n"
+ "d_total_n_enc_bits = " << d_total_n_enc_bits << "\n";
+ }
+
+ if (DO_TIME_THOUGHPUT) {
+ // compute the throughput for this particular function call
+ u_long d_t = end_timer (&t_tp);
+ std::cout << "Completed " << d_total_n_enc_bits <<
+ " bits in " << d_t << " usec => " <<
+ 1e6*(((double) d_total_n_enc_bits)/((double) d_t)) <<
+ " b/s\n";
+ }
+}
+
+void
+encoder_convolutional::encode_loop
+(const char** in_buf,
+ char** out_buf,
+ size_t* which_counter,
+ size_t how_many)
+{
+ if (DO_PRINT_DEBUG) {
+ std::cout << "starting encode_loop.\n";
+ }
+ while (((*which_counter) > 0) & (d_n_enc_bits < how_many)) {
+ if (DO_PRINT_DEBUG) {
+ std::cout << "*w_c = " << (*which_counter) << ", "
+ "# enc_bits = " << d_n_enc_bits << " of " << how_many << ".\n"
+ "Getting new inputs.\n";
+ }
+
+ // get a new input bit per stream, and update the memory;
+ // loop over all inputs, push the current state bit into d_memory
+ // (which is pointed to by d_states, and thus both are updated).
+
+ for (size_t p = 0; p < d_n_memories; p++) {
+ if (DO_PRINT_DEBUG) {
+ std::cout << "mem_in[" << p << "] = " <<
+ n2bs (d_memory[p], d_max_memory+2) << "\n";
+ }
+
+ d_memory[p] |= get_next_bit (in_buf, d_input_num[p]);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "mem_out[" << p << "] = " <<
+ n2bs (d_memory[p], d_max_memory+2) << "\n";
+ }
+ }
+
+ // now encode those inputs using the code generators,
+ // and output a single bit per output stream
+
+ // loop over all outputs
+
+ for (size_t q = 0; q < d_n_code_outputs; q++) {
+ memory_t t_out_result = 0;
+
+ // loop over all inputs, xor'ing the result each time
+
+ for (size_t p = 0; p < d_n_code_inputs; p++) {
+ memory_t t_c_g = d_code_generators[maio(p,q)];
+ memory_t t_mem = (*(d_states[maio(p,q)]));
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "b_i = " <<
+ n2bs (t_out_result, d_max_memory+2) <<
+ ", st[" << p << "," << q << "] = " <<
+ n2bs (t_mem, d_max_memory+2) <<
+ ", cg[" << p << "," << q << "] = " <<
+ n2bs (t_c_g, d_max_memory+2) <<
+ ", st[] & cg[] = " <<
+ n2bs (t_mem & t_c_g, d_max_memory+2);
+ }
+
+ t_out_result ^= (t_mem & t_c_g);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << ", b_o = " <<
+ n2bs (t_out_result, d_max_memory+2) << '\n';
+ }
+ }
+ if (DO_PRINT_DEBUG) {
+ std::cout << "b_r = " << n2bs (t_out_result, d_max_memory+2);
+ }
+
+ // sum the number of set bits, mod 2, for the output bit
+
+ char t_out_bit = sum_bits_mod2 (t_out_result, d_max_memory);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "t_out_bit = mo2_sum (b_o) = " <<
+ n2bs (t_out_result, 2);
+ }
+
+ // output this particular bit on this output stream
+
+ output_bit (t_out_bit, out_buf, q);
+
+ // increment the input and output indices, if necessary, between
+ // output bits
+
+ increment_io_indices (true);
+ }
+
+ // do post-encoding memory mods (e.g. feedback); at a minimum:
+ // must shift memory to get ready for a new input bit, and mask
+ // off any extra bit from shifting (beyond a particular input's
+ // memory bits).
+
+ update_memory_post_encode ();
+
+ // increment the input and output counters, if necessary, between
+ // input bits
+
+ increment_io_indices (false);
+
+ // increment the number of encoded bits for the current block, and
+ // the total number of bits for this running of "encode()"
+
+ d_n_enc_bits++;
+ d_total_n_enc_bits++;
+
+ // decrement the number of input and output bits left
+
+ d_n_input_bits_left--;
+ d_n_output_bits_left--;
+ }
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "ending encode_loop.\n";
+ }
+}
+
+void
+encoder_convolutional::update_memory_post_encode
+()
+{
+ if (DO_PRINT_DEBUG) {
+ std::cout << "starting update_memory_post_encode.\n";
+ }
+
+ // update memory with any feedback, then shift up (left) by 1 bit
+ // and mask the memory state to be ready for the next input
+
+ // loop over all memories, shift the memory left (up) by 1 bit and
+ // mask off any high non-memory bit(s)
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " doing memory shift and mask:\n";
+ }
+
+ for (size_t p = 0; p < d_n_memories; p++) {
+ if (DO_PRINT_DEBUG) {
+ std::cout << " mem_in[" << p << "] = " <<
+ n2bs (d_memory[p], d_max_memory+2) << "\n";
+ }
+
+ d_memory[p] = (d_memory[p] << 1) & d_max_mem_mask;
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " mem_out[" << p << "] = " <<
+ n2bs (d_memory[p], d_max_memory+2) << "\n";
+ }
+ }
+
+ if (d_do_feedback == true) {
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " doing feedback:\n";
+ }
+
+ // loop over all unique memories, creating the feedback bit for each
+ // and placing those bits in the state's second bit location
+
+ for (size_t p = 0; p < d_n_memories; p++) {
+ if (DO_PRINT_DEBUG) {
+ std::cout << " mem_in[" << p << "] = " <<
+ n2bs (d_memory[p], d_max_memory+2) << "\n";
+ }
+
+ // do feedback with current memory
+ // get the memory, and zero out the second bit
+
+ memory_t t_state = d_memory[p] & (d_max_mem_mask ^ 2);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " t_state = mem[] & (" << d_max_mem_mask <<
+ " xor 2) = " << n2bs (t_state, d_max_memory+2) << "\n";
+ }
+
+ // create the code feedback state
+
+ memory_t t_fb_state = t_state & (d_code_feedback[p]);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " t_fb_state = t_state & {fb[" << p << "] == " <<
+ d_code_feedback[p] << "} = " <<
+ n2bs (t_fb_state, d_max_memory+2) << "\n";
+ }
+
+ // mod2 sum the feedback state to get the feedback bit value
+
+ char t_fb_bit = sum_bits_mod2 (t_fb_state, d_max_memory);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " t_fb_bit = mod2_sum (t_fb_state) = " <<
+ n2bs (t_fb_bit, 2) << "\n";
+ }
+
+ // place the feedback bit into the second state bit
+
+ d_memory[p] = t_state | (t_fb_bit << 1);
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << " mem_out[" << p << "] = t_state | (fb_bit << 1) = " <<
+ n2bs (d_memory[p], d_max_memory+2) << "\n";
+ }
+ }
+ }
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "ending update_memory_post_encode.\n";
+ }
+}
+
+char
+encoder_convolutional::get_next_bit
+(const char** in_buf,
+ size_t code_input_n)
+{
+ char ret_val = 0;
+ switch (d_fsm_state) {
+ case fsm_enc_conv_doing_input:
+ ret_val = get_next_bit__input (in_buf, code_input_n);
+ break;
+ case fsm_enc_conv_doing_term:
+ ret_val = get_next_bit__term (code_input_n);
+ break;
+ default:
+ assert (0);
+ break;
+ }
+ return (ret_val);
+}
+
+char
+encoder_convolutional::get_next_bit__term
+(size_t code_input_n)
+{
+ // FIXME: how to figure out which term bit to get?
+ return (d_term_states[code_input_n] & 1);
+}
Index: encoder_convolutional.h
===================================================================
RCS file: encoder_convolutional.h
diff -N encoder_convolutional.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder_convolutional.h 5 Jul 2006 20:57:44 -0000 1.3
@@ -0,0 +1,196 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2006 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifndef INCLUDED_ENCODER_CONVOLUTIONAL_H
+#define INCLUDED_ENCODER_CONVOLUTIONAL_H
+
+#include <vector>
+#include "encoder.h"
+
+class encoder_convolutional : public encoder
+{
+public:
+/*!
+ * class encoder_convolutional : public encoder
+ *
+ * Encode the incoming streams using a convolutional encoder; This is
+ * a virtual class which defines the basics of a convolutional
+ * encoder, but not how input and output bits are handled, nor
+ * feedback in the encoder. These features are all defined by
+ * overriding methods appropriately.
+ *
+ * frame_size_bits: if == 0, then do streaming encoding ("infinite"
+ * trellis); otherwise this is the frame size in bits to encode
+ * before terminating the trellis. This value -does not- include
+ * any termination bits.
+ *
+ * n_code_inputs:
+ * n_code_outputs:
+ * code_generator: vector of integers (32 bit) representing the code
+ * to be implemented. E.g. "4" in binary is "100", which would be
+ * "D^2" for code generation. "6" == 110b == "D^2 + D"
+ * ==> The vector is listed in order for each output stream, so if there
+ * are 2 input streams (I1, I2) [specified in "n_code_inputs"]
+ * and 2 output streams (O1, O2) [specified in "n_code_outputs"],
+ * then the vector would be the code generator for:
+ * [I1->O1, I2->O1, I1->O2, I2->O2]
+ * with each element being an integer representation of the code.
+ *
+ * do_termination: valid only if frame_size_bits != 0, and defines
+ * whether or not to use trellis termination. Default is to use
+ * termination when doing block coding.
+ *
+ * start_memory_state: when starting a new block, the starting memory
+ * state to begin encoding; there will be a helper function to
+ * assist in creating this value for a given set of inputs;
+ * default is the "all zero" state.
+ *
+ * end_memory_state: when terminating a block, the ending memory
+ * state to stop encoding; there will be a helper function to
+ * assist in creating this value for a given set of inputs;
+ * default is the "all zero" state.
+ */
+
+ inline encoder_convolutional (int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ bool do_termination = true,
+ int start_memory_state = 0,
+ int end_memory_state = 0)
+ {encoder_convolutional_init (frame_size_bits,
+ n_code_inputs,
+ n_code_outputs,
+ code_generators,
+ do_termination,
+ start_memory_state,
+ end_memory_state);};
+
+/*!
+ * Encoder with feedback.
+ *
+ * code_feedback: vector of integers (32 bit) representing the code
+ * feedback to be implemented (same as for the
+ * code_generator). For this feedback type, the LSB ("& 1") must
+ * be equal to 1 ... the represents the input bit for the given
+ * encoder, without which there would be no encoding! Each
+ * successive higher-order bit represents the output of that
+ * delay block; for example "6" == 110b == "D^2 + D" means use
+ * the current input bit + the output of the second delay block.
+ * Listing order is the same as for the code_generator.
+ */
+
+ encoder_convolutional (int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ std::vector<int> &code_feedback,
+ bool do_termination = true,
+ int start_memory_state = 0,
+ int end_memory_state = 0);
+
+ virtual ~encoder_convolutional () {};
+
+protected:
+/*
+ * fsm_enc_conv_t: finite state machine for the convolutional encoder;
+ * output happens all the time, so that's built-in to each state.
+ *
+ * fsm_enc_conv_init: initialize for a new frame / block; this is already
+ * done at instantiation, so do it only at the end of a block.
+ *
+ * fsm_enc_conv_doing_input: doing encoding inside the trellis
+ *
+ * fsm_enc_conv_doing_term: termination trellis, if requested
+ */
+
+ enum fsm_enc_conv_t {
+ fsm_enc_conv_init, fsm_enc_conv_doing_input, fsm_enc_conv_doing_term
+ };
+
+/*
+ * maio(i,o): matrix access into a vector, knowing the # of code
+ * outputs (from inside the class). References into a vector with
+ * code inputs ordered by code output.
+ *
+ * 'i' is the first dimension - immediate memory order first - the code input
+ * 'o' is the second dimension - slower memory order second - the code output
+ *
+ * returns ((o*n_code_outputs) + i)
+ */
+
+ inline size_t maio(size_t i, size_t o) {return ((o*d_n_code_outputs) + i);};
+
+/*
+ * maoi(i,o): matrix access into a vector, knowing the # of code
+ * inputs (from inside the class). References into a vector with
+ * code outputs ordered by code input.
+ *
+ * 'o' is the first dimension - immediate memory order first - the code output
+ * 'i' is the second dimension - slower memory order second - the code input
+ *
+ * returns ((i*n_code_inputs) + o)
+ */
+
+ inline size_t maoi(size_t i, size_t o) {return ((i*d_n_code_inputs) + o);};
+
+ // methods defined in this class
+
+ void encoder_convolutional_init (int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ bool do_termination,
+ int start_memory_state,
+ int end_memory_state);
+ virtual void encode_private (const char** in_buf, char** out_buf);
+ virtual void encode_loop (const char** in_buf, char** out_buf,
+ size_t* which_counter, size_t how_many);
+ virtual char get_next_bit (const char** in_buf, size_t code_input_n);
+ virtual char get_next_bit__term (size_t code_input_n);
+ virtual void update_memory_post_encode ();
+
+ // methods which are required by classes which inherit from this
+ // one; primarily just the parts which deal with getting input bits
+ // and writing output bits, changing the indices for those buffers.
+
+ virtual char get_next_bit__input (const char** in_buf,
+ size_t code_input_n) = 0;
+ virtual void increment_io_indices (bool while_encoding) = 0;
+
+ // variables
+
+ fsm_enc_conv_t d_fsm_state;
+ bool d_do_streaming, d_do_termination, d_do_feedback;
+ size_t d_n_memories;
+
+ // code generators and feedback are stored internally in "maXY(i,o)"
+ // order this allows for looping over all a single output and
+ // computing all input parts sequentially.
+
+ std::vector<memory_t> d_code_generators, d_code_feedback;
+ std::vector<memory_ptr_t> d_states;
+ std::vector<memory_t> d_memory, d_init_states, d_term_states;
+ std::vector<size_t> d_input_num;
+};
+
+#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_H */
Index: encoder_convolutional_ic8_ic8.cc
===================================================================
RCS file: encoder_convolutional_ic8_ic8.cc
diff -N encoder_convolutional_ic8_ic8.cc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder_convolutional_ic8_ic8.cc 5 Jul 2006 20:57:44 -0000 1.1
@@ -0,0 +1,224 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2006 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <encoder_convolutional_ic8_ic8.h>
+#include <assert.h>
+#include <iostream>
+
+#define DO_TIME_THOUGHPUT 1
+#define DO_PRINT_DEBUG 1
+
+#if DO_TIME_THOUGHPUT
+#include <mld/mld_timer.h>
+#endif
+#if DO_PRINT_DEBUG
+#include <mld/n2bs.h>
+#endif
+
+// FIXME: when doing packed, should probably allow user to select how
+// bits are selected, so-as to make sure it's always the same
+// no matter the CPU endianness
+
+// FIXME
+size_t
+encoder_convolutional_ic8_ic8::compute_n_output_bits
+(size_t n_input_bits)
+{
+ assert (0);
+ return (0);
+}
+
+/*
+ * Compute the number of input bits needed to produce
+ * 'n_output' bits. For convolutional encoders, there is
+ * 1 bit output per bit input per stream, with the addition of a some
+ * bits for trellis termination if selected. Thus the input:output
+ * bit ratio will be:
+ *
+ * if (streaming | no termination), 1:1
+ *
+ * if (not streaming & termination), roughly 1:(1+X), where "X" is the
+ * total memory size of the code divided by the block length in bits.
+ * But this also depends on the state of the FSM ... how many bits are
+ * left before termination.
+ *
+ * The returned value will also depend on whether bits are packed, as
+ * well as whether streams are mux'ed together.
+ */
+
+size_t
+encoder_convolutional_ic8_ic8::compute_n_input_bits
+(size_t n_output_bits)
+{
+ size_t t_n_output_bits, t_n_input_bits;
+ t_n_output_bits = t_n_input_bits = n_output_bits;
+
+ if (d_do_termination == true) {
+
+ // not streaming, doing termination; find the number of bits
+ // currently available with no required inputs, if any
+
+ size_t n_extra = 0;
+ if (d_fsm_state == fsm_enc_conv_doing_term) {
+ n_extra = d_max_memory - d_n_enc_bits;
+ }
+
+ // check to see if this is enough; return 0 if it is.
+
+ if (n_extra >= t_n_output_bits)
+ return (0);
+
+ // remove those which require no input
+
+ t_n_output_bits -= n_extra;
+
+ // find the number of frames of data which could be processed
+
+ size_t t_n_output_bits_per_frame = d_frame_size_bits + d_max_memory;
+
+ // get the base number of input items required for the given
+ // number of frames to be generated
+
+ size_t t_n_frames = t_n_output_bits / t_n_output_bits_per_frame;
+ t_n_input_bits = t_n_frames * d_frame_size_bits;
+
+ // add to that the number of leftover inputs needed to generate
+ // the remainder of the outputs within the remaining frame, up to
+ // the given frame size (since anything beyond that within this
+ // frame requires no inputs)
+
+ size_t t_leftover_bits = t_n_output_bits % t_n_output_bits_per_frame;
+ t_n_input_bits += ((t_leftover_bits > d_frame_size_bits) ?
+ d_frame_size_bits : t_leftover_bits);
+ }
+
+ return (t_n_input_bits);
+}
+
+void
+encoder_convolutional_ic8_ic8::increment_io_indices
+(bool while_encoding)
+{
+ // increment the buffer index only for this version, only after
+ // encoding is done and all resulting outputs are stored on the
+ // output streams
+
+ if (while_encoding == false) {
+ d_out_buf_ndx++;
+ d_in_buf_ndx++;
+ }
+
+ // nothing to do while encoding, so no else
+
+#if 0
+// move counters to the next input bit, wrapping to the next input
+// byte as necessary
+ if (++d_in_bit_shift % g_num_bits_per_byte == 0) {
+ d_in_bit_shift = 0;
+ d_in_buf_ndx++;
+ }
+// move counters to the next output bit, wrapping to the next output
+// byte as necessary
+ if (++d_out_bit_shift % g_num_bits_per_byte == 0) {
+ d_out_bit_shift = 0;
+ d_out_buf_ndx++;
+ }
+#endif
+}
+
+void
+encoder_convolutional_ic8_ic8::output_bit
+(char t_out_bit,
+ char** out_buf,
+ size_t t_output_stream)
+{
+ // store the result for this particular output stream
+ // one bit per output item for "ic8" type output
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << ", O_i[" << t_output_stream <<
+ "][" << d_out_buf_ndx << "] = " <<
+ n2bs (out_buf[t_output_stream][d_out_buf_ndx], 2);
+ }
+
+ out_buf[t_output_stream][d_out_buf_ndx] = t_out_bit;
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << ", b_out = " << t_out_bit <<
+ ", O_o[" << t_output_stream << "][" << d_out_buf_ndx << "][" <<
+ d_out_bit_shift << "] = " <<
+ n2bs (out_buf[t_output_stream][d_out_buf_ndx], 2) << '\n';
+ }
+
+#if 0
+#if DO_PRINT_DEBUG
+ std::cout << ", O_i[" << t_output_stream <<
+ "][" << d_out_buf_ndx << "] = " <<
+ n2bs (out_buf[t_output_stream][d_out_buf_ndx], g_num_bits_per_byte);
+#endif
+
+// packed bits in each output item
+ out_buf[t_output_stream][d_out_buf_ndx] |=
+ (t_out_bit << d_out_bit_shift);
+
+#if DO_PRINT_DEBUG
+ std::cout << ", b_out = " << t_out_bit <<
+ ", O_o[" << t_output_stream << "][" << d_out_buf_ndx << "][" <<
+ d_out_bit_shift << "] = " <<
+ n2bs (out_buf[t_output_stream][d_out_buf_ndx], g_num_bits_per_byte) <<
'\n';
+#endif
+#endif
+}
+
+char
+encoder_convolutional_ic8_ic8::get_next_bit__input
+(const char** in_buf,
+ size_t code_input_n)
+{
+ // get a bit from this particular input stream
+ // one bit per output item for "ic8" type input
+
+ if (DO_PRINT_DEBUG) {
+ std::cout << "I[" << p << "][" << d_in_buf_ndx << "] = ";
+ cout_binary (t_next_bit, g_num_bits_per_byte);
+ std::cout << ", st_i[" << p << "] = ";
+ cout_binary ((*t_states_ptr), d_max_memory+2);
+ std::cout << ", I[" << p << "][" << d_in_buf_ndx << "][" <<
+ d_in_bit_shift << "] = " << t_next_bit <<
+ ", st_o[" << p << "] = ";
+ cout_binary (t_state, d_max_memory+2);
+ std::cout << '\n';
+ }
+
+ return ((in_buf[code_input_n][d_in_buf_ndx] >> d_in_bit_shift) & 1);
+}
+
+char
+encoder_convolutional_ic8_ic8::get_next_bit__term
+(size_t code_input_n)
+{
+ return ((d_term_states[code_input_n] >> d_in_bit_shift) & 1);
+}
Index: encoder_convolutional_ic8_ic8.h
===================================================================
RCS file: encoder_convolutional_ic8_ic8.h
diff -N encoder_convolutional_ic8_ic8.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder_convolutional_ic8_ic8.h 5 Jul 2006 20:57:44 -0000 1.1
@@ -0,0 +1,94 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2006 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING. If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifndef INCLUDED_ENCODER_CONVOLUTIONAL_IC8_IC8_H
+#define INCLUDED_ENCODER_CONVOLUTIONAL_IC8_IC8_H
+
+#include "encoder_convolutional.h"
+
+/*!
+ * class encoder_convolutional_ic8_ic8 : public encoder_convolutional
+ *
+ * Encode the incoming streams using a convolutional encoder,
+ * "feedforward" or feedback. Optional termination, data
+ * streaming, and starting and ending memory states.
+ *
+ * input is "ic8": streams of char, one stream per input as defined by the
+ * instantiated code, using all 8 bits in the char.
+ *
+ * FIXME: need to have inputs for MSB or LSB first input and output.
+ *
+ * output is "ic8": streams of char, one stream per output as defined by the
+ * instantiated code, using all 8 bits in the char.
+ */
+
+class encoder_convolutional_ic8_ic8 : public encoder_convolutional
+{
+public:
+ inline encoder_convolutional_ic8_ic8 (int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ bool do_termination = true,
+ int start_memory_state = 0,
+ int end_memory_state = 0)
+ : encoder_convolutional (frame_size_bits,
+ n_code_inputs,
+ n_code_outputs,
+ code_generators,
+ do_termination,
+ start_memory_state,
+ end_memory_state) {};
+
+ inline encoder_convolutional_ic8_ic8 (int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ std::vector<int> &code_feedback,
+ bool do_termination = true,
+ int start_memory_state = 0,
+ int end_memory_state = 0)
+ : encoder_convolutional (frame_size_bits,
+ n_code_inputs,
+ n_code_outputs,
+ code_generators,
+ code_feedback
+ do_termination,
+ start_memory_state,
+ end_memory_state) {};
+
+ virtual ~encoder_convolutional_ic8_ic8 () {};
+
+ virtual size_t compute_n_input_bits (size_t n_output_bits);
+ virtual size_t compute_n_output_bits (size_t n_input_bits);
+
+protected:
+ virtual char get_next_bit__input (const char** in_buf,
+ size_t code_input_n);
+ virtual char get_next_bit__term (size_t code_input_n);
+ virtual void output_bit (char t_out_bit, char** out_buf,
+ size_t t_output_stream);
+ virtual void increment_io_indices (bool while_encoding);
+ virtual void update_memory_post_encode ();
+};
+
+#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_IC8_IC8_H */