[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Commit-gnuradio] gr-error-correcting-codes/src/lib/libecc Makefi...
|
From: |
Michael Dickens |
|
Subject: |
[Commit-gnuradio] gr-error-correcting-codes/src/lib/libecc Makefi... |
|
Date: |
Tue, 04 Jul 2006 01:53:35 +0000 |
CVSROOT: /sources/gnuradio
Module name: gr-error-correcting-codes
Changes by: Michael Dickens <michaelld> 06/07/04 01:53:35
Modified files:
src/lib/libecc : Makefile.am code_metrics.h encoder.h
Added files:
src/lib/libecc : decoder.h decoder_viterbi_base.h encoder.cc
encoder_convolutional_base.cc
encoder_convolutional_base.h
Removed files:
src/lib/libecc : encoder_convolutional.cc
encoder_convolutional.h
Log message:
Separated encoder into a base class type which defines the basic
methods and variables for general use. Other classes specify IO
functionality via inheritance from the base class. Updated Makefile
to reflect this change. Naming is (for now) "ic1" means "individual
streams" (not mux'ed), "char" input type, "1" bit per to incode
... might change or add to these later if this doesn't make enough
sense, bit I think I'll create a static master function to call which
returns the correct class type for the given inputs, no matter the
(odd) naming. Obviously this could be directly overridden by the
user, but it would provide a clean starting point for the user.
Started work on the decoder classes, moving over functionality from
the '..' directory's gr_block for viterbi decoding.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/Makefile.am?cvsroot=gnuradio&r1=1.1&r2=1.2
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/code_metrics.h?cvsroot=gnuradio&r1=1.1&r2=1.2
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder.h?cvsroot=gnuradio&r1=1.1&r2=1.2
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/decoder.h?cvsroot=gnuradio&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_base.h?cvsroot=gnuradio&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder.cc?cvsroot=gnuradio&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_base.cc?cvsroot=gnuradio&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_base.h?cvsroot=gnuradio&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc?cvsroot=gnuradio&r1=1.1&r2=0
http://cvs.savannah.gnu.org/viewcvs/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h?cvsroot=gnuradio&r1=1.1&r2=0
Patches:
Index: Makefile.am
===================================================================
RCS file:
/sources/gnuradio/gr-error-correcting-codes/src/lib/libecc/Makefile.am,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -b -r1.1 -r1.2
--- Makefile.am 3 Jul 2006 02:14:12 -0000 1.1
+++ Makefile.am 4 Jul 2006 01:53:35 -0000 1.2
@@ -28,10 +28,13 @@
noinst_LTLIBRARIES = libecc.la
libecc_la_SOURCES = \
- encoder_convolutional.cc code_metrics.cc
+ encoder.cc code_metrics.cc encoder_convolutional_base.cc \
+ encoder_convolutional_ic1_ic1_ff.cc
noinst_HEADERS = \
- encoder.h encoder_convolutional.h code_metrics.h
+ encoder.h code_metrics.h encoder_convolutional_base.h \
+ encoder_convolutional_ic1_ic1_ff.h \
+ decoder.h decoder_viterbi.h
# link the library against the c++ standard library
libecc_la_LIBADD = \
Index: code_metrics.h
===================================================================
RCS file:
/sources/gnuradio/gr-error-correcting-codes/src/lib/libecc/code_metrics.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -b -r1.1 -r1.2
--- code_metrics.h 3 Jul 2006 02:14:12 -0000 1.1
+++ code_metrics.h 4 Jul 2006 01:53:35 -0000 1.2
@@ -23,7 +23,6 @@
#include <sys/types.h>
#include <vector>
-#include <assert.h>
class code_metrics
{
Index: encoder.h
===================================================================
RCS file: /sources/gnuradio/gr-error-correcting-codes/src/lib/libecc/encoder.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -b -r1.1 -r1.2
--- encoder.h 3 Jul 2006 02:14:12 -0000 1.1
+++ encoder.h 4 Jul 2006 01:53:35 -0000 1.2
@@ -40,10 +40,17 @@
virtual size_t compute_n_output_bits (size_t n_input_bits) = 0;
virtual size_t encode (const char** in_buf,
char** out_buf,
- size_t n_bits_to_output) = 0;
+ size_t n_bits_to_output);
virtual size_t encode (const char** in_buf,
size_t n_bits_to_input,
- char** out_buf) = 0;
+ char** out_buf);
+ virtual char sum_bits_mod2 (memory_t in_mem, size_t max_memory);
+
+protected:
+ virtual void encode_private (const char** in_buf, char** out_buf) = 0;
+ virtual char get_next_bit (const char** in_buf, size_t code_input_n) = 0;
+ virtual void output_bit (char t_out_bit, char** out_buf,
+ size_t t_output_stream) = 0;
size_t d_frame_size_bits, d_n_code_inputs, d_n_code_outputs;
size_t d_max_memory, d_n_enc_bits;
Index: decoder.h
===================================================================
RCS file: decoder.h
diff -N decoder.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ decoder.h 4 Jul 2006 01:53:35 -0000 1.1
@@ -0,0 +1,56 @@
+/* -*- c++ -*- */
+/*
+ * Copyright @ 2006 Michael Dickens
+ *
+ * This library 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.
+ *
+ * This library 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 this library; 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_DECODER_H
+#define INCLUDED_DECODER_H
+
+#include <sys/types.h>
+
+// the following is the type used for decoder memory
+
+typedef unsigned long memory_t, *memory_ptr_t;
+
+// the 'decoder' class is a virtual class upon which all decoder types
+// can be built.
+
+class decoder
+{
+public:
+ decoder () {};
+ virtual ~decoder () {};
+
+ virtual size_t compute_n_input_bits (size_t n_output_bits) = 0;
+ virtual size_t compute_n_output_bits (size_t n_input_bits) = 0;
+ virtual size_t decode (const char** in_buf,
+ char** out_buf,
+ size_t n_bits_to_output) = 0;
+ virtual size_t decode (const char** in_buf,
+ size_t n_bits_to_input,
+ char** out_buf) = 0;
+
+ size_t d_frame_size_bits, d_n_code_inputs, d_n_code_outputs;
+ size_t d_max_memory, d_n_enc_bits;
+ memory_t d_max_mem_mask;
+ memory_t d_in_buf_ndx, d_out_buf_ndx;
+ memory_t d_in_bit_shift, d_out_bit_shift;
+ size_t d_n_input_bits_left, d_n_output_bits_left;
+};
+
+#endif /* INCLUDED_DECODER_H */
Index: decoder_viterbi_base.h
===================================================================
RCS file: decoder_viterbi_base.h
diff -N decoder_viterbi_base.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ decoder_viterbi_base.h 4 Jul 2006 01:53:35 -0000 1.1
@@ -0,0 +1,137 @@
+/* -*- c++ -*- */
+/*
+ * Copyright @ 2006 Michael Dickens
+ *
+ * This library 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.
+ *
+ * This library 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 this library; 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_DECODER_VITERBI_H
+#define INCLUDED_DECODER_VITERBI_H
+
+#include <vector>
+#include "decoder.h"
+
+/*!
+ * \brief Decode the incoming metrics streams using the Viterbi algorithm.
+ *
+ * input: streams of metrics,
+ *
+ * output: streams of char, one stream per output as defined by the
+ * instantiated code, using only the right-most justified bit as
+ * the single output bit per output item.
+ */
+
+class decoder_viterbi : public decoder
+{
+public:
+/*
+ * frame_size_bits: if == 0, then do streaming encoding ("infinite"
+ * trellis); otherwise this is the frame size in bits to decode
+ * 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 in octal form. E.g. "04" in binary is "100",
+ * which would be "D^2" for code generation. "06" == 110b == "D^2 + D"
+ * ==> The vector is listed in order for each input 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, I1->O2, I2->O1, I2->O2]
+ * with each element being the octal 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.
+ */
+
+ decoder_viterbi (int frame_size_bits,
+ int n_code_inputs,
+ int n_code_outputs,
+ std::vector<int> &code_generators,
+ int start_memory_state = 0,
+ int end_memory_state = 0,
+ bool do_termination = true,
+ bool use_muxed_inputs = false,
+ bool do_muxed_outputs = false,
+ bool use_packed_input = false,
+ bool do_packed_outputs = false);
+
+ virtual ~decoder_viterbi () {};
+
+ virtual size_t compute_n_input_bits (size_t n_output_bits);
+ virtual size_t compute_n_output_bits (size_t n_input_bits);
+ virtual size_t decode (const char** in_buf,
+ char** out_buf,
+ size_t n_bits_to_output);
+ virtual size_t decode (const char** in_buf,
+ size_t n_bits_to_input,
+ char** out_buf);
+
+private:
+/*
+ * fsm_dec_viterbi_t: finite state machine for the convolutional decoder;
+ * output happens all the time, so that's built-in to each state.
+ *
+ * fsm_dec_viterbi_init: initialize for a new frame / block; this is already
+ * done at instantiation, so do it only at the end of a block.
+ *
+ * fsm_dec_viterbi_doing_up: encoding at the start of a block
+ *
+ * fsm_dec_viterbi_doing_middle: doing encoding inside the trellis
+ *
+ * fsm_dec_viterbi_doing_term: termination trellis, if requested
+ */
+
+ enum fsm_dec_viterbi_t {
+ fsm_dec_viterbi_init, fsm_dec_viterbi_doing_up,
+ fsm_dec_viterbi_doing_middle, fsm_dec_viterbi_doing_term
+ };
+
+ virtual void decode_private (const char** in_buf, char** out_buf);
+ virtual void decode_loop (const char** in_buf, char** out_buf,
+ size_t* which_counter, size_t how_many);
+ virtual char get_new_input_bit (const char** in_buf, size_t code_input_n);
+ virtual char get_new_input_bit__up (const char** in_buf,
+ size_t code_input_n);
+ virtual char get_new_input_bit__middle (const char** in_buf,
+ size_t code_input_n);
+ virtual char get_new_input_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_counters (bool while_encoding);
+
+ fsm_dec_viterbi_t d_fsm_state;
+ bool d_use_muxed_inputs, d_do_muxed_outputs;
+ bool d_use_packed_input, d_do_packed_outputs;
+ bool d_do_streaming, d_do_termination;
+ std::vector<memory_t> d_code_generators;
+ std::vector<memory_t> d_states, d_init_states, d_term_states;
+};
+
+#endif /* INCLUDED_DECODER_VITERBI_H */
Index: encoder.cc
===================================================================
RCS file: encoder.cc
diff -N encoder.cc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder.cc 4 Jul 2006 01:53:35 -0000 1.1
@@ -0,0 +1,123 @@
+/* -*- c++ -*- */
+/*
+ * Copyright @ 2006 Michael Dickens
+ *
+ * This library 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.
+ *
+ * This library 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 this library; 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.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
+
+// sum the number of set bits, mod 2, for the output bit
+char
+encoder::sum_bits_mod2 (memory_t in_mem, size_t max_memory)
+{
+// there are faster ways to do this, but this works for now; could
+// certainly do a single inline asm, which most processors provide to
+// deal with summing the bits in an integer
+
+// this routine can be overridden by another method if desired.
+
+ char t_out_bit = (char)(in_mem & 1);
+ for (size_t r = max_memory; r > 0; r--) {
+ in_mem >>= 1;
+ t_out_bit ^= ((char)(in_mem & 1));
+ }
+ return (t_out_bit);
+}
+
+
+size_t
+encoder::encode (const char** in_buf,
+ char** out_buf,
+ size_t n_bits_to_output)
+{
+// set the class-internal number of input and
+// output bits left to encode
+ size_t saved_n_input_bits;
+ saved_n_input_bits = d_n_input_bits_left =
+ compute_n_input_bits (n_bits_to_output);
+ d_n_output_bits_left = n_bits_to_output;
+
+// call the private encode function
+ encode_private (in_buf, out_buf);
+
+#ifdef DO_PRINT_DEBUG
+ std::cout << "n_input_bits_used = " <<
+ (saved_n_input_bits - d_n_input_bits_left) << '\n';
+ std::cout << "n_output_bits_used = " <<
+ (n_bits_to_output - d_n_output_bits_left) << '\n';
+
+ assert (d_out_buf_ndx == n_bits_to_output);
+#endif
+
+// return the actual number of input bits used
+ return (saved_n_input_bits - d_n_input_bits_left);
+}
+
+/*
+ * encode a certain number of input bits
+ *
+ * the 'in_buf' and 'out_buf' must have enough memory to handle the
+ * number of input and output bits; no error checking is done!
+ *
+ * n_bits_to_input: is the number of input bits per input stream to encode
+ *
+ * returns the number of actual bits written to the output stream(s)
+ */
+
+size_t
+encoder::encode (const char** in_buf,
+ size_t n_bits_to_input,
+ char** out_buf)
+{
+// set the class-internal number of input and
+// output bits left to encode
+ size_t saved_n_output_bits;
+ saved_n_output_bits = d_n_output_bits_left =
+ compute_n_output_bits (n_bits_to_input);
+ d_n_input_bits_left = n_bits_to_input;
+
+// call the private encode function
+ encode_private (in_buf, out_buf);
+
+#ifdef DO_PRINT_DEBUG
+ std::cout << "n_input_bits_used = " <<
+ (n_bits_to_input - d_n_input_bits_left) << '\n';
+ std::cout << "n_output_bits_used = " <<
+ (saved_n_output_bits - d_n_output_bits_left) << '\n';
+
+ assert (d_in_buf_ndx == n_bits_to_input);
+#endif
+
+// return the actual number of input bits used
+ return (saved_n_output_bits - d_n_output_bits_left);
+}
Index: encoder_convolutional_base.cc
===================================================================
RCS file: encoder_convolutional_base.cc
diff -N encoder_convolutional_base.cc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder_convolutional_base.cc 4 Jul 2006 01:53:35 -0000 1.1
@@ -0,0 +1,400 @@
+/* -*- c++ -*- */
+/*
+ * Copyright @ 2006 Michael Dickens
+ *
+ * This library 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.
+ *
+ * This library 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 this library; 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_base.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;
+static const int g_num_bits_per_byte = 8;
+
+encoder_convolutional_base::encoder_convolutional_base
+(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)
+{
+// 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 32-bit int's
+// actual bits to represent memory and the code, as it makes the
+// operations quite simple the state vectors.
+// states are per each input,
+// code generates are for each I/O combination
+
+ d_states.assign (d_n_code_inputs, 0);
+ d_init_states.assign (d_n_code_inputs, 0);
+ d_term_states.assign (d_n_code_inputs, 0);
+ d_code_generators.assign (d_n_code_inputs * d_n_code_outputs, 0);
+
+// FIXME: STILL NEED TO COPY OVER START AND END MEMORY STATES;
+
+// 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
+// t_code_ndx is a counter over all input code_generator elements
+ size_t t_max_mem = 0, t_code_ndx = d_code_generators.size() - 1;
+// loop over all input streams first, output streams second
+ for (int n = d_n_code_outputs - 1; n >= 0; n--) {
+ size_t t_all_inputs_zero = 0;
+ for (int m = d_n_code_inputs - 1; m >= 0; m--) {
+ size_t t_in_code = code_generators[t_code_ndx];
+ t_all_inputs_zero |= t_in_code;
+ size_t t_code_mem = 0;
+// find the memory requirement for this code generator
+ 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;
+// store in d_code_generators in output-first ordering
+ d_code_generators[(m*d_n_code_outputs) + n] =
+ code_generators[t_code_ndx--];
+ }
+ 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 constraint 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;
+
+// set the initial FSM state to 'init'
+ d_fsm_state = fsm_enc_conv_init;
+
+// debugging from here down
+#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.";
+#endif
+}
+
+void
+encoder_convolutional_base::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_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';
+#endif
+
+// 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 states
+ d_states = 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 part of the trellis which requires input bits
+// from external sources; loop up to the frame size (before
+// termination bits, if any), counting down the number of 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;
+// lopp 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";
+ std::cout << "d_in_bit_shift = " << d_in_bit_shift << '\n';
+ std::cout << "d_out_bit_shift = " << d_out_bit_shift << '\n';
+ std::cout << "d_in_buf_ndx = " << d_in_buf_ndx << '\n';
+ std::cout << "d_out_buf_ndx = " << d_out_buf_ndx << '\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';
+#endif
+
+#if DO_TIME_THOUGHPUT
+ u_long d_t = end_timer (&t_tp);
+
+#if 1
+ std::cout << "Completed " << d_in_buf_ndx <<
+ " bits in " << d_t << " usec => " <<
+ 1e6*(((double) d_in_buf_ndx)/((double) d_t)) <<
+ " b/s\n";
+#else
+ std::cout << "Completed " << (d_in_buf_ndx * g_num_bits_per_byte) <<
+ " bits in " << d_t << " usec => " <<
+ 1e6*(((double)(d_in_buf_ndx * g_num_bits_per_byte))/((double) d_t)) <<
+ " b/s\n";
+#endif
+#endif
+}
+
+void
+encoder_convolutional_base::update_memory_new_input
+(const char** in_buf)
+{
+// get the new inputs, one bit per stream, and update the state to
+// reflect these inputs
+
+// loop over all inputs, push the current state bit into d_states
+ memory_ptr_t t_states_ptr = &(d_states[0]);
+ for (size_t p = 0; p < d_n_code_inputs; p++) {
+ memory_t t_state = (*t_states_ptr) & d_max_mem_mask;
+
+#if DO_PRINT_DEBUG
+ char t_next_bit = get_next_bit (in_buf, p);
+ t_state |= t_next_bit;
+#else
+ t_state |= get_next_bit (in_buf, p);
+#endif
+
+#if DO_PRINT_DEBUG
+ std::cout << "I[" << p << "][" << d_in_buf_ndx << "] = ";
+ cout_binary (in_buf[p][d_in_buf_ndx], 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';
+#endif
+
+ (*t_states_ptr++) = t_state;
+ }
+}
+
+void
+encoder_convolutional_base::encode_loop
+(const char** in_buf,
+ char** out_buf,
+ size_t* which_counter,
+ size_t how_many)
+{
+ while (((*which_counter) > 0) & (d_n_enc_bits < how_many)) {
+// get a new input bit per stream, and update the memory
+ update_memory_new_input (in_buf);
+
+// now encode those inputs using the code generators,
+// and output a single bit per output stream
+
+#if DO_PRINT_DEBUG
+ size_t t_vec_ctr = 0;
+#endif
+
+ memory_ptr_t t_code_generators = &(d_code_generators[0]);
+// loop over all outputs
+ for (size_t q = 0; q < d_n_code_outputs; q++) {
+ memory_t t_out_result = 0;
+ memory_ptr_t t_states_ptr = &(d_states[0]);
+
+// loop over all inputs, xor'ing the result each time
+ for (size_t p = 0; p < d_n_code_inputs; p++) {
+
+#if DO_PRINT_DEBUG
+ std::cout << "b_i = " <<
+ n2bs (t_out_result, d_max_memory+2) << ", st[" << p << "] = " <<
+ n2bs (*t_states_ptr, d_max_memory+2) << ", cg[" << t_vec_ctr++ <<
+ "] = " << n2bs (*t_code_generators, d_max_memory+2) <<
+ ", st[] & cg[] = " <<
+ n2bs ((*t_states_ptr) & (*t_code_generators), d_max_memory+2);
+#endif
+
+ t_out_result ^= ((*t_states_ptr++) & (*t_code_generators++));
+
+#if DO_PRINT_DEBUG
+ std::cout << ", b_o = " << n2bs (t_out_result, d_max_memory+2) << '\n';
+#endif
+ }
+#if DO_PRINT_DEBUG
+ std::cout << "b_r = " << n2bs (t_out_result, d_max_memory+2);
+#endif
+// 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);
+
+// output this particular bit on this output stream
+ output_bit (t_out_bit, out_buf, q);
+
+// increment the input and output counters, if necessary, between output bits
+ increment_io_indices (true);
+ }
+
+// do post-encoding memory mods (e.g. feedback), if any
+ 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
+ d_n_enc_bits++;
+
+// decrement the number of input and output bits left
+ d_n_input_bits_left--;
+ d_n_output_bits_left--;
+ }
+}
+
+char
+encoder_convolutional_base::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);
+}
Index: encoder_convolutional_base.h
===================================================================
RCS file: encoder_convolutional_base.h
diff -N encoder_convolutional_base.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ encoder_convolutional_base.h 4 Jul 2006 01:53:35 -0000 1.1
@@ -0,0 +1,115 @@
+/* -*- c++ -*- */
+/*
+ * Copyright @ 2006 Michael Dickens
+ *
+ * This library 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.
+ *
+ * This library 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 this library; 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_BASE_H
+#define INCLUDED_ENCODER_CONVOLUTIONAL_BASE_H
+
+#include <vector>
+#include "encoder.h"
+
+/*
+ * Encode the incoming streams using a convolutional encoder; This is
+ * a virtual base 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.
+ */
+
+class encoder_convolutional_base : public encoder
+{
+public:
+/*
+ * 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 in octal form. E.g. "04" in binary is "100",
+ * which would be "D^2" for code generation. "06" == 110b == "D^2 + D"
+ * ==> The vector is listed in order for each input 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, I1->O2, I2->O1, I2->O2]
+ * with each element being the octal 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.
+ */
+
+ encoder_convolutional_base (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);
+
+ virtual ~encoder_convolutional_base () {};
+
+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
+ };
+
+ 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__input (const char** in_buf,
+ size_t code_input_n) = 0;
+ virtual char get_next_bit__term (size_t code_input_n);
+ virtual void increment_io_indices (bool while_encoding) = 0;
+ virtual void update_memory_new_input (const char** in_buf);
+ virtual void update_memory_post_encode () = 0;
+
+ fsm_enc_conv_t d_fsm_state;
+ bool d_do_streaming, d_do_termination;
+ std::vector<memory_t> d_code_generators;
+ std::vector<memory_t> d_states, d_init_states, d_term_states;
+};
+
+#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_BASE_H */
Index: encoder_convolutional.cc
===================================================================
RCS file: encoder_convolutional.cc
diff -N encoder_convolutional.cc
--- encoder_convolutional.cc 3 Jul 2006 02:14:12 -0000 1.1
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,640 +0,0 @@
-/* -*- c++ -*- */
-/*
- * Copyright @ 2006 Michael Dickens
- *
- * This library 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.
- *
- * This library 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 this library; 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;
-static const int g_num_bits_per_byte = 8;
-
-// sum the number of set bits, mod 2, for the output bit
-char sum_bits_mod2 (memory_t in_mem, size_t max_memory)
-{
-// there are faster ways to do this, but this works for now; could
-// certainly do a single inline asm, which most processors provide to
-// deal with summing the bits in an integer
-
- char t_out_bit = (char)(in_mem & 1);
- for (size_t r = max_memory; r > 0; r--) {
- in_mem >>= 1;
- t_out_bit ^= ((char)(in_mem & 1));
- }
- return (t_out_bit);
-}
-
-encoder_convolutional::encoder_convolutional
-(int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- std::vector<int> &code_generators,
- int start_memory_state,
- int end_memory_state,
- bool do_termination,
- bool use_muxed_inputs,
- bool do_muxed_outputs,
- bool use_packed_input,
- bool do_packed_outputs)
-{
-// 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;
- d_use_muxed_inputs = use_muxed_inputs;
- d_do_muxed_outputs = do_muxed_outputs;
- d_use_packed_input = use_packed_input;
- d_do_packed_outputs = do_packed_outputs;
-
-// allocate the vectors for doing the encoding. use 32-bit int's
-// actual bits to represent memory and the code, as it makes the
-// operations quite simple the state vectors.
-// states are per each input,
-// code generates are for each I/O combination
-
- d_states.assign (d_n_code_inputs, 0);
- d_init_states.assign (d_n_code_inputs, 0);
- d_term_states.assign (d_n_code_inputs, 0);
- d_code_generators.assign (d_n_code_inputs * d_n_code_outputs, 0);
-
-// FIXME: STILL NEED TO COPY OVER START AND END MEMORY STATES;
-
-// 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
-// t_code_ndx is a counter over all input code_generator elements
- size_t t_max_mem = 0, t_code_ndx = d_code_generators.size() - 1;
-// loop over all input streams first, output streams second
- for (int n = d_n_code_outputs - 1; n >= 0; n--) {
- size_t t_all_inputs_zero = 0;
- for (int m = d_n_code_inputs - 1; m >= 0; m--) {
- size_t t_in_code = code_generators[t_code_ndx];
- t_all_inputs_zero |= t_in_code;
- size_t t_code_mem = 0;
-// find the memory requirement for this code generator
- 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;
-// store in d_code_generators in output-first ordering
- d_code_generators[(m*d_n_code_outputs) + n] =
- code_generators[t_code_ndx--];
- }
- 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 constraint 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;
-
-// set the initial FSM state to 'init'
- d_fsm_state = fsm_enc_conv_init;
-
-// debugging from here down
-#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.";
-#endif
-}
-
-size_t
-encoder_convolutional::compute_n_output_bits
-(size_t n_input_bits)
-{
- 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::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);
-}
-
-size_t
-encoder_convolutional::encode (const char** in_buf,
- char** out_buf,
- size_t n_bits_to_output)
-{
-// set the class-internal number of input and
-// output bits left to encode
- size_t saved_n_input_bits;
- saved_n_input_bits = d_n_input_bits_left =
- compute_n_input_bits (n_bits_to_output);
- d_n_output_bits_left = n_bits_to_output;
-
-// call the private encode function
- encode_private (in_buf, out_buf);
-
-#ifdef DO_PRINT_DEBUG
- std::cout << "n_input_bits_used = " <<
- (saved_n_input_bits - d_n_input_bits_left) << '\n';
- std::cout << "n_output_bits_used = " <<
- (n_bits_to_output - d_n_output_bits_left) << '\n';
-
- assert (d_out_buf_ndx == n_bits_to_output);
-#endif
-
-// return the actual number of input bits used
- return (saved_n_input_bits - d_n_input_bits_left);
-}
-
-/*
- * encode a certain number of input bits
- *
- * the 'in_buf' and 'out_buf' must have enough memory to handle the
- * number of input and output bits; no error checking is done!
- *
- * n_bits_to_input: is the number of input bits per input stream to encode
- *
- * returns the number of actual bits written to the output stream(s)
- */
-
-size_t
-encoder_convolutional::encode (const char** in_buf,
- size_t n_bits_to_input,
- char** out_buf)
-{
-// set the class-internal number of input and
-// output bits left to encode
- size_t saved_n_output_bits;
- saved_n_output_bits = d_n_output_bits_left =
- compute_n_output_bits (n_bits_to_input);
- d_n_input_bits_left = n_bits_to_input;
-
-// call the private encode function
- encode_private (in_buf, out_buf);
-
-#ifdef DO_PRINT_DEBUG
- std::cout << "n_input_bits_used = " <<
- (n_bits_to_input - d_n_input_bits_left) << '\n';
- std::cout << "n_output_bits_used = " <<
- (saved_n_output_bits - d_n_output_bits_left) << '\n';
-
- assert (d_in_buf_ndx == n_bits_to_input);
-#endif
-
-// return the actual number of input bits used
- return (saved_n_output_bits - d_n_output_bits_left);
-}
-
-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_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';
-#endif
-
-// 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 states
- d_states = 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 'up' state
- d_fsm_state = fsm_enc_conv_doing_up;
- break;
-
- case fsm_enc_conv_doing_up:
-// starting the trellis;
-// loop up to the max memory, counting down the number of input bits left
- encode_loop (in_buf, out_buf, &d_n_input_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_doing_middle;
- break;
-
- case fsm_enc_conv_doing_middle:
-// middle of the trellis;
-// loop up to the frame size (before termination bits, if any),
-// counting down the number of 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;
-// better get here only when do_termination is true, but check just in case;
-// lopp 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";
- std::cout << "d_in_bit_shift = " << d_in_bit_shift << '\n';
- std::cout << "d_out_bit_shift = " << d_out_bit_shift << '\n';
- std::cout << "d_in_buf_ndx = " << d_in_buf_ndx << '\n';
- std::cout << "d_out_buf_ndx = " << d_out_buf_ndx << '\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';
-#endif
-
-#if DO_TIME_THOUGHPUT
- u_long d_t = end_timer (&t_tp);
-
-#if 1
- std::cout << "Completed " << d_in_buf_ndx <<
- " bits in " << d_t << " usec => " <<
- 1e6*(((double) d_in_buf_ndx)/((double) d_t)) <<
- " b/s\n";
-#else
- std::cout << "Completed " << (d_in_buf_ndx * g_num_bits_per_byte) <<
- " bits in " << d_t << " usec => " <<
- 1e6*(((double)(d_in_buf_ndx * g_num_bits_per_byte))/((double) d_t)) <<
- " b/s\n";
-#endif
-#endif
-}
-
-void
-encoder_convolutional::encode_loop
-(const char** in_buf, char** out_buf, size_t* which_counter, size_t how_many)
-{
- while (((*which_counter) > 0) & (d_n_enc_bits < how_many)) {
-// get the new inputs, one bit per stream, and update the state to
-// reflect these inputs
-
-// loop over all inputs, push the current state bit into d_states
- memory_ptr_t t_states_ptr = &(d_states[0]);
- for (size_t p = 0; p < d_n_code_inputs; p++) {
- memory_t t_state = ((*t_states_ptr) << 1) & d_max_mem_mask;
-
-#if DO_PRINT_DEBUG
- char t_new_input_bit = get_new_input_bit (in_buf, p);
- t_state |= t_new_input_bit;
-#else
- t_state |= get_new_input_bit (in_buf, p);
-#endif
-
-#if DO_PRINT_DEBUG
- std::cout << "I[" << p << "][" << d_in_buf_ndx << "] = ";
- cout_binary (in_buf[p][d_in_buf_ndx], 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_new_input_bit <<
- ", st_o[" << p << "] = ";
- cout_binary (t_state, d_max_memory+2);
- std::cout << '\n';
-#endif
-
- (*t_states_ptr++) = t_state;
- }
-
-// now encode those inputs using the code generators,
-// and output a single bit per output stream
-
-#if DO_PRINT_DEBUG
- size_t t_vec_ctr = 0;
-#endif
-
- memory_ptr_t t_code_generators = &(d_code_generators[0]);
-// loop over all outputs
- for (size_t q = 0; q < d_n_code_outputs; q++) {
- memory_t t_out_result = 0;
- t_states_ptr = &(d_states[0]);
-
-// loop over all inputs, xor'ing the result each time
- for (size_t p = 0; p < d_n_code_inputs; p++) {
-
-#if DO_PRINT_DEBUG
- std::cout << "b_i = " <<
- n2bs (t_out_result, d_max_memory+2) << ", st[" << p << "] = " <<
- n2bs (*t_states_ptr, d_max_memory+2) << ", cg[" << t_vec_ctr++ <<
- "] = " << n2bs (*t_code_generators, d_max_memory+2) <<
- ", st[] & cg[] = " <<
- n2bs ((*t_states_ptr) & (*t_code_generators), d_max_memory+2);
-#endif
-
- t_out_result ^= ((*t_states_ptr++) & (*t_code_generators++));
-
-#if DO_PRINT_DEBUG
- std::cout << ", b_o = " << n2bs (t_out_result, d_max_memory+2) << '\n';
-#endif
- }
-#if DO_PRINT_DEBUG
- std::cout << "b_r = " << n2bs (t_out_result, d_max_memory+2);
-#endif
-// 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);
-
-// output this particular bit on this output stream
- output_bit (t_out_bit, out_buf, q);
-
-// increment the input and output counters, if necessary, between output bits
- increment_counters (true);
- }
-
-// increment the input and output counters, if necessary, between input bits
- increment_counters (false);
-
-// increment the number of encoded bits for the current block
- d_n_enc_bits++;
-
-// decrement the number of input and output bits left
- d_n_input_bits_left--;
- d_n_output_bits_left--;
- }
-}
-
-void
-encoder_convolutional::increment_counters (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++;
-// increment the input buffer index only for this version
- d_in_buf_ndx++;
- }
-#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::output_bit (char t_out_bit,
- char** out_buf,
- size_t t_output_stream)
-{
-// store the result for this particular output stream
-
-#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
-
-// one bit per output item
- out_buf[t_output_stream][d_out_buf_ndx] = t_out_bit;
-
-#if 0
-// packed bits in each output item
- out_buf[t_output_stream][d_out_buf_ndx] |=
- (t_out_bit << d_out_bit_shift);
-#endif
-
-#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
-}
-
-char
-encoder_convolutional::get_new_input_bit__up (const char** in_buf,
- size_t code_input_n)
-{
- return (get_new_input_bit__middle (in_buf, code_input_n));
-}
-
-char
-encoder_convolutional::get_new_input_bit__middle (const char** in_buf,
- size_t code_input_n)
-{
- return (in_buf[code_input_n][d_in_buf_ndx] & 1);
-
-#if 0
-// if 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
- return ((in_buf[code_input_n][d_in_buf_ndx] >> d_in_bit_shift) & 1);
-#endif
-}
-
-char
-encoder_convolutional::get_new_input_bit__term (size_t code_input_n)
-{
- return (d_term_states[code_input_n] & 1);
-
-#if 0
- return ((d_term_states[code_input_n] >> d_in_bit_shift) & 1);
-#endif
-}
-
-char
-encoder_convolutional::get_new_input_bit (const char** in_buf,
- size_t code_input_n)
-{
- char ret_val = 0;
- switch (d_fsm_state) {
- case fsm_enc_conv_doing_up:
- ret_val = get_new_input_bit__up (in_buf, code_input_n);
- break;
- case fsm_enc_conv_doing_middle:
- ret_val = get_new_input_bit__middle (in_buf, code_input_n);
- break;
- case fsm_enc_conv_doing_term:
- ret_val = get_new_input_bit__term (code_input_n);
- break;
- default:
- break;
- }
- return (ret_val);
-}
Index: encoder_convolutional.h
===================================================================
RCS file: encoder_convolutional.h
diff -N encoder_convolutional.h
--- encoder_convolutional.h 3 Jul 2006 02:14:12 -0000 1.1
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,139 +0,0 @@
-/* -*- c++ -*- */
-/*
- * Copyright @ 2006 Michael Dickens
- *
- * This library 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.
- *
- * This library 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 this library; 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"
-
-/*!
- * \brief Encode the incoming streams using a convolutional encoder
- *
- * input: streams of char, one stream per input as defined by the
- * instantiated code, using only the right-most justified bit as
- * the single input bit per input item.
- *
- * output: streams of char, one stream per output as defined by the
- * instantiated code, using only the right-most justified bit as
- * the single output bit per output item.
- */
-
-class encoder_convolutional : public encoder
-{
-public:
-/*
- * 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 in octal form. E.g. "04" in binary is "100",
- * which would be "D^2" for code generation. "06" == 110b == "D^2 + D"
- * ==> The vector is listed in order for each input 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, I1->O2, I2->O1, I2->O2]
- * with each element being the octal 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.
- */
-
- encoder_convolutional (int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- std::vector<int> &code_generators,
- int start_memory_state = 0,
- int end_memory_state = 0,
- bool do_termination = true,
- bool use_muxed_inputs = false,
- bool do_muxed_outputs = false,
- bool use_packed_input = false,
- bool do_packed_outputs = false);
-
- virtual ~encoder_convolutional () {};
-
- virtual size_t compute_n_input_bits (size_t n_output_bits);
- virtual size_t compute_n_output_bits (size_t n_input_bits);
- virtual size_t encode (const char** in_buf,
- char** out_buf,
- size_t n_bits_to_output);
- virtual size_t encode (const char** in_buf,
- size_t n_bits_to_input,
- char** out_buf);
-
-private:
-/*
- * 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_up: encoding at the start of a block
- *
- * fsm_enc_conv_doing_middle: 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_up,
- fsm_enc_conv_doing_middle, fsm_enc_conv_doing_term
- };
-
- 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_new_input_bit (const char** in_buf, size_t code_input_n);
- virtual char get_new_input_bit__up (const char** in_buf,
- size_t code_input_n);
- virtual char get_new_input_bit__middle (const char** in_buf,
- size_t code_input_n);
- virtual char get_new_input_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_counters (bool while_encoding);
-
- fsm_enc_conv_t d_fsm_state;
- bool d_use_muxed_inputs, d_do_muxed_outputs;
- bool d_use_packed_input, d_do_packed_outputs;
- bool d_do_streaming, d_do_termination;
- std::vector<memory_t> d_code_generators;
- std::vector<memory_t> d_states, d_init_states, d_term_states;
-};
-
-#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_H */