[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Commit-gnuradio] r3362 - in gnuradio/branches/developers/michaelld/wip/
|
From: |
michaelld |
|
Subject: |
[Commit-gnuradio] r3362 - in gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src: lib lib/libecc lib/libecc/tests python |
|
Date: |
Mon, 21 Aug 2006 10:48:00 -0600 (MDT) |
Author: michaelld
Date: 2006-08-21 10:48:00 -0600 (Mon, 21 Aug 2006)
New Revision: 3362
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy_alt.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/doubly_linked_list.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_ecc.py
Removed:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/qa_ecc.py
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_coding_1.py
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_coding_2.py
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_encoder_convolutional_1.py
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_encoder_convolutional_2.py
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/Makefile.am
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.i
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.i
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/Makefile.am
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_io.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_types.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/Makefile.am
Log:
WIP: First cut implementing the Lazy Viterbi decoder.
Removed non-standard python QA stuff; replaced with the generic test
for library loading.
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/Makefile.am
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/Makefile.am
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/Makefile.am
2006-08-21 16:48:00 UTC (rev 3362)
@@ -35,21 +35,21 @@
SWIGCPPPYTHONARGS = -fvirtual -python -modern $(PYTHON_CPPFLAGS) \
$(STD_DEFINES_AND_INCLUDES)
-ALL_IFILES = $(LOCAL_IFILES) $(NON_LOCAL_IFILES)
-
NON_LOCAL_IFILES = $(GNURADIO_I)
-LOCAL_IFILES = \
- ecc_syms_to_metrics.i \
- ecc_metrics_decode_viterbi_full_block.i \
- ecc_streams_encode_convolutional.i \
- ecc_streams_encode_turbo.i \
- ecc.i
+LOCAL_IFILES = \
+ $(top_srcdir)/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.i \
+
$(top_srcdir)/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.i
\
+
$(top_srcdir)/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.i
\
+
$(top_srcdir)/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.i
\
+ $(top_srcdir)/gr-error-correcting-codes/src/lib/ecc.i
# These files are built by SWIG. The first is the C++ glue.
# The second is the python wrapper that loads the _howto shared library
# and knows how to call our extensions.
+ALL_IFILES = $(LOCAL_IFILES) $(NON_LOCAL_IFILES)
+
BUILT_SOURCES = \
ecc.cc \
ecc.py
@@ -89,8 +89,8 @@
# These swig headers get installed in ${prefix}/include/gnuradio/swig
swiginclude_HEADERS = $(LOCAL_IFILES)
-ecc.cc ecc.py: ecc.i $(ALL_IFILES)
- $(SWIG) $(SWIGCPPPYTHONARGS) -module ecc -o ecc.cc $<
+ecc.cc ecc.py: $(top_srcdir)/gr-error-correcting-codes/src/lib/ecc.i
$(ALL_IFILES)
+ $(SWIG) $(SWIGCPPPYTHONARGS) -module ecc -o ecc.cc
$(top_srcdir)/gr-error-correcting-codes/src/lib/ecc.i
MOSTLYCLEANFILES = $(BUILT_SOURCES) *.pyc *.loT *~
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -32,6 +32,9 @@
ecc_metrics_decode_viterbi_full_block_sptr
ecc_make_metrics_decode_viterbi_full_block
(int sample_precision,
+<<<<<<< .working
+ const ecc_streams_encode_convolutional_sptr& encoder)
+=======
int frame_size_bits,
int n_code_inputs,
int n_code_outputs,
@@ -39,19 +42,16 @@
bool do_termination,
int start_memory_state,
int end_memory_state)
+>>>>>>> .merge-right.r3343
{
return ecc_metrics_decode_viterbi_full_block_sptr
(new ecc_metrics_decode_viterbi_full_block
(sample_precision,
- frame_size_bits,
- n_code_inputs,
- n_code_outputs,
- code_generator,
- do_termination,
- start_memory_state,
- end_memory_state));
+ encoder));
}
+<<<<<<< .working
+=======
ecc_metrics_decode_viterbi_full_block_feedback_sptr
ecc_make_metrics_decode_viterbi_full_block_feedback
(int sample_precision,
@@ -127,25 +127,33 @@
setup_io_signatures (sample_precision, n_code_inputs, n_code_outputs);
}
+>>>>>>> .merge-right.r3343
ecc_metrics_decode_viterbi_full_block::~ecc_metrics_decode_viterbi_full_block
()
{
delete d_decoder;
d_decoder = 0;
- delete d_encoder;
- d_encoder = 0;
delete d_in_buf;
d_in_buf = 0;
delete d_out_buf;
d_out_buf = 0;
}
-void
-ecc_metrics_decode_viterbi_full_block::setup_io_signatures
+ecc_metrics_decode_viterbi_full_block::ecc_metrics_decode_viterbi_full_block
(int sample_precision,
- int n_code_inputs,
- int n_code_outputs)
+ const ecc_streams_encode_convolutional_sptr& encoder)
+ : gr_block ("metrics_decode_viterbi_full_block",
+ gr_make_io_signature (0, 0, 0),
+ gr_make_io_signature (0, 0, 0))
{
+ // error checking is done in the encoder and decoder classes
+ // so just use the parameters as given; will be correct!
+
+ // get the trellis
+
+ code_convolutional_trellis* l_trellis =
+ (code_convolutional_trellis*) encoder->encoder()->trellis ();
+
// create the decoder
//
// the input model: individual input streams; two per metric type
@@ -156,21 +164,18 @@
// individual output streams per decoded code input stream;
// each item is a 'char' type with 1 bit aligned on the LSB.
+ size_t n_code_inputs = l_trellis->n_code_inputs ();
+ size_t n_code_outputs = l_trellis->n_code_outputs ();
+
d_decoder = new decoder_viterbi_full_block (sample_precision,
- d_encoder);
+ l_trellis);
d_out_buf = new code_output_ic1l (n_code_inputs);
- // error checking is done in the encoder and decoder classes
- // so just use the parameters as given; will be correct!
-
- d_n_code_inputs = n_code_inputs;
- d_n_code_outputs = n_code_outputs;
-
// output signature is always the same:
// sizeof (char) with 1 bit per char as the LSB
- set_output_signature (gr_make_io_signature (d_n_code_inputs,
- d_n_code_inputs,
+ set_output_signature (gr_make_io_signature (n_code_inputs,
+ n_code_inputs,
sizeof (char)));
// determine the input signature element size
@@ -194,14 +199,14 @@
d_in_buf = new code_input_il (n_code_outputs);
}
- set_input_signature (gr_make_io_signature (2*d_n_code_outputs,
- 2*d_n_code_outputs,
+ set_input_signature (gr_make_io_signature (2*n_code_outputs,
+ 2*n_code_outputs,
l_input_item_size_bytes));
}
void ecc_metrics_decode_viterbi_full_block::forecast
(int noutput_items,
- gr_vector_int &ninput_items_required)
+ gr_vector_int& ninput_items_required)
{
int ninput_items = d_decoder->compute_n_input_items (noutput_items);
size_t ninputs = ninput_items_required.size();
@@ -212,14 +217,14 @@
int
ecc_metrics_decode_viterbi_full_block::general_work
(int noutput_items,
- gr_vector_int &ninput_items,
- gr_vector_const_void_star &input_items,
- gr_vector_void_star &output_items)
+ gr_vector_int& ninput_items,
+ gr_vector_const_void_star& input_items,
+ gr_vector_void_star& output_items)
{
// compute the actual number of output items (1 bit char's) created.
size_t t_n_input_items = d_decoder->compute_n_input_items (noutput_items);
-#if 1
+#if 0
size_t t_n_output_items = d_decoder->compute_n_output_bits (t_n_input_items);
assert (t_n_output_items == ((size_t)noutput_items));
#endif
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -23,19 +23,20 @@
#ifndef INCLUDED_ECC_METRICS_DECODE_VITERBI_FULL_BLOCK_H
#define INCLUDED_ECC_METRICS_DECODE_VITERBI_FULL_BLOCK_H
-#include <gr_block.h>
+#include <ecc_streams_encode_convolutional.h>
#include <libecc/decoder_viterbi_full_block.h>
-#include <libecc/encoder_convolutional.h>
class ecc_metrics_decode_viterbi_full_block;
typedef boost::shared_ptr<ecc_metrics_decode_viterbi_full_block>
-ecc_metrics_decode_viterbi_full_block_sptr,
-ecc_metrics_decode_viterbi_full_block_feedback_sptr;
+ecc_metrics_decode_viterbi_full_block_sptr;
ecc_metrics_decode_viterbi_full_block_sptr
ecc_make_metrics_decode_viterbi_full_block
(int sample_precision,
+<<<<<<< .working
+ const ecc_streams_encode_convolutional_sptr& encoder);
+=======
int frame_size_bits,
int n_code_inputs,
int n_code_outputs,
@@ -43,7 +44,10 @@
bool do_termination = true,
int start_memory_state = 0,
int end_memory_state = 0);
+>>>>>>> .merge-right.r3343
+<<<<<<< .working
+=======
ecc_metrics_decode_viterbi_full_block_feedback_sptr
ecc_make_metrics_decode_viterbi_full_block_feedback
(int sample_precision,
@@ -56,6 +60,7 @@
int start_memory_state = 0,
int end_memory_state = 0);
+>>>>>>> .merge-right.r3343
/*!
* \brief Decode the incoming streams using a Viterbi-style decoder,
* full trellis block decoding.
@@ -71,84 +76,25 @@
friend ecc_metrics_decode_viterbi_full_block_sptr
ecc_make_metrics_decode_viterbi_full_block
(int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int>& code_generator,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
+ const ecc_streams_encode_convolutional_sptr& encoder);
- friend ecc_metrics_decode_viterbi_full_block_feedback_sptr
- ecc_make_metrics_decode_viterbi_full_block_feedback
- (int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int>& code_generator,
- const std::vector<int>& code_feedback,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
/*
- * frame_size_bits: if == 0, then do streaming decoding (infinite
- * trellis); otherwise this is the block size to decode before
- * terminating the trellis.
+ * sample_precision: if == 0, then metrics are float precision and
+ * always in [0,1]; if in [1,32] (== M), then use M-ary integer
+ * precision and each metric will always be in [0,(2^M)-1].
*
- * 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 is valid only if frame_size_bits != 0, and defines
- * whether or not to to trellis termination.
- *
- * do_mux_input: is true, then the one input stream will be
- * interpreted as the multiplexing all of the input bits. For
- * example for a 3 input decoder, the input stream would be
- * [I1[k], I2[k], I3[k], I1[k+1], I2[k+1], ...], where "k" is the
- * input sample time, and "I1" through "I3" are the 3 input
- * streams.
- *
- * n_code_inputs: the number of decoder-input (encoder-output)
- * streams, no matter if separate or mux'ed
- *
- * n_code_outputs: the number of decoder-output (encoder-input) streams
+ * encoder: the encoder which was used for the original data
*/
ecc_metrics_decode_viterbi_full_block
(int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int>& code_generator,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
+ const ecc_streams_encode_convolutional_sptr& encoder);
- ecc_metrics_decode_viterbi_full_block
- (int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int>& code_generator,
- const std::vector<int>& code_feedback,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
-
void setup_io_signatures (int sample_precision,
int n_code_inputs,
int n_code_outputs);
- int d_n_code_inputs, d_n_code_outputs;
decoder_viterbi_full_block* d_decoder;
- encoder_convolutional* d_encoder;
code_input_ptr d_in_buf;
code_output_ptr d_out_buf;
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.i
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.i
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_metrics_decode_viterbi_full_block.i
2006-08-21 16:48:00 UTC (rev 3362)
@@ -22,56 +22,14 @@
GR_SWIG_BLOCK_MAGIC(ecc,metrics_decode_viterbi_full_block);
-// corrected "class NAME" statement, which uses slightly different NAMEs
-
-typedef boost::shared_ptr<ecc_metrics_decode_viterbi_full_block>
-ecc_metrics_decode_viterbi_full_block_feedback_sptr;
-
-LOCAL_GR_SWIG_BLOCK_MAGIC(ecc,metrics_decode_viterbi_full_block_feedback);
-
ecc_metrics_decode_viterbi_full_block_sptr
ecc_make_metrics_decode_viterbi_full_block
(int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int> &code_generator,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
+ const ecc_streams_encode_convolutional_sptr& encoder);
-ecc_metrics_decode_viterbi_full_block_feedback_sptr
-ecc_make_metrics_decode_viterbi_full_block_feedback
-(int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int> &code_generator,
- const std::vector<int> &code_feedback,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
-
class ecc_metrics_decode_viterbi_full_block : public gr_block
{
ecc_metrics_decode_viterbi_full_block
(int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int> &code_generator,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
-
- ecc_metrics_decode_viterbi_full_block
- (int sample_precision,
- int frame_size_bits,
- int n_code_inputs,
- int n_code_outputs,
- const std::vector<int> &code_generator,
- const std::vector<int> &code_feedback,
- bool do_termination,
- int start_memory_state,
- int end_memory_state);
+ const ecc_streams_encode_convolutional_sptr& encoder);
};
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -35,7 +35,7 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generator,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state)
{
@@ -56,7 +56,7 @@
int n_code_outputs,
const std::vector<int> &code_generator,
const std::vector<int> &code_feedback,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state)
{
@@ -76,21 +76,33 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generators,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state)
: gr_block ("streams_encode_convolutional",
gr_make_io_signature (0, 0, 0),
gr_make_io_signature (0, 0, 0))
{
- // error checking is done by the encoder class itself;
- // just pass items on here.
+ // convert the "do_termination" argument into a "bool" type
+ bool l_do_term = false;
+
+ if (do_termination != 0) {
+ l_do_term = true;
+ if (do_termination != 1) {
+ std::cout << "ecc_streams_encode_convolutional: Warning: "
+ "do_termination is not 0 or 1; using 'true'.\n";
+ }
+ }
+
+ // the rest of the error checking is done by the encoder class
+ // itself; just pass items on here.
+
d_encoder = new encoder_convolutional (frame_size_bits,
n_code_inputs,
n_code_outputs,
code_generators,
- do_termination,
+ l_do_term,
start_memory_state,
end_memory_state);
@@ -103,22 +115,34 @@
int n_code_outputs,
const std::vector<int> &code_generators,
const std::vector<int> &code_feedback,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state)
: gr_block ("streams_encode_convolutional_feedback",
gr_make_io_signature (0, 0, 0),
gr_make_io_signature (0, 0, 0))
{
- // error checking is done by the encoder class itself;
- // just pass items on here.
+ // convert the "do_termination" argument into a "bool" type
+ bool l_do_term = false;
+
+ if (do_termination != 0) {
+ l_do_term = true;
+ if (do_termination != 1) {
+ std::cout << "ecc_streams_encode_convolutional_feedback: Warning: "
+ "do_termination is not 0 or 1; using 'true'.\n";
+ }
+ }
+
+ // the rest of the error checking is done by the encoder class
+ // itself; just pass items on here.
+
d_encoder = new encoder_convolutional (frame_size_bits,
n_code_inputs,
n_code_outputs,
code_generators,
code_feedback,
- do_termination,
+ l_do_term,
start_memory_state,
end_memory_state);
@@ -181,7 +205,7 @@
// compute the actual number of output items (1 bit char's) created.
size_t t_n_input_items = d_encoder->compute_n_input_bits (noutput_items);
-#if 1
+#if 0
size_t t_n_output_items = d_encoder->compute_n_output_bits (t_n_input_items);
assert (t_n_output_items == ((size_t)noutput_items));
#endif
@@ -196,8 +220,6 @@
t_n_input_items = d_encoder->encode (d_in_buf, d_out_buf,
(size_t) noutput_items);
- assert (0);
-
// consume the number of used input items on all input streams
consume_each (t_n_input_items);
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -79,7 +79,7 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generator,
- bool do_termination = true,
+ int do_termination = 1,
int start_memory_state = 0,
int end_memory_state = 0);
@@ -90,7 +90,7 @@
int n_code_outputs,
const std::vector<int> &code_generator,
const std::vector<int> &code_feedback,
- bool do_termination = true,
+ int do_termination = 1,
int start_memory_state = 0,
int end_memory_state = 0);
@@ -103,7 +103,7 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generator,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state);
@@ -114,7 +114,7 @@
int n_code_outputs,
const std::vector<int> &code_generator,
const std::vector<int> &code_feedback,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state);
@@ -122,7 +122,7 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generator,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state);
@@ -131,7 +131,7 @@
int n_code_outputs,
const std::vector<int> &code_generator,
const std::vector<int> &code_feedback,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state);
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.i
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.i
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_convolutional.i
2006-08-21 16:48:00 UTC (rev 3362)
@@ -38,7 +38,7 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generator,
- bool do_termination = true,
+ int do_termination = 1,
int start_memory_state = 0,
int end_memory_state = 0);
@@ -49,7 +49,7 @@
int n_code_outputs,
const std::vector<int> &code_generator,
const std::vector<int> &code_feedback,
- bool do_termination = true,
+ int do_termination = 1,
int start_memory_state = 0,
int end_memory_state = 0);
@@ -61,7 +61,7 @@
int n_code_inputs,
int n_code_outputs,
const std::vector<int> &code_generator,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state);
@@ -71,7 +71,7 @@
int n_code_outputs,
const std::vector<int> &code_generator,
const std::vector<int> &code_feedback,
- bool do_termination,
+ int do_termination,
int start_memory_state,
int end_memory_state);
};
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -170,7 +170,7 @@
// compute the actual number of output items (1 bit char's) created.
size_t t_n_input_items = d_encoder->compute_n_input_bits (noutput_items);
-#if 1
+#if 0
size_t t_n_output_items = d_encoder->compute_n_output_bits (t_n_input_items);
assert (t_n_output_items == ((size_t)noutput_items));
#endif
@@ -185,8 +185,6 @@
t_n_input_items = d_encoder->encode (d_in_buf, d_out_buf,
(size_t) noutput_items);
- assert (0);
-
// consume the number of used input items on all input streams
consume_each (t_n_input_items);
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_streams_encode_turbo.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -25,12 +25,7 @@
#include <gr_block.h>
#include <ecc_streams_encode_convolutional.h>
-
-#if 0
-#include <libecc/encoder_turbo_ic1_ic1.h>
-#else
#include <libecc/encoder_turbo.h>
-#endif
/*!
* \brief Encode the incoming stream(s) using a turbo encoder
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -76,14 +76,22 @@
{
// setup the dummy functions to do the conversion from the
// python-provided feval classes to that which is needed by the
- // libecc's code_metrics classes.
+ // libecc's code_syms_to_metrics classes.
l_pdf_fcn_0_bit = pdf_fcn_0_bit;
l_pdf_fcn_1_bit = pdf_fcn_1_bit;
// use the static "create" member function to create the actual
- // code_metrics to use.
+ // code_syms_to_metrics to use.
+<<<<<<< .working
+<<<<<<< .working
+ d_code_metrics_table = libecc_code_syms_to_metrics_create_table<float>
+ (&pdf_fcn_0, &pdf_fcn_1, n_samples,
+ min_sample, max_sample,sample_precision);
+=======
+=======
+>>>>>>> .merge-right.r3361
d_code_metrics_table = libecc_code_metrics_create_table<float>
(&pdf_fcn_0,
&pdf_fcn_1,
@@ -91,13 +99,15 @@
min_sample,
max_sample,
sample_precision);
+>>>>>>> .merge-right.r3343
- // get the output item size in bytes from the new code_metrics.
+ // get the output item size in bytes from the new
+ // code_syms_to_metrics.
d_out_item_size_bytes = d_code_metrics_table->out_item_size_bytes ();
- // set the output signature to match that which the code_metrics
- // will generate.
+ // set the output signature to match that which the
+ // code_syms_to_metrics will generate.
set_output_signature (gr_make_io_signature (1, -1, d_out_item_size_bytes));
}
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/ecc_syms_to_metrics.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -26,7 +26,7 @@
#include <gr_block.h>
#include <gr_feval.h>
#include <vector>
-#include <libecc/code_metrics.h>
+#include <libecc/code_syms_to_metrics.h>
class ecc_syms_to_metrics;
typedef boost::shared_ptr<ecc_syms_to_metrics> ecc_syms_to_metrics_sptr;
@@ -106,7 +106,17 @@
int sample_precision);
size_t d_out_item_size_bytes;
+<<<<<<< .working
+<<<<<<< .working
+ code_syms_to_metrics<float>* d_code_metrics_table;
+=======
+=======
+>>>>>>> .merge-right.r3361
code_metrics_table<float>* d_code_metrics_table;
+<<<<<<< .working
+>>>>>>> .merge-right.r3343
+=======
+>>>>>>> .merge-right.r3361
public:
~ecc_syms_to_metrics() {delete d_code_metrics_table;};
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/Makefile.am
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/Makefile.am
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/Makefile.am
2006-08-21 16:48:00 UTC (rev 3362)
@@ -30,22 +30,35 @@
libecc_la_SOURCES = \
code_convolutional_trellis.cc \
- code_metrics.cc code_io.cc \
+ code_syms_to_metrics.cc \
+ code_metrics_to_branches.cc \
+ code_io.cc \
encoder.cc \
encoder_convolutional.cc \
encoder_turbo.cc \
decoder.cc \
decoder_viterbi.cc \
- decoder_viterbi_full_block.cc
+ decoder_viterbi_lazy.cc
+# decoder_viterbi_lazy_alt.cc
+# decoder_viterbi_standard.cc
+
noinst_HEADERS = \
- code_types.h code_metrics.h code_io.h \
+ code_types.h \
+ code_syms_to_metrics.h \
+ code_metrics_to_branches.h \
+ code_io.h \
code_convolutional_trellis.h \
- encoder.h encoder_turbo.h \
+ encoder.h \
encoder_convolutional.h \
- decoder.h decoder_viterbi.h \
- decoder_viterbi_full_block.h
+ encoder_turbo.h \
+ decoder.h \
+ decoder_viterbi.h \
+ decoder_viterbi_lazy.h
+# decoder_viterbi_lazy_alt.h
+# decoder_viterbi_standard.h
+
# link the library against the c++ standard library
libecc_la_LIBADD = \
mld/libmld.la \
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -430,25 +430,19 @@
// create the trellis for this code:
memory_t t_mask = (memory_t)((1 << d_total_n_delays) - 1);
- memory_t t_end_memory_state = (memory_t) end_memory_state;
+ d_end_memory_state = (memory_t) end_memory_state;
- if (t_end_memory_state != (t_end_memory_state & t_mask)) {
+ if (d_end_memory_state != (d_end_memory_state & t_mask)) {
std::cout << "code_convolutional_trellis: Warning: " <<
"provided end memory state out (" << end_memory_state <<
") is out of the state range [0, " <<
(d_n_states-1) << "]; masking off the unused bits.\n";
- end_memory_state &= t_mask;
+ d_end_memory_state &= t_mask;
}
create_trellis ();
-
- if (d_do_termination == true) {
-
- // create the termination lookup table
-
- create_termination_table (end_memory_state);
- }
+ create_termination_table ();
}
void
@@ -752,7 +746,7 @@
void
code_convolutional_trellis::create_termination_table
-(memory_t end_memory_state)
+()
{
// somewhat involved, but basically start with the terminating state
// and work backwards d_total_n_delays, then create a
@@ -763,6 +757,9 @@
// particular state, listed in order from LSB for the first input
// bit to the MSB for the last input bit.
+ if (d_do_termination == false)
+ return;
+
// create a reverse trellis
// it's temporary, just for doing the termination, so just do it locally
@@ -780,7 +777,7 @@
}
std::vector<memory_t> tmp(d_n_memories);
- demux_state (end_memory_state, tmp);
+ demux_state (d_end_memory_state, tmp);
memory_t to_state, outputs;
connection_t t_conn;
@@ -839,7 +836,7 @@
// create the list of "in-use" states for the current t_term_inputs
- std::vector<size_t> t_used_states_ndx[2];
+ std::vector<memory_t> t_used_states_ndx[2];
t_used_states_ndx[0].assign (d_n_states, 0);
t_used_states_ndx[1].assign (d_n_states, 0);
@@ -856,8 +853,8 @@
// setup the first state
size_t t_which_input = 0;
- t_used_states_ndx[t_which_input][0] = (size_t) end_memory_state;
- t_in_use_states[t_which_input][(size_t) end_memory_state] = true;
+ t_used_states_ndx[t_which_input][0] = d_end_memory_state;
+ t_in_use_states[t_which_input][d_end_memory_state] = true;
size_t n_states_used[2];
n_states_used[t_which_input] = 1;
n_states_used[t_which_input^1] = 0;
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -164,21 +164,39 @@
inline const bool do_encode_soai () {return (d_do_encode_soai);};
inline const size_t total_n_delays () {return (d_total_n_delays);};
inline const size_t n_bits_to_term () {return (d_n_bits_to_term);};
+ inline const memory_t end_memory_state () {return (d_end_memory_state);};
virtual char sum_bits_mod2 (memory_t in_mem, size_t max_memory);
- void get_termination_inputs (memory_t term_start_state,
- size_t bit_num,
- std::vector<char>& inputs) {
+ inline void get_termination_inputs (memory_t term_start_state,
+ size_t bit_num,
+ std::vector<char>& inputs) {
// no error checking ... be careful!
for (size_t m = 0; m < d_n_code_inputs; m++) {
inputs[m] = ((d_term_inputs[term_start_state][m]) >> bit_num) & 1;
}
};
+ inline memory_t get_termination_inputs (memory_t term_start_state,
+ size_t bit_num) {
+ // no error checking ... be careful!
+ memory_t t_inputs = 0;
+ for (size_t m = 0; m < d_n_code_inputs; m++) {
+ memory_t t_input = ((d_term_inputs[term_start_state][m]) >> bit_num) & 1;
+ t_inputs |= (t_input << m);
+ }
+ return (t_inputs);
+ };
// encode_lookup: given the starting state and inputs, return the
// resulting state and output bits. Two versions: the first is
// better for decoding, while the second is better for encoding.
+ inline void encode_lookup (memory_t& state,
+ const memory_t inputs,
+ memory_t& out_bits) {
+ connection_t_ptr t_connection = &(d_trellis[state][inputs]);
+ state = t_connection->d_to_state;
+ out_bits = t_connection->d_output_bits;
+ };
void encode_lookup (memory_t& state,
const std::vector<char>& inputs,
memory_t& out_bits);
@@ -196,39 +214,7 @@
memory_t mux_outputs (const std::vector<char>& out_vec);
protected:
-#if 0
/*
- * state_get_from(v,i,k): use to retrieve a given bit-memory state,
- * from the inputs:
- *
- * memory_t v: the value from which to retrieve the given state
- * size_t i: for which input stream (0 to #I-1)
- * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
- */
-
- inline memory_t state_get_from (memory_t v,
- size_t i,
- size_t k)
- {return (((v)>>((i)*(k)))&((1<<(k))-1));};
-
-/*
- * state_add_to(s,v,i,k): use to create a given bit-memory state,
- * from the inputs:
- *
- * memory_t s: the state value to modify
- * memory_t v: value to set the state to for this input
- * size_t i: for which input stream (0 to #I-1)
- * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
- */
-
- inline void state_add_to (memory_t s,
- memory_t v,
- size_t i,
- size_t k)
- {(s)|=(((v)&((1<<(k))-1))<<((i)*(k)));};
-#endif
-
-/*
* 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.
@@ -284,7 +270,7 @@
int end_memory_state);
void create_trellis ();
- void create_termination_table (memory_t end_memory_state);
+ void create_termination_table ();
void encode_single (memory_t in_state,
memory_t inputs,
memory_t& out_state,
@@ -400,6 +386,11 @@
// representation for this code; forward paths only
trellis_t d_trellis;
+
+ // "end_memory_state" is the user-provided ending memory
+ // state, interpreted w/r.t. the actual trellis;
+
+ memory_t d_end_memory_state;
};
#endif /* INCLUDED_CODE_CONVOLUTIONAL_TRELLIS_H */
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_io.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_io.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_io.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -126,7 +126,7 @@
* "id":
* 'i': one stream per code input as defined by the instantiated
* code ("individual", not mux'ed);
- * 'f': streams of double;
+ * 'd': streams of double;
*/
inline code_input_id (size_t n_streams) : code_input (n_streams) {};
virtual ~code_input_id () {};
@@ -197,7 +197,7 @@
public:
/*!
- * class code_input_is : public code_input
+ * class code_input_ic : public code_input
*
* "ic":
* 'i': one stream per code input as defined by the instantiated
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics.cc
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics.h
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.cc
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,145 @@
+/* -*- 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 "code_metrics_to_branches.h"
+#include <iostream>
+#include <assert.h>
+
+code_metrics_to_branches*
+libecc_code_metrics_to_branches_create
+(const code_convolutional_trellis* trellis,
+ int sample_precision)
+{
+ if (trellis == 0) {
+ std::cerr << "libecc_code_metrics_to_branches_create: Error: "
+ "Trellis is NULL.\n";
+ assert (0);
+ }
+
+ if ((sample_precision < 0) | (sample_precision > 32)) {
+ std::cerr << "libecc_code_metrics_to_branches_create: Error: "
+ "sample_precision must be between 0 and 32.\n";
+ assert (0);
+ }
+
+ code_metrics_to_branches* t_code_metrics_to_branches = 0;
+
+ if (sample_precision == 0) {
+ // float for metric and computations
+ t_code_metrics_to_branches = new
+ code_metrics_to_branches_work<float,float>(trellis);
+ } else if (sample_precision <= 8) {
+ // use char for metrics, long for computations
+ t_code_metrics_to_branches = new
+ code_metrics_to_branches_work<unsigned char,unsigned long>(trellis);
+ } else if (sample_precision <= 16) {
+ // use short for metrics, long for computations
+ t_code_metrics_to_branches = new
+ code_metrics_to_branches_work<unsigned short,unsigned long>(trellis);
+ } else {
+ // use long for metrics, long for computations
+ t_code_metrics_to_branches = new
+ code_metrics_to_branches_work<unsigned long,unsigned long>(trellis);
+ }
+
+ return (t_code_metrics_to_branches);
+}
+
+code_metrics_to_branches::code_metrics_to_branches
+(const code_convolutional_trellis* trellis)
+{
+ d_n_code_outputs = ((code_convolutional_trellis*) trellis)->n_code_outputs
();
+}
+
+template<typename metric_t, typename computation_t>
+void
+code_metrics_to_branches_work<metric_t,computation_t>::compute_all_branches
+(void* t_input_metrics,
+ void* t_branches)
+{
+ metric_t_hdl metrics = (metric_t_hdl) t_input_metrics;
+ computation_t_ptr out = (computation_t_ptr) t_branches;
+
+ // compute all possible (summation) combinations of the metrics
+ // using <computation_t>-precision (e.g. "float") computations and
+ // return those in the provided vector.
+
+ // the input metrics must be a [2][d_n_code_outputs] "matrix", with
+ // the [0][] and [1][] entries representing p(0|sym) and p(1|sym),
+ // respectively.
+
+ // the output "table" must be a [1 << d_n_code_outputs] "vector",
+ // where each entry represents the combined (added) metric for that
+ // given set of output bits. e.g. [6] (== 110 in binary) would be
+ // the sum of metrics for p(1|sym#2), p(1|sym#1), and p(0|sym#0)
+
+ // assign the starting minimum metric to 0. This is safe because
+ // metrics are always non-negative.
+
+ computation_t min_metric = 0;
+ for (size_t m = 0; m < (((size_t)1) << d_n_code_outputs); m++) {
+ size_t t_out_ndx = m;
+ computation_t t_metric = 0;
+ for (size_t n = 0; n < d_n_code_outputs; n++, t_out_ndx >>= 1)
+ t_metric += metrics[t_out_ndx&1][n];
+ if (t_metric < min_metric)
+ min_metric = t_metric;
+ out[m] = t_metric;
+ }
+
+ // normalize so that the minimum metric always equals 0
+
+ for (size_t m = 0; m < d_n_code_outputs; m++)
+ out[m] -= min_metric;
+}
+
+#if 0
+// force instantiation all used versions of the templates
+
+template
+void
+code_metrics_to_branches_work<float,float>::compute_all_outputs
+(void* t_metrics,
+ void* t_out);
+
+template
+void
+code_metrics_to_branches_work<unsigned char,unsigned long>::compute_all_outputs
+(void* t_metrics,
+ void* t_out);
+
+template
+void
+code_metrics_to_branches_work<unsigned short,unsigned
long>::compute_all_outputs
+(void* t_metrics,
+ void* t_out);
+
+template
+void
+code_metrics_to_branches_work<unsigned long,unsigned long>::compute_all_outputs
+(void* t_metrics,
+ void* t_out);
+#endif
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.h
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_metrics_to_branches.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,74 @@
+/* -*- 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_CODE_METRICS_TO_BRANCHES_H
+#define INCLUDED_CODE_METRICS_TO_BRANCHES_H
+
+#include "code_convolutional_trellis.h"
+
+class code_metrics_to_branches;
+
+code_metrics_to_branches*
+libecc_code_metrics_to_branches_create
+(const code_convolutional_trellis* trellis,
+ int sample_precision = 10);
+
+class code_metrics_to_branches
+{
+public:
+ // compute all possible output-bit branches of the incoming metrics
+
+ virtual void compute_all_branches (void* t_input_metrics,
+ void* t_branches) = 0;
+
+ virtual ~code_metrics_to_branches () {};
+
+protected:
+ code_metrics_to_branches (const code_convolutional_trellis* trellis);
+
+ size_t d_n_code_outputs;
+};
+
+template<typename metric_t, typename computation_t>
+class code_metrics_to_branches_work : public code_metrics_to_branches
+{
+public:
+ typedef metric_t *metric_t_ptr, **metric_t_hdl;
+ typedef computation_t * computation_t_ptr;
+
+ virtual void compute_all_branches (void* t_input_metrics,
+ void* t_branches);
+
+ virtual ~code_metrics_to_branches_work () {};
+
+protected:
+ inline code_metrics_to_branches_work
+ (const code_convolutional_trellis* trellis) :
+ code_metrics_to_branches (trellis) {};
+
+ friend code_metrics_to_branches*
+ libecc_code_metrics_to_branches_create
+ (const code_convolutional_trellis* trellis,
+ int sample_precision);
+};
+
+#endif /* INCLUDED_CODE_METRICS_TO_BRANCHES_H */
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.cc
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,340 @@
+/* -*- 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 <code_syms_to_metrics.h>
+#include <iostream>
+#include <math.h>
+#include <assert.h>
+
+template<typename pdf_fcn_io_t>
+code_syms_to_metrics<pdf_fcn_io_t>*
+libecc_code_syms_to_metrics_create_table
+(pdf_fcn_io_t (*pdf_fcn_0_bit) (pdf_fcn_io_t),
+ pdf_fcn_io_t (*pdf_fcn_1_bit) (pdf_fcn_io_t),
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample,
+ int sample_precision)
+{
+ if (! pdf_fcn_0_bit) {
+ std::cerr << "libecc_code_syms_to_metrics_create_table: Error: "
+ "pdf_fcn_0_bit must be a non-null pointer to function.\n";
+ assert (0);
+ }
+ if (! pdf_fcn_1_bit) {
+ std::cerr << "libecc_code_syms_to_metrics_create_table: Error: "
+ "pdf_fcn_0_bit must be a non-null pointer to function.\n";
+ assert (0);
+ }
+ if (n_samples < 2) {
+ std::cerr << "libecc_code_syms_to_metrics_create_table: Error: "
+ "n_samples must be at least 2.\n";
+ assert (0);
+ }
+ if (min_sample >= max_sample) {
+ std::cerr << "libecc_code_syms_to_metrics_create_table: Error: "
+ "min_sample must be less than max_sample.\n";
+ assert (0);
+ }
+ if ((sample_precision < 0) | (sample_precision > 32)) {
+ std::cerr << "libecc_code_syms_to_metrics_create_table: Error: "
+ "sample_precision must be between 0 and 32.\n";
+ assert (0);
+ }
+
+ code_syms_to_metrics<pdf_fcn_io_t>* t_code_syms_to_metrics = 0;
+
+ if (sample_precision == 0) {
+ // float
+ t_code_syms_to_metrics = new code_syms_to_metrics_work
+ <pdf_fcn_io_t, float>(pdf_fcn_0_bit,
+ pdf_fcn_1_bit,
+ n_samples,
+ min_sample,
+ max_sample);
+ } else if (sample_precision <= 8) {
+ // use char
+ t_code_syms_to_metrics = new code_syms_to_metrics_work
+ <pdf_fcn_io_t, unsigned char>(pdf_fcn_0_bit,
+ pdf_fcn_1_bit,
+ n_samples,
+ min_sample,
+ max_sample,
+ sample_precision);
+ } else if (sample_precision <= 16) {
+ // use short
+ t_code_syms_to_metrics = new code_syms_to_metrics_work
+ <pdf_fcn_io_t, unsigned short>(pdf_fcn_0_bit,
+ pdf_fcn_1_bit,
+ n_samples,
+ min_sample,
+ max_sample,
+ sample_precision);
+ } else {
+ // use long
+ t_code_syms_to_metrics = new code_syms_to_metrics_work
+ <pdf_fcn_io_t, unsigned long>(pdf_fcn_0_bit,
+ pdf_fcn_1_bit,
+ n_samples,
+ min_sample,
+ max_sample,
+ sample_precision);
+ }
+
+ return (t_code_syms_to_metrics);
+}
+
+template<typename pdf_fcn_io_t>
+code_syms_to_metrics<pdf_fcn_io_t>::code_syms_to_metrics
+(pdf_fcn_t pdf_fcn_0_bit,
+ pdf_fcn_t pdf_fcn_1_bit,
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample)
+{
+ // internally, all samples are taken as pdf_fcn_io_t initially, and
+ // only converted to other values by their specific constructors.
+
+ d_n_samples = n_samples;
+ d_max_sample = max_sample;
+ d_min_sample = min_sample;
+ d_delta = (max_sample - min_sample) / ((pdf_fcn_io_t) n_samples);
+ d_pdf_fcn_0_bit = pdf_fcn_0_bit;
+ d_pdf_fcn_1_bit = pdf_fcn_1_bit;
+
+ // use a sub-sample by 100 to better determine the actual "bin"
+ // probability values for each actual sample. Each "bin" is 100
+ // delta's less than the min_sample up to the min_sample+delta; then
+ // each delta; then from the max_sample-delta to 100 delta's more
+ // than the max sample. Once normalized, these give a reasonable
+ // interpretation of the PDF function.
+
+ pdf_fcn_io_t d_sub_delta = d_delta / ((pdf_fcn_io_t) 100);
+ pdf_fcn_io_t d_sub_min_sample = d_min_sample - ((pdf_fcn_io_t) 100)*d_delta;
+ pdf_fcn_io_t d_sup_max_sample = d_max_sample + ((pdf_fcn_io_t) 100)*d_delta;
+
+ d_pdf_fcn_0_samples.assign (d_n_samples, 0);
+ d_pdf_fcn_1_samples.assign (d_n_samples, 0);
+
+ pdf_fcn_io_t t_val, t_sum_0, t_sum_1, t_max_0, t_max_1, t_min_0, t_min_1;
+ t_sum_0 = t_sum_1 = t_max_0 = t_max_1 = t_min_0 = t_min_1 = 0;
+ size_t m = 0;
+ t_val = d_sub_min_sample;
+ for (; m < (d_n_samples - 1); m++) {
+ pdf_fcn_io_t t_sample_0 = 1;
+ pdf_fcn_io_t t_sample_1 = 1;
+ for (; t_val < (d_min_sample+d_delta); t_val += d_sub_delta) {
+ t_sample_0 += ((*d_pdf_fcn_0_bit)(t_val));
+ t_sample_1 += ((*d_pdf_fcn_1_bit)(t_val));
+ }
+ d_pdf_fcn_0_samples[m] = t_sample_0;
+ d_pdf_fcn_0_samples[m] = t_sample_1;
+ t_sum_0 += t_sample_0;
+ t_sum_1 += t_sample_1;
+ if (m == 0) {
+ t_max_0 = t_min_0 = t_sample_0;
+ t_max_1 = t_min_1 = t_sample_1;
+ } else {
+ if (t_max_0 < t_sample_0)
+ t_max_0 = t_sample_0;
+ else if (t_min_0 > t_sample_0)
+ t_min_0 = t_sample_0;
+ if (t_max_1 < t_sample_1)
+ t_max_1 = t_sample_1;
+ else if (t_min_1 > t_sample_1)
+ t_min_1 = t_sample_1;
+ }
+ }
+
+ pdf_fcn_io_t t_sample_0 = 1;
+ pdf_fcn_io_t t_sample_1 = 1;
+ for (; t_val < d_sup_max_sample; t_val += d_sub_delta) {
+ t_sample_0 += ((*d_pdf_fcn_0_bit)(t_val));
+ t_sample_1 += ((*d_pdf_fcn_1_bit)(t_val));
+ }
+ d_pdf_fcn_0_samples[m] = t_sample_0;
+ d_pdf_fcn_0_samples[m] = t_sample_1;
+ t_sum_0 += t_sample_0;
+ t_sum_1 += t_sample_1;
+ if (t_max_0 < t_sample_0)
+ t_max_0 = t_sample_0;
+ else if (t_min_0 > t_sample_0)
+ t_min_0 = t_sample_0;
+ if (t_max_1 < t_sample_1)
+ t_max_1 = t_sample_1;
+ else if (t_min_1 > t_sample_1)
+ t_min_1 = t_sample_1;
+
+ // normalize to the sum, so that these are "real" probabilities.
+
+ for (m = 0; m < d_n_samples; m++) {
+ d_pdf_fcn_0_samples[m] /= t_sum_0;
+ d_pdf_fcn_1_samples[m] /= t_sum_1;
+ }
+ t_max_0 /= t_sum_0;
+ t_min_0 /= t_sum_0;
+ t_max_1 /= t_sum_1;
+ t_min_1 /= t_sum_1;
+
+ // take the logf so that metrics can add
+
+ for (m = 0; m < d_n_samples; m++) {
+ d_pdf_fcn_0_samples[m] = logf (d_pdf_fcn_0_samples[m]);
+ d_pdf_fcn_1_samples[m] = logf (d_pdf_fcn_1_samples[m]);
+ }
+ t_max_0 = logf (t_max_0);
+ t_min_0 = logf (t_min_0);
+ t_max_1 = logf (t_max_1);
+ t_min_1 = logf (t_min_1);
+
+ // higher (less negative) log-probabilities mean more likely; lower
+ // (more negative) mean less likely. Want metrics which are 0 when
+ // most likely and more positive when less likely. So subtract the
+ // max, then negate and normalize to the min (new max) so that the
+ // max value is 1 and the min value is 0.
+
+ for (m = 0; m < d_n_samples; m++) {
+ d_pdf_fcn_0_samples[m] = ((d_pdf_fcn_0_samples[m] - t_max_0) /
+ (t_min_0 - t_max_0));
+ d_pdf_fcn_1_samples[m] = ((d_pdf_fcn_1_samples[m] - t_max_1) /
+ (t_min_1 - t_max_1));
+ }
+
+ // correct the delta to the lookup computations
+
+ d_delta = (max_sample - min_sample) / ((pdf_fcn_io_t)(n_samples-1));
+}
+
+template<typename pdf_fcn_io_t, typename metric_t>
+code_syms_to_metrics_work<pdf_fcn_io_t,metric_t>::code_syms_to_metrics_work
+(pdf_fcn_t pdf_fcn_0_bit,
+ pdf_fcn_t pdf_fcn_1_bit,
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample,
+ int sample_precision)
+ : code_syms_to_metrics<pdf_fcn_io_t>
+ (pdf_fcn_0_bit,
+ pdf_fcn_1_bit,
+ n_samples,
+ min_sample,
+ max_sample)
+{
+ code_syms_to_metrics<pdf_fcn_io_t>::d_out_item_size_bytes = sizeof
(metric_t);
+ code_syms_to_metrics<pdf_fcn_io_t>::d_sample_precision = sample_precision;
+
+ // get the scale factor for converting from float to
+ // sample_precision maps: 0 -> 0, 1 -> (2^sample_precision)-1 for
+ // integers; there is no need for a mapping for float types, since
+ // those are already in [0,1].
+
+ pdf_fcn_io_t t_mult = ((sample_precision == 0) ? 1 :
+ ((pdf_fcn_io_t)((2^sample_precision)-1)));
+
+ // convert the 0 bit metrics from float to integer
+
+ d_metric_table_0_bit.assign (n_samples, 0);
+ for (size_t m = 0; m < n_samples; m++) {
+ d_metric_table_0_bit[m] =
+ (metric_t)((code_syms_to_metrics<pdf_fcn_io_t>::d_pdf_fcn_0_samples[m]) *
+ t_mult);
+ }
+
+ // clear the old float sample vectors to free memory
+
+ code_syms_to_metrics<pdf_fcn_io_t>::d_pdf_fcn_0_samples.resize (0);
+
+ // convert the 1 bit metrics from float to integer
+
+ d_metric_table_1_bit.assign (n_samples, 0);
+ for (size_t m = 0; m < n_samples; m++) {
+ d_metric_table_1_bit[m] =
+ (metric_t)((code_syms_to_metrics<pdf_fcn_io_t>::d_pdf_fcn_1_samples[m]) *
+ t_mult);
+ }
+
+ // clear the old float sample vectors to free memory
+
+ code_syms_to_metrics<pdf_fcn_io_t>::d_pdf_fcn_1_samples.resize (0);
+}
+
+template<typename pdf_fcn_io_t, typename metric_t>
+void
+code_syms_to_metrics_work<pdf_fcn_io_t,metric_t>::lookup
+(pdf_fcn_io_t sym,
+ void* bit_0,
+ void* bit_1)
+{
+ metric_t_ptr l_bit_0 = (metric_t_ptr) bit_0;
+ metric_t_ptr l_bit_1 = (metric_t_ptr) bit_1;
+
+ if (sym <= code_syms_to_metrics<pdf_fcn_io_t>::d_min_sample) {
+ *l_bit_0 = d_metric_table_0_bit[0];
+ *l_bit_1 = d_metric_table_1_bit[0];
+ return;
+ }
+ if (sym >= code_syms_to_metrics<pdf_fcn_io_t>::d_max_sample) {
+ *l_bit_0 = d_metric_table_0_bit.back ();
+ *l_bit_1 = d_metric_table_1_bit.back ();
+ return;
+ }
+
+ size_t l_ndx = (size_t) round
+ ((double)((sym - code_syms_to_metrics<pdf_fcn_io_t>::d_min_sample) /
+ code_syms_to_metrics<pdf_fcn_io_t>::d_delta));
+ *l_bit_0 = d_metric_table_0_bit[l_ndx];
+ *l_bit_1 = d_metric_table_1_bit[l_ndx];
+}
+
+template<typename pdf_fcn_io_t, typename metric_t>
+void
+code_syms_to_metrics_work<pdf_fcn_io_t,metric_t>::convert
+(size_t n_syms,
+ pdf_fcn_io_t* sym,
+ void* bit_0,
+ void* bit_1)
+{
+ metric_t_ptr l_bit_0 = (metric_t_ptr) bit_0;
+ metric_t_ptr l_bit_1 = (metric_t_ptr) bit_1;
+
+ for (size_t m = n_syms; m > 0; m--)
+ lookup (*sym++, (void*) l_bit_0++, (void*) l_bit_1++);
+}
+
+// force the compiler to instantiate a particular version of the
+// templated super-class, for <float> PDF function precision because
+// all code_syms_to_metrics classes are created by this function, this is the
+// only one which is required to instantaite.
+
+template
+code_syms_to_metrics<float>*
+libecc_code_syms_to_metrics_create_table<float>
+(float (*pdf_fcn_0_bit) (float),
+ float (*pdf_fcn_1_bit) (float),
+ size_t n_samples,
+ float min_sample,
+ float max_sample,
+ int sample_precision);
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.h
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_syms_to_metrics.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,150 @@
+/* -*- 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_CODE_SYMS_TO_METRICS_H
+#define INCLUDED_CODE_SYMS_TO_METRICS_H
+
+#include "code_types.h"
+#include <vector>
+
+template<typename pdf_fcn_io_t>
+class code_syms_to_metrics;
+
+template<typename pdf_fcn_io_t>
+code_syms_to_metrics<pdf_fcn_io_t>*
+libecc_code_syms_to_metrics_create_table
+(pdf_fcn_io_t (*pdf_fcn_0_bit) (pdf_fcn_io_t),
+ pdf_fcn_io_t (*pdf_fcn_1_bit) (pdf_fcn_io_t),
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample,
+ int sample_precision = 10);
+
+template<typename pdf_fcn_io_t>
+class code_syms_to_metrics
+{
+/*
+ * class code_syms_to_metrics: metrics table for convolutional
+ * codes. Pre-compute a lookup table upon instantiation, which makes
+ * for quick conversion from soft-float symbol value ('sym') to metric
+ * value. The symbol value probability is defined by the arguments
+ * 'pdf_fcn_0_bit' and 'pdf_fcn_1_bit' for p(0|sym) and p(1|sym)
+ * respectively. Internally, the PDF's are sampled and normalized to
+ * always have a minimum value of 0. For float-precision, the maximum
+ * value is 1.0, while for integer M-bits the maximum value is
+ * (2^M)-1. Smaller metric values indicate that the received symbols
+ * are closer to the given output bits; larger values indicate greater
+ * differences. The only constraint on the PDF functions are that
+ * they are piecewise continuous; otherwise, they don't even have to
+ * be a true PDF in terms of the integral from -inf to +inf being
+ * equal to 1 due to the normalization.
+ *
+ * Storage type for the tables is determined by the "sample_precision"
+ * argument. When the precision equals 0, 32-bit float storage is
+ * used; otherwise, the next largest standard integer type is used
+ * unsigned (char for 1 to 8 bits, short for 9 to 16 bits, and long
+ * for 17 to 32 bits). For the purposes of coding gain, any
+ * sample_precision larger than about 9 will have minimal added
+ * benefit under most conditions where communications are possible.
+ * Trellis computations are performed in either 32-bit float (for
+ * float storage) or 32-bit unsigned long (for all integer storage).
+ *
+ * The number of samples to store is determined by the "n_samples"
+ * argument, which must be at least 2 but is otherwise not limited
+ * except by the memory of the host computer.
+ *
+ * Samples of the PDF functions are taken from "min_sample" to
+ * "max_sample", which represent the floor and ceiling on input symbol
+ * values below and above which symbol values are truncated.
+ * Internally, a sub-n_samples value is determined and used to "sum"
+ * the PDF functions to divide the probabilities into "bins".
+ */
+
+public:
+ typedef pdf_fcn_io_t (*pdf_fcn_t) (pdf_fcn_io_t);
+
+ virtual ~code_syms_to_metrics () {};
+
+ // lookup() returns either a float, or a sign-extended
+ // 'sample_precision'-bit integer value.
+
+ virtual void lookup (pdf_fcn_io_t sym,
+ void* bit_0,
+ void* bit_1) = 0;
+
+ // convert does a lookup on 'n_syms' input symbols
+
+ virtual void convert (size_t n_syms,
+ pdf_fcn_io_t* syms,
+ void* bit_0,
+ void* bit_1) = 0;
+
+ inline const unsigned char out_item_size_bytes ()
+ {return(d_out_item_size_bytes);};
+
+protected:
+ code_syms_to_metrics (pdf_fcn_t pdf_fcn_0_bit,
+ pdf_fcn_t pdf_fcn_1_bit,
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample);
+
+ unsigned char d_out_item_size_bytes, d_sample_precision;
+ size_t d_n_samples;
+ pdf_fcn_io_t d_max_sample, d_min_sample, d_delta;
+ pdf_fcn_t d_pdf_fcn_0_bit, d_pdf_fcn_1_bit;
+ std::vector<pdf_fcn_io_t> d_pdf_fcn_0_samples, d_pdf_fcn_1_samples;
+};
+
+template<typename pdf_fcn_io_t, typename metric_t>
+class code_syms_to_metrics_work : public code_syms_to_metrics<pdf_fcn_io_t>
+{
+public:
+ typedef metric_t *metric_t_ptr;
+ typedef pdf_fcn_io_t (*pdf_fcn_t) (pdf_fcn_io_t);
+
+ ~code_syms_to_metrics_work () {};
+
+ void lookup (pdf_fcn_io_t sym, void* bit_0, void* bit_1);
+ void convert (size_t n_syms, pdf_fcn_io_t* sym, void* bit_0, void* bit_1);
+
+protected:
+ code_syms_to_metrics_work (pdf_fcn_t pdf_fcn_0_bit,
+ pdf_fcn_t pdf_fcn_1_bit,
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample,
+ int sample_precision = 10);
+
+ friend code_syms_to_metrics<pdf_fcn_io_t>*
+ libecc_code_syms_to_metrics_create_table<pdf_fcn_io_t>
+ (pdf_fcn_io_t (*pdf_fcn_0_bit) (pdf_fcn_io_t),
+ pdf_fcn_io_t (*pdf_fcn_1_bit) (pdf_fcn_io_t),
+ size_t n_samples,
+ pdf_fcn_io_t min_sample,
+ pdf_fcn_io_t max_sample,
+ int sample_precision);
+
+ std::vector<metric_t> d_metric_table_0_bit, d_metric_table_1_bit;
+};
+
+#endif /* INCLUDED_CODE_SYMS_TO_METRICS_H */
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_types.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_types.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/code_types.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -26,6 +26,6 @@
// the following is the type used for encoder memory
-typedef unsigned long memory_t, *memory_ptr_t;
+typedef u_int32_t memory_t, *memory_ptr_t;
#endif /* INCLUDED_CODE_TYPES_H */
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -27,1086 +27,263 @@
#include <decoder_viterbi.h>
#include <assert.h>
#include <iostream>
+#include <math.h> // for ceilf ()
-const int g_max_block_size_bits = 10000000;
-const int g_max_num_streams = 10;
-const int g_num_bits_per_byte = 8;
-
#define DO_TIME_THOUGHPUT 0
-#define DO_PRINT_DEBUG_INST 0
-#define DO_PRINT_DEBUG_INST_0 0
-#define DO_PRINT_DEBUG_INST_1 0
-#define DO_PRINT_DEBUG_INST_2 0
-#define DO_PRINT_DEBUG_FSM 0
-#define DO_PRINT_DEBUG_INIT 0
-#define DO_PRINT_DEBUG_UP 0
-#define DO_PRINT_DEBUG_UP_0 0
-#define DO_PRINT_DEBUG_UP_1 0
-#define DO_PRINT_DEBUG_MIDDLE 0
-#define DO_PRINT_DEBUG_MIDDLE_0 0
-#define DO_PRINT_DEBUG_MIDDLE_1 0
-#define DO_PRINT_DEBUG_TERM 0
-#define DO_PRINT_DEBUG_TERM_1 0
-#define DO_PRINT_DEBUG_OUTPUT 0
-#define DO_PRINT_DEBUG_OUTPUT_0 0
-#define DO_PRINT_DEBUG_EXIT 0
#define DO_PRINT_DEBUG 0
+#define DO_PRINT_DEBUG_VARS 0
+#define DO_PRINT_DEBUG_FSM 0
#include <mld/mld_timer.h>
#include <mld/n2bs.h>
-
-#if 0
-// at instantiation
-
- // for compute_all_outputs
-
- in_l[0].resize (d_n_code_outputs);
- in_l[1].resize (d_n_code_outputs);
- in_f[0].resize (d_n_code_outputs);
- in_f[1].resize (d_n_code_outputs);
-#endif
-
-#if 0
-template<typename pdf_fcn_io_t, typename computation_t>
-void
-code_metrics<pdf_fcn_io_t>::compute_all_outputs
-(pdf_fcn_io_t* syms,
- std::vector<computation_t>& out)
+template<typename computation_t>
+decoder_viterbi<computation_t>::decoder_viterbi
+(const encoder_convolutional* encoder,
+ u_int8_t sample_precision,
+ bool full_or_partial,
+ u_int32_t n_bits_before_decode)
{
- // use the first 'n_code_output' symbols, convert them into metrics,
- // then call the other "compute_all_outputs"
-
- convert (d_n_code_outputs, syms,
- (void*)(&(in_c[0][0])), (void*)(&in_c[1][0]));
-
- compute_all_outputs (&(in_c[0][0]), out);
-}
-
-template<typename metric_t, typename computation_t>
-void
-code_metrics<metric_t>::compute_all_outputs
-(metric_t** metrics,
- std::vector<computation_t>& out)
-{
- // compute all possible (summation) combinations of the metrics
- // using <computation_t>-precision (e.g. "float") computations and
- // return those in the provided vector.
-
- // the input metrics must be a [2][d_n_code_outputs] "matrix", with
- // the [0][] and [1][] entries representing p(0|sym) and p(1|sym),
- // respectively.
-
- // assign the starting minimum metric to 0. This is safe because
- // metrics are always non-negative.
-
- computation_t min_metric = 0;
- for (size_t m = 0; m < (((size_t)1) << d_n_code_outputs); m++) {
- size_t t_out_ndx = m;
- computation_t t_metric = 0;
- for (size_t n = 0; n < d_n_code_outputs; n++, t_out_ndx >>= 1)
- t_metric += metrics[t_out_ndx&1][n];
- if (t_metric < min_metric)
- min_metric = t_metric;
- out[m] = t_metric;
- }
-
- // normalize so that the minimum metric equals 0
-
- for (size_t m = 0; m < d_n_code_outputs; m++)
- out[m] -= min_metric;
-}
-#endif
-
-decoder_viterbi::decoder_viterbi
-(int sample_precision,
- const encoder_convolutional* l_encoder)
-{
// make sure that the encoder is "valid"
- if (! l_encoder) {
+ if (! encoder) {
std::cerr << "decoder_viterbi: Error: Encoder is NULL.\n";
assert (0);
}
- // make the metrics converter
+ // make sure the sample precision is valid
- // d_code_metrics = new code_metrics (
-
- if ((sample_precision < 0) | (sample_precision > 32)) {
- std::cerr << "decoder_viterbi: "
- "Requested sample_precision (" << sample_precision <<
- ") must be between 0 and 32.\n";
+ if (sample_precision == 0) {
+ // FIXME : very different setup for float
+ std::cout << "decoder_viterbi:: Not set up for <float> precision yet"
+ " ... sorry.\n";
assert (0);
+ } else if (sample_precision > 32) {
+ std::cout << "decoder_viterbi:: Error: Provided sample precision (" <<
+ ((int)sample_precision) << ") must be in the range [0,32].\n";
+ assert (0);
}
// get the trellis
- d_encoder = (encoder_convolutional*) l_encoder;
- d_trellis = (code_convolutional_trellis*) d_encoder->trellis ();
+ d_encoder = (code_convolutional_trellis*) encoder;
+ d_trellis = d_encoder->trellis ();
// fill the class variables
- d_block_size_bits = d_encoder->block_size_bits ();
- d_n_code_inputs = d_encoder->n_code_inputs ();
- d_n_code_outputs = d_encoder->n_code_outputs ();
- d_do_termination = d_encoder->do_termination ();
- d_total_n_delays = d_encoder->total_n_delays ();
+ d_block_size_bits = d_trellis->block_size_bits ();
+ d_n_code_inputs = d_trellis->n_code_inputs ();
+ d_n_code_outputs = d_trellis->n_code_outputs ();
+ d_do_termination = d_trellis->do_termination ();
+ d_n_bits_to_term = d_trellis->n_bits_to_term ();
d_n_states = d_trellis->n_states ();
d_n_input_combinations = d_trellis->n_input_combinations ();
+ d_do_streaming = d_trellis->do_streaming ();
- // really nothing else to do here, since this class doesn't "know"
- // how to process streaming versus block decoding, or partial
- // trellis versus full-trellis. Those will be handled by
- // sub-classes which inherit from this one.
+ // make sure the number of bits before decode make sense
- if (DO_PRINT_DEBUG_INST_0) {
- std::cout << "Init:\n" <<
- "d_block_size_bits = " << d_block_size_bits << "\n" <<
- "d_n_code_inputs = " << d_n_code_inputs << "\n" <<
- "d_n_code_outputs = " << d_n_code_outputs << "\n" <<
- "d_do_termination = " <<
- ((d_do_termination == true) ? "true" : "false") << "\n" <<
- "d_total_n_delays = " << d_total_n_delays << "\n" <<
- "d_n_states = " << d_n_states << "\n" <<
- "d_n_input_combinations = " << d_n_input_combinations << "\n";
+ if ((full_or_partial == G_LIBECC_DECODE_PARTIAL) &
+ (d_do_streaming == false)) {
+ size_t total_block_size_bits = d_block_size_bits;
+ if (d_do_termination == true)
+ total_block_size_bits += d_n_bits_to_term;
+ if (n_bits_before_decode >= total_block_size_bits) {
+ std::cout << "decoder_viterbi:: Warning: Provided # of bit-time "
+ "inputs to process before decoding one bit (" <<
+ n_bits_before_decode << ") is larger than the total block size "
+ "including any termination bits (" << total_block_size_bits <<
+ "). Reverting to full block decoding.\n";
+ }
+ full_or_partial = G_LIBECC_DECODE_FULL;
}
- // always start the fsm in the "init" state
+ d_do_full_or_partial = full_or_partial;
- d_fsm_state = fsm_dec_viterbi_init;
+ if ((n_bits_before_decode == 0) &
+ (d_do_full_or_partial == G_LIBECC_DECODE_PARTIAL)) {
- // create a vector of indexes to states when doing "up" or "termination";
+ // set the number of bits to 5.3 constraint lengths, rounded up
+ n_bits_before_decode =
+ (size_t) ceilf (((float) 5.3) *
+ (((float) d_trellis->total_n_delays ()) + 1));
+ }
- d_up_term_states_ndx[0] = new size_t [d_n_states];
- d_up_term_states_ndx[1] = new size_t [d_n_states];
+ d_n_bits_before_decode = n_bits_before_decode;
- // get the total number of out bits per stream
+ if (d_do_full_or_partial == G_LIBECC_DECODE_FULL) {
+ // full block decoding checks
- d_n_total_inputs_per_stream = d_block_size_bits;
- if (d_do_termination == true)
- d_n_total_inputs_per_stream += d_total_n_delays;
-}
+ // verify that the block size is non-zero
-decoder_viterbi::~decoder_viterbi
-()
-{
- // reverse over from allocation
-#if 0
- delete [] d_up_term_states_ndx[0];
- delete [] d_up_term_states_ndx[1];
+ if (d_block_size_bits == 0) {
+ std::cerr << "decoder_viterbi_full: Error: "
+ "Block size is 0, indicating partial block or stream decoding ... "
+ "must be positive for block decoding.\n";
+ assert (0);
+ }
- // delete the state's structures
+ // set the total number of encoder-output bits per stream for full
+ // block processing, this is the block size + any termination bits
- state_t_ptr t_state = d_states[0];
- for (size_t n = d_n_states; n > 0; n--, t_state++) {
- connection_t_ptr t_connection = t_state->d_connections;
- for (size_t m = d_n_input_combinations; m > 0; m--, t_connection++) {
- delete [] t_connection->d_output_bits;
- }
- delete [] t_state->d_connections;
+ d_total_n_inputs_per_stream = d_block_size_bits;
+ if (d_do_termination == true)
+ d_total_n_inputs_per_stream += d_n_bits_to_term;
+
+ // create the state trellis; for full/block, use the total # of
+ // time-bits to decode + 1: each set of inputs is represented by a
+ // transition between traceback elements.
+
+ d_n_state_trellis_time_bits = d_total_n_inputs_per_stream + 1;
+
+ // set up the nodes w/ the correct number to pre-allocate
+
+ d_total_n_nodes_to_alloc = d_total_n_inputs_per_stream * d_n_states;
+ } else {
+ // partial
+
+ // set the total number of encoder-output bits per stream for full
+ // block processing, this is the block size + any termination bits
+
+ d_total_n_inputs_per_stream = d_n_bits_before_decode;
+
+ // create the state trellis; for partial, use the total # of
+ // time-bits to decode + 1: each set of inputs is represented by a
+ // transition between traceback elements.
+
+ d_n_state_trellis_time_bits = d_total_n_inputs_per_stream + 1;
+
+ // set up the nodes w/ the correct number to pre-allocate
+
+ d_total_n_nodes_to_alloc = d_total_n_inputs_per_stream * d_n_states;
}
- delete [] d_states[0];
- t_state = d_states[1];
- for (size_t n = d_n_states; n > 0; n--, t_state++) {
- connection_t_ptr t_connection = t_state->d_connections;
- for (size_t m = d_n_input_combinations; m > 0; m--, t_connection++) {
- delete [] t_connection->d_output_bits;
- }
- delete [] t_state->d_connections;
+ if (DO_PRINT_DEBUG_VARS) {
+ std::cout << "Decoder Viterbi Init:\n"
+ "block_size_bits = " << d_block_size_bits << "\n"
+ "n_code_inputs = " << d_n_code_inputs << "\n"
+ "n_code_outputs = " << d_n_code_outputs << "\n"
+ "do_termination = " <<
+ ((d_do_termination == true) ? "true" : "false") << "\n"
+ "n_bits_to_term = " << d_n_bits_to_term << "\n"
+ "n_states = " << d_n_states << "\n"
+ "n_input_combinations = " << d_n_input_combinations << "\n"
+ "do_streaming = " <<
+ ((d_do_streaming == true) ? "true" : "false") << "\n"
+ "do_full_or_partial = " <<
+ ((d_do_full_or_partial == G_LIBECC_DECODE_FULL) ?
+ "full" : "partial") << "\n" <<
+ "n_bits_before_decode = " << d_n_bits_before_decode << "\n"
+ "total_n_nodes_to_alloc = " << d_total_n_nodes_to_alloc << "\n"
+ "total_n_inputs_per_stream = " << d_total_n_inputs_per_stream << "\n"
+ "n_state_trellis_time_bits = " << d_n_state_trellis_time_bits << "\n";
}
- delete [] d_states[1];
- // delete the save buffer
+ // always start the fsm in the "init" state
- char** t_save_buffer = d_save_buffer;
- for (size_t n = 0; n < d_n_code_inputs; n++) {
- delete [] (*t_save_buffer++);
+ d_fsm_state = fsm_dec_viterbi_init;
+
+ if (d_do_termination == true) {
+ // create a vector of indexes to states when doing termination
+
+ d_term_states_ndx[0].resize (d_n_states);
+ d_term_states_ndx[1].resize (d_n_states);
}
- delete [] d_save_buffer;
-#endif
}
+template<typename computation_t>
void
-decoder_viterbi::reset_metrics
-(u_char which)
+decoder_viterbi<computation_t>::expand_node
+(void* in_node)
{
- state_t_ptr t_state = d_states[which&1];
- for (size_t n = d_n_states; n > 0; n--, t_state++) {
- t_state->d_max_metric = -1e10;
-#if 0
-// probably don't need to do these, try removing them later
- t_state->d_max_state_ndx = 0;
- t_state->d_max_input = -1;
-#endif
- }
+ if ((d_do_termination == true) &
+ (get_time (in_node) >= d_block_size_bits))
+ expand_node__term (in_node);
+ else
+ expand_node__input (in_node);
}
+template<typename computation_t>
void
-decoder_viterbi::zero_metrics
-(u_char which)
+decoder_viterbi<computation_t>::do_init
+()
{
- state_t_ptr t_state = d_states[which&1];
- for (size_t n = d_n_states; n > 0; n--, t_state++) {
- t_state->d_max_metric = 0;
-#if 0
-// probably don't need to do these, try removing them later
- t_state->d_max_state_ndx = -1;
- t_state->d_max_input = -1;
-#endif
+ if (d_do_termination == true) {
+ // reset the termination stuff
+
+ d_n_term_bits = 0;
+ d_which_term = 0;
+ d_term_ndx[0] = d_n_states;
+
+ for (memory_t m = 0; m < d_n_states; m++)
+ d_term_states_ndx[0] = m;
+
+ // FIXME: this might not be necessary; might be necessary to set
+ // just the [0] entries
+ d_term_ndx[1] = 0;
+ d_term_states_ndx[1].assign (d_n_states, 0);
}
}
+template<typename computation_t>
void
-decoder_viterbi::decode_private
+decoder_viterbi<computation_t>::decode_private
()
{
-#if 0
-
-#if DO_TIME_THOUGHPUT
struct timeval t_tp;
- start_timer (&t_tp);
-#endif
-#if DO_PRINT_DEBUG
- size_t t_state_print_bits = d_total_n_delays;
- size_t t_mem_print_bits = d_total_n_delays;
-#endif
-// setup variables for quicker access
- const char **in_buf = (const char **) &input_items[0];
- char **out_buf = (char **) &output_items[0];
- int t_in_buf_ndx = 0, t_out_buf_ndx = 0;
- int t_out_bit_shift = 0;
- int t_ninput_items = compute_n_input_metrics (noutput_items);
- int t_noutput_bits = noutput_items;
+ if (DO_TIME_THOUGHPUT)
+ start_timer (&t_tp);
-#if DO_PRINT_DEBUG_INST
- std::cout << "# output items = " << noutput_items << " (" <<
- t_noutput_bytes << " Bytes, " << (t_noutput_bytes * g_num_bits_per_byte) <<
- " bits), # input items = " << t_ninput_items << " Symbols\n";
- for (size_t n = 0; n < ninput_items.size(); n++) {
- std::cout << "# input items [" << n << "] = " << ninput_items[n] << "\n";
- }
-#endif
+ // jump to the correct state in the fsm
-// put any leftover bits into the output
- if (d_n_saved_bits != 0) {
-// copy the leftover from the save buffer
-// check to make sure it will all fit
- size_t t_noutput_bits = t_noutput_bytes * g_num_bits_per_byte;
- size_t t_n_copy;
- if (t_noutput_bits < d_n_saved_bits) {
-// asking for fewer bits than available; set to copy
-// just what's being asked for
- t_n_copy = t_noutput_bytes;
- } else {
-// asking for at least as many bits as available; set to copy all
- t_out_buf_ndx = d_n_saved_bits / g_num_bits_per_byte;
- t_out_bit_shift = d_n_saved_bits % g_num_bits_per_byte;
- t_n_copy = t_out_buf_ndx + (t_out_bit_shift != 0 ? 1 : 0);
+ switch (d_fsm_state) {
+ case fsm_dec_viterbi_init:
+ if (DO_PRINT_DEBUG_FSM) {
+ std::cout << "Starting FSM Decoder Viterbi Init\n";
}
-// do the copy for all output streams (code inputs)
-// copy starting at save buffer index "start"
- for (size_t n = 0; n < d_n_code_inputs; n++)
- bcopy (&(d_save_buffer[n][d_n_saved_bits_start_ndx]),
- out_buf[n], t_n_copy);
-#if DO_PRINT_DEBUG_INST
- std::cout << "Copied " << t_n_copy << " Byte" <<
- (t_n_copy != 1 ? "s" : "") << ": s_b[][" <<
- d_n_saved_bits_start_ndx << "] => o_b[][0]\n" <<
- "# saved bits = " << d_n_saved_bits <<
- ", o_b_ndx = " << t_out_buf_ndx <<
- ", bit shift = " << t_out_bit_shift << "\n";
-#endif
-// update the number of saved bits and start
- if (t_noutput_bits < d_n_saved_bits) {
-// asking for fewer bit than available: update
-// the number of saved bits and their starting index
- d_n_saved_bits_start_ndx += t_noutput_bytes;
- d_n_saved_bits -= (t_noutput_bytes * g_num_bits_per_byte);
-#if DO_PRINT_DEBUG_INST
- std::cout << "Updated # saved bits = " << d_n_saved_bits <<
- ", index = " << d_n_saved_bits_start_ndx << "\n";
-#endif
-// nothing to consume; return the desired number of output items
- return (noutput_items);
- } else {
- d_n_saved_bits_start_ndx = d_n_saved_bits = 0;
- }
- }
-#if DO_PRINT_DEBUG_INST
- std::cout << "Starting FSM in state: " <<
- (d_fsm_state == fsm_dec_viterbi_init ? "init" :
- (d_fsm_state == fsm_dec_viterbi_doing_up ? "up" :
- (d_fsm_state == fsm_dec_viterbi_doing_middle ? "middle" :
- (d_fsm_state == fsm_dec_viterbi_doing_term ? "term" :
- (d_fsm_state == fsm_dec_viterbi_output ? "output" : "unknown"))))) <<
"\n";
-#endif
-// while there are input items to create
- while (t_out_buf_ndx < t_noutput_bytes) {
-#if DO_PRINT_DEBUG_FMS
- std::cout << "Starting 'while': processing " << t_in_buf_ndx << " of " <<
- t_ninput_items << " items.\nJumping to state '" <<
- (d_fsm_state == fsm_dec_viterbi_init ? "init" :
- (d_fsm_state == fsm_dec_viterbi_doing_up ? "up" :
- (d_fsm_state == fsm_dec_viterbi_doing_middle ? "middle" :
- (d_fsm_state == fsm_dec_viterbi_doing_term ? "term" :
- (d_fsm_state == fsm_dec_viterbi_output ? "output" : "unknown"))))) <<
"'\n";
-#endif
-// jump to the correct state in the fsm
- switch (d_fsm_state) {
- case fsm_dec_viterbi_doing_up:
-#if 0
- encode_loop_up ();
-#endif
- break;
- case (fsm_dec_viterbi_doing_middle):
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Entered fsm_dec_viterbi_doing_middle\n";
-#endif
-// stay in this state until the correct number of input symbols is
-// reached (if doing block coding), or until there are no more input
-// symbols to parse
- while (((d_block_size_bits != 0) &
- (d_time_count < d_block_size_bits) &
- (t_in_buf_ndx < t_ninput_items)) |
- ((d_block_size_bits == 0) &
- (t_in_buf_ndx < t_ninput_items))) {
-// use all states, loop over all inputs, compute the metric for
-// each; compare the current metric with all previous stored metric in the
-// endpoint of the connection to find the highest one.
+ do_init ();
-// reset the "to" state's metrics
- reset_metrics (d_states_ndx ^ 1);
-// get the state's index for each set of new inputs
- state_t_ptr t_state = d_states[d_states_ndx];
-#if DO_PRINT_DEBUG_MIDDLE
- std::cout << "Time Count " << (d_time_count+1) << " of " <<
- d_block_size_bits << "\n" <<
- "d_states_ndx = " << d_states_ndx << "\n";
-#endif
-// loop over all current states
- for (size_t n = 0; n < d_n_states; n++, t_state++) {
-// loop over all possible input values, 1 bit per input stream
- connection_t_ptr t_connection = t_state->d_connections;
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << "Looping over all 'middle' states: " <<
- n << " of " << d_n_states << "\n";
-#endif
- for (size_t q = 0; q < d_n_input_combinations; q++, t_connection++) {
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << "Input = " << n2bs(q, d_n_code_inputs+1) << "\n";
-#endif
-// start with this state's metric
- float t_metric = t_state->d_max_metric;
-// get the "to" state
- state_t_ptr t_to_state = t_connection->d_to;
-// get that state's metric
- float t_to_metric = t_to_state->d_max_metric;
-// see if the computation is even needed;
-// maximum change is d_n_code_outputs if all bits match exactly
- if ((t_to_metric - t_metric) > ((float) 2*d_n_code_outputs)) {
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << "!not computing metric!\n";
-#endif
- continue;
- }
-// metrics are close enough; do the computation and the compare
-// get the output bits for this connection
- float* t_output_bit = t_connection->d_output_bits;
- if (d_do_mux_inputs == true) {
-// if using mux'ed input streams, handle differently
- const float* t_in_buf = &(in_buf[0][t_in_buf_ndx]);
-// loop over all encoder-output values
- for (size_t r = d_n_code_outputs; r > 0; r--) {
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << "in_sym = " << *t_in_buf << ", code_out_bit = " <<
- *t_output_bit << " ==> metric -> ";
-#endif
- t_metric += ((*t_in_buf++) * (*t_output_bit++));
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << t_metric << "\n";
-#endif
- }
- } else {
-// loop over all encoder-output values
- for (size_t r = 0; r < d_n_code_outputs; r++) {
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << "in_sym = " << in_buf[r][t_in_buf_ndx] <<
- ", code_out_bit = " << *t_output_bit << " ==> metric -> ";
-#endif
- t_metric += (in_buf[r][t_in_buf_ndx] * (*t_output_bit++));
-#if DO_PRINT_DEBUG_MIDDLE_0
- std::cout << t_metric << "\n";
-#endif
- }
- }
-// done with this input value; compare old and new metrics
- if (t_metric > t_to_metric) {
-#if DO_PRINT_DEBUG_MIDDLE
- std::cout << "New Metric to s[" <<
- n2bs (t_connection->d_to_ndx,t_state_print_bits) << "]: ";
- if (t_to_state->d_max_metric == -1e10) {
- std::cout << "setting to ";
- } else {
- std::cout << "was s[" <<
- n2bs(t_to_state->d_max_state_ndx,t_state_print_bits) <<
- "]i[" << n2bs (t_to_state->d_max_input, d_n_code_inputs+1) <<
- "]@ " << t_to_state->d_max_metric << " now ";
- }
- std::cout << "s[" << n2bs(n,t_state_print_bits) << "] i[" <<
- n2bs (q, d_n_code_inputs+1) << "]@ " << t_metric << "\n";
-#endif
-// new metric is better; copy that info into the "to" state
- t_to_state->d_max_metric = t_metric;
- t_to_state->d_max_state_ndx = n;
- t_to_state->d_max_input = q;
- }
-// finished (for) this input value
- }
-// finished (for) this state
- }
-// done with all states and all inputs; now update the traceback structure
-// change which d_states' index to use as starting
- d_states_ndx ^= 1;
-// get the state's index for the "to" set of new inputs to get the
-// "max" stuff from
- t_state = d_states[d_states_ndx];
-// update the traceback structure
-// loop over all current states
- traceback_t_ptr t_prev_out_bufs = d_out_buf[d_time_count];
- traceback_t_ptr t_out_bufs = d_out_buf[d_time_count+1];
-#if DO_PRINT_DEBUG_MIDDLE_1
- std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n";
-#endif
- for (size_t n = d_n_states; n > 0; n--, t_state++) {
-// simple: get the current state & output state
-// and connect output to the current, set inputs on output
- traceback_t_ptr t_out_buf = t_out_bufs++;
- traceback_t_ptr t_prev_out_buf =
- &(t_prev_out_bufs[t_state->d_max_state_ndx]);
-#if DO_PRINT_DEBUG_MIDDLE_1
- std::cout << "s[" << n2bs(d_n_states-n,t_state_print_bits) <<
- "]: max_ndx = " <<
- n2bs(t_state->d_max_state_ndx,t_state_print_bits) <<
- ", input = " << n2bs(t_state->d_max_input, d_n_code_inputs+1) <<
- ": " << t_out_buf << " => " << t_prev_out_buf << "\n";
-#endif
- t_out_buf->d_prev = t_prev_out_buf;
- t_out_buf->d_inputs = t_state->d_max_input;
-// finished doing this state
- }
-// increment the in_buf index, depending on mux'ing or not
- t_in_buf_ndx += (d_do_mux_inputs == false) ? 1 : d_n_code_outputs;
-// increment the time counter
- d_time_count++;
-// finished (while) staying in this fsm state or not
- }
- if ((d_block_size_bits != 0) &
- (d_time_count == d_block_size_bits)) {
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Setting FSM to fsm_dec_viterbi_doing_term\n";
-#endif
- d_fsm_state = fsm_dec_viterbi_doing_term;
- }
- break;
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Exited fsm_dec_viterbi_doing_middle\n";
-#endif
- case (fsm_dec_viterbi_doing_term):
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Entered fsm_dec_viterbi_doing_term\n";
-#endif
-// set the "next" up_down index to the end of their states
- size_t t_time_count = d_total_n_delays - (d_time_count -
d_block_size_bits);
- t_n_up_down_ndx = 1 << (d_n_code_inputs * t_time_count);
-// stay in this state until the correct number of input symbols are
-// reached; exit also if we run out of input symbols to process
- while ((t_time_count > 0) &
- (t_in_buf_ndx < t_ninput_items)) {
-#if DO_PRINT_DEBUG_TERM
- std::cout << "Doing time " << (d_total_n_delays - t_time_count + 1) <<
- " of " << d_total_n_delays << "; starting buf[" << t_in_buf_ndx <<
- "] of [" << t_ninput_items << "]\n";
-#endif
-// use the "to" states,
-// FIXME: loop over just the "0" inputs
-// and compute the metric for
-// each, compare & store it in the "to" state at the end of the connection.
+ d_fsm_state = fsm_dec_viterbi_doing_input;
-// reset the "to" state's metrics
- reset_metrics (d_states_ndx ^ 1);
-// reset the state's index for each set of new inputs
- size_t* t_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx];
- size_t* t_next_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx ^ 1];
-// loop over all current stored "term" state indeces
- for (size_t n = 0; n < t_n_up_down_ndx; n++) {
- size_t t_state_ndx = *t_state_ndx_ptr++;
- state_t_ptr t_state = &(d_states[d_states_ndx][t_state_ndx]);
-// loop over just the all 0 input value (d_connections[0])
- connection_t_ptr t_connection = t_state->d_connections;
-// get the "to" state
- state_t_ptr t_to_state = t_connection->d_to;
-// start with this state's metric
- float t_metric = t_state->d_max_metric;
-// get that state's metric
- float t_to_metric = t_to_state->d_max_metric;
-#if DO_PRINT_DEBUG_TERM
- std::cout << "Term state " << (n+1) << " of " << t_n_up_down_ndx <<
- "; using d_s[" << d_states_ndx << "][" <<
- n2bs(t_state_ndx,t_state_print_bits) << "]\n";
-#endif
-// see if the computation is even needed;
-// maximum change is d_n_code_outputs if all bits match exactly
- if ((t_to_metric - t_metric) > ((float) 2*d_n_code_outputs)) {
-#if DO_PRINT_DEBUG_TERM
- std::cout << "!not computing metric!\n";
-#endif
- continue;
- }
-// metrics are close enough; do the computation and the compare
-// get the output bits for this connection
- float* t_output_bit = t_connection->d_output_bits;
- if (d_do_mux_inputs == true) {
-// if using mux'ed input streams, handle differently
- const float* t_in_buf = &(in_buf[0][t_in_buf_ndx]);
-// loop over all encoder-output values
- for (size_t r = d_n_code_outputs; r > 0; r--) {
- t_metric += ((*t_in_buf++) * (*t_output_bit++));
- }
- } else {
-// loop over all encoder-output values
- for (size_t r = 0; r < d_n_code_outputs; r++) {
- t_metric += (in_buf[r][t_in_buf_ndx] * (*t_output_bit++));
- }
- }
-// done with this input value; compare old and new metrics
-// see if it's the best metric
- if (t_metric > t_to_metric) {
-#if DO_PRINT_DEBUG_TERM
- std::cout << "New Metric to s[" <<
- n2bs (t_connection->d_to_ndx,t_state_print_bits) << "]: ";
- if (t_to_state->d_max_metric == -1e10) {
- std::cout << "setting to ";
- } else {
- std::cout << "was s[" <<
- n2bs(t_to_state->d_max_state_ndx,t_state_print_bits) <<
- "]i[" << n2bs (t_to_state->d_max_input, d_n_code_inputs+1) <<
- "]@ " << t_to_state->d_max_metric << " now ";
- }
- std::cout << "s[" << n2bs(t_state_ndx,t_state_print_bits) <<
- "] i[" << n2bs (0, d_n_code_inputs+1) << "]@ " << t_metric <<
"\n";
-#endif
- t_to_state->d_max_metric = t_metric;
- t_to_state->d_max_state_ndx = t_state_ndx;
- t_to_state->d_max_input = 0;
- }
-// add the "to" state's index to the "next" set of state's indices list
- *t_next_state_ndx_ptr++ = t_connection->d_to_ndx;
-// finished (for) this state
- }
-// done with all states and all inputs; now update the traceback structure
-// change which d_states' index to use as starting
- d_states_ndx ^= 1;
-// update the number of "up_term" states
- d_up_term_ndx ^= 1;
-// reduce the number of using states
- t_n_up_down_ndx >>= d_n_code_inputs;
-// reset the state's index for each set of new inputs
- t_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx];
-// update the traceback structure
-// loop over all current states
- traceback_t_ptr t_prev_out_bufs = d_out_buf[d_time_count];
- traceback_t_ptr t_out_bufs = d_out_buf[d_time_count+1];
-#if DO_PRINT_DEBUG_TERM_1
- std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n";
-#endif
-// loop over all current stored "term" state indices
- for (size_t n = 0; n < t_n_up_down_ndx; n++) {
-// get the start index and then pointer to each of the "to" states,
-// which hold the newest "max" stuff
- size_t t_state_ndx = *t_state_ndx_ptr++;
- state_t_ptr t_state = &(d_states[d_states_ndx][t_state_ndx]);
-// simple: get the current state & output state
-// and connect output to the current, set inputs on output
- traceback_t_ptr t_out_buf = &(t_out_bufs[t_state_ndx]);
- traceback_t_ptr t_prev_out_buf =
- &(t_prev_out_bufs[t_state->d_max_state_ndx]);
-#if DO_PRINT_DEBUG_TERM_1
- std::cout << "ndx[" << n << "] == " << t_state_ndx <<
- ", s[" << n2bs(t_state_ndx,t_state_print_bits) <<
- "]: max_ndx = " <<
- n2bs(t_state->d_max_state_ndx,t_state_print_bits) <<
- ", input = " << n2bs(t_state->d_max_input, d_n_code_inputs+1) <<
- ": " << t_out_buf << " => " << t_prev_out_buf << "\n";
-#endif
- t_out_buf->d_prev = t_prev_out_buf;
- t_out_buf->d_inputs = t_state->d_max_input;
-// finished (for) this state
- }
-// increment the in_buf index, depending on mux'ing or not
- t_in_buf_ndx += (d_do_mux_inputs == false) ? 1 : d_n_code_outputs;
-// increment the time counters
- t_time_count--;
- d_time_count++;
-// finished (while) staying in this fsm state or not
- }
- if (t_time_count == 0) {
-// finished this trellis, now move as much of the decoded input to the
-// output buffer as possible
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Setting FSM to fsm_dec_viterbi_output\n";
-#endif
- d_fsm_state = fsm_dec_viterbi_output;
- }
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Exited fsm_dec_viterbi_doing_term\n";
-#endif
- break;
- case (fsm_dec_viterbi_output):
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Entered fsm_dec_viterbi_output.\n";
-#endif
-// this is done in reverse bit order (last time to first time)
-// using the traceback structure in d_out_buf, starting with
-// the maximum valued one in the last time slot, then using
-// the traceback's "d_prev" link to trace the trellis back
+ if (DO_PRINT_DEBUG_FSM) {
+ std::cout << "Setting state to FSM Decoder Viterbi Doing Input\n"
+ "Ending FSM Decoder Viterbi Init\n";
+ }
+ break;
-// see where the output data will terminate
- int t_next_out_buf_ndx = (t_out_buf_ndx +
- (d_block_size_bits / g_num_bits_per_byte));
- int t_next_out_bit_shift = (t_out_bit_shift +
- (d_block_size_bits % g_num_bits_per_byte));
- if (t_next_out_bit_shift >= g_num_bits_per_byte) {
- t_next_out_bit_shift -= g_num_bits_per_byte;
- t_next_out_buf_ndx++;
- }
-#if DO_PRINT_DEBUG_OUTPUT
- std::cout << "First bit in at out[][" << t_out_buf_ndx << "].[" <<
- t_out_bit_shift << "] -> " << d_block_size_bits << " bits == " <<
- (d_block_size_bits / g_num_bits_per_byte) << " Byte" <<
- ((d_block_size_bits / g_num_bits_per_byte) != 1 ? "s" : "") <<
- " + " << (d_block_size_bits % g_num_bits_per_byte) << " bit" <<
- ((d_block_size_bits % g_num_bits_per_byte) != 1 ? "s" : "") <<
- "\nNext set of bits start at out[][" << t_next_out_buf_ndx <<
- "].[" << t_next_out_bit_shift << "]\n";
-#endif
-// find the starting traceback structure
- traceback_t_ptr t_out_buf;
- if (d_do_termination == true) {
-// FIXME: assume termination state == 0
-#if DO_PRINT_DEBUG_OUTPUT_0
- std::cout << "Using termination; going through trellis for " <<
- d_total_n_delays << " bit" <<
- ((d_total_n_delays != 1) ? "s" : "") << "\n";
-#endif
- t_out_buf = &(d_out_buf[d_time_count][0]);
-#if DO_PRINT_DEBUG_OUTPUT_0
- std::cout << "Starting traceback ptr " << t_out_buf << "\n";
-#endif
-// skip over the termination bits
- for (size_t n = d_total_n_delays; n > 0; n--) {
- t_out_buf = t_out_buf->d_prev;
-#if DO_PRINT_DEBUG_OUTPUT_0
- std::cout << "Next traceback ptr " << t_out_buf << "\n";
-#endif
- }
- } else {
-// no termination but doing block coding;
-// FIXME: use the state with the bext metric
-// get the state's index for each set of new inputs
- state_t_ptr t_state = d_states[d_states_ndx];
- float t_max_metric = t_state->d_max_metric;
- size_t t_max_state_ndx = 0;
- t_state++;
-// loop over all current states
- for (size_t n = 1; n < d_n_states; n++, t_state++) {
-// start with this state's metric
- float t_metric = t_state->d_max_metric;
-// compare with current max
- if (t_metric > t_max_metric) {
- t_max_metric = t_metric;
- t_max_state_ndx = n;
- }
- }
-// get the correct out_buf reference to start with
- t_out_buf = &(d_out_buf[d_time_count][t_max_state_ndx]);
- }
-#if DO_PRINT_DEBUG_OUTPUT
- std::cout << "Found starting traceback ptr " << t_out_buf <<
- "; getting all " << d_block_size_bits << " bits per stream.\n";
-#endif
-// now we've got the starting traceback structure address;
-// check to make sure there is enough space in each output buffer
- size_t t_block_bit_ndx = d_block_size_bits;
- if ((t_next_out_buf_ndx > t_noutput_bytes) |
- ((t_next_out_buf_ndx == t_noutput_bytes) &
- (t_next_out_bit_shift != 0))) {
-// not enough space for all output bits;
-// find the number of extra bits to save
- size_t t_save_buf_ndx = t_next_out_buf_ndx - t_noutput_bytes;
- size_t t_n_extra_bits = ((t_save_buf_ndx * g_num_bits_per_byte) +
- t_next_out_bit_shift);
-// set the number of saved bits
- d_n_saved_bits = t_n_extra_bits;
-// remove the extra bits from the number to copy to the output buffer
- t_block_bit_ndx -= t_n_extra_bits;
-// find the actual output buf index, once we get there
- t_next_out_buf_ndx -= t_save_buf_ndx;
-#if DO_PRINT_DEBUG_OUTPUT
- std::cout << "Not enough output buffer space:\n" <<
- "len (o_b) = " << t_noutput_bytes << " ==> " <<
- t_n_extra_bits << " extra bit" <<
- (t_n_extra_bits != 1 ? "s" : "") << " == " <<
- t_save_buf_ndx << " Byte" <<
- (t_save_buf_ndx != 1 ? "s" : "") << ", " <<
- t_next_out_bit_shift << " bit" <<
- (t_next_out_bit_shift != 1 ? "s" : "") << "\n";
-#endif
-// zero each output buffers' bytes
- size_t t_n_zero = t_save_buf_ndx + (t_next_out_bit_shift ? 1 : 0);
-#if DO_PRINT_DEBUG_OUTPUT
- size_t t_n_out_bytes = ((d_block_size_bits / g_num_bits_per_byte) +
- ((d_block_size_bits % g_num_bits_per_byte) ? 1
: 0));
- std::cout << "Zeroing save buffer from for " << t_n_zero <<
- " Byte" << (t_n_zero != 1 ? "s" : "") << " (of " <<
- d_block_size_bits << " bit" <<
- (d_block_size_bits != 1 ? "s" : "") << " == " << t_n_out_bytes <<
- " Byte" << (t_n_out_bytes != 1 ? "s" : "") << ")\n";
-#endif
- for (size_t m = 0; m < d_n_code_inputs; m++)
- bzero (d_save_buffer[m], t_n_zero);
-// loop over all extra bits
- for (size_t n = t_n_extra_bits; n > 0; n--) {
-// first decrement the output bit & byte as necessary
- if (--t_next_out_bit_shift < 0) {
- t_next_out_bit_shift += g_num_bits_per_byte;
- t_save_buf_ndx--;
- }
-// get the encoder inputs to output
- size_t t_inputs = t_out_buf->d_inputs;
-// loop over all code inputs (decoder-outputs), 1 bit per stream
- for (size_t m = 0; m < d_n_code_inputs; m++) {
- d_save_buffer[m][t_save_buf_ndx] |=
- ((t_inputs & 1) << t_next_out_bit_shift);
- t_inputs >>= 1;
- }
- t_out_buf = t_out_buf->d_prev;
-#if DO_PRINT_DEBUG_OUTPUT_0
- std::cout << "Next traceback ptr " << t_out_buf << "\n";
-#endif
- }
-// at exit, "t_out_buf_ndx" should be == t_noutput_bytes, and
-// "t_out_bit_shift" should be 0; check these!
-#if DO_PRINT_DEBUG_OUTPUT
- std::cout << "n_o_b_ndx (" << t_next_out_buf_ndx << ") ?=? " <<
- "#o_B (" << t_noutput_bytes << ") & t_o_b_sh (" <<
- t_next_out_bit_shift << ") ?=? 0\n";
- assert (t_next_out_buf_ndx == t_noutput_bytes);
- assert (t_next_out_bit_shift == 0);
-#endif
- }
-// set the correct output buffer index and bit shift
- t_out_bit_shift = t_next_out_bit_shift;
- t_out_buf_ndx = t_next_out_buf_ndx;
-// copy any remaining bits looping backwards in bit-time
-// through the traceback trellis
- for (size_t n = t_block_bit_ndx; n > 0; n--) {
-// first decrement the output bit & byte as necessary
- if (--t_out_bit_shift < 0) {
- t_out_bit_shift += g_num_bits_per_byte;
- t_out_buf_ndx--;
- }
-// get the encoder inputs to output
- size_t t_inputs = t_out_buf->d_inputs;
-// loop over all code inputs (decoder-outputs), 1 bit per stream
- for (size_t m = 0; m < d_n_code_inputs; m++) {
- out_buf[m][t_out_buf_ndx] |= ((t_inputs & 1) << t_out_bit_shift);
- t_inputs >>= 1;
- }
- t_out_buf = t_out_buf->d_prev;
-#if DO_PRINT_DEBUG_OUTPUT_0
- std::cout << "Next traceback ptr " << t_out_buf << "\n";
-#endif
- }
-// set the next output byte and bit-shift
- t_out_bit_shift = t_next_out_bit_shift;
- t_out_buf_ndx = t_next_out_buf_ndx;
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Set FSM to fsm_dec_viterbi_init\n";
-#endif
- d_fsm_state = fsm_dec_viterbi_init;
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Exited fsm_dec_viterbi_output\n";
-#endif
- break;
- case (fsm_dec_viterbi_init):
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Entered fsm_dec_viterbi_init\n";
-#endif
-// this is called immediately (first input bit upon startup),
-// or after termination of a trellis.
+ case fsm_dec_viterbi_doing_input:
+ if (DO_PRINT_DEBUG_FSM) {
+ std::cout << "Starting FSM Decoder Viterbi Doing Input\n";
+ }
-// reset states to the 0'th one
- d_up_term_ndx = d_states_ndx = 0;
-// zero the metrics for those states
- zero_metrics (0);
-#if 0
-// might not need to do this; check and see after it works
-// reset up_term states and number so that there is 1 item, the "0" state.
- bzero (d_up_term_states_ndx[0], sizeof (size_t) * d_n_states);
- bzero (d_up_term_states_ndx[1], sizeof (size_t) * d_n_states);
-#else
- d_up_term_states_ndx[0][0] = 0;
-#endif
-// reset time count back to the start
- d_time_count = 0;
-#if 0
-// reset the traceback structures
-// might not need to do this; check and see after it works
- traceback_t_hdl t_out_bufs = d_out_buf;
- for (size_t n = d_n_traceback_els; n > 0; n--) {
- traceback_t_ptr t_out_buf = (*t_out_bufs++);
- for (size_t m = d_n_states; m > 0; m--, t_out_buf++) {
- t_out_buf->d_prev = NULL;
- t_out_buf->d_inputs = -1;
- }
- }
-#endif
-// set the fsm to "doing up"
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Set FSM to fsm_dec_viterbi_doing_up\n";
-#endif
- d_fsm_state = fsm_dec_viterbi_doing_up;
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Exited fsm_dec_viterbi_init\n";
-#endif
- break;
-// should never get here!
- default:
- assert (0);
-// done (switch) with FSM
+
+ if (DO_PRINT_DEBUG_FSM) {
+ std::cout << "Ending FSM Decoder Viterbi Doing Input\n";
}
-// done (while) there are inputs
- }
+ break;
-// consume all of the input items on all input streams
-// "ninput_items[]" doesn't seem to be reliable,
-// so compute this from the actual number of blocks processed
-#if DO_PRINT_DEBUG_EXIT
- std::cout << "Exiting FSM in state: " <<
- (d_fsm_state == fsm_dec_viterbi_init ? "init" :
- (d_fsm_state == fsm_dec_viterbi_doing_up ? "up" :
- (d_fsm_state == fsm_dec_viterbi_doing_middle ? "middle" :
- (d_fsm_state == fsm_dec_viterbi_doing_term ? "term" :
- (d_fsm_state == fsm_dec_viterbi_output ? "output" : "unknown"))))) <<
"\n" <<
- "Consuming " << t_in_buf_ndx <<
- " input items on each input stream (of " << t_ninput_items << ").\n";
-#endif
- consume_each (t_in_buf_ndx);
+ case (fsm_dec_viterbi_doing_term):
+ if (DO_PRINT_DEBUG_FSM) {
+ std::cout << "Starting FSM Decoder Viterbi Doing Term\n";
+ }
-// make sure the number of output items makes sense
-// t_out_buf_ndx always points to the current index
-// t_out_bit_shift always points to the next bit position to be written
- int t_leftover_bytes = t_out_buf_ndx % d_out_stream_el_size_bytes;
- int t_leftover_bits = ((t_leftover_bytes * g_num_bits_per_byte) +
- t_out_bit_shift);
- int t_noutput_items = noutput_items;
-#if DO_PRINT_DEBUG_EXIT
- std::cout << "Final o_b[" << t_out_buf_ndx << "][" <<
- t_out_bit_shift << "] of " << t_noutput_bytes <<
- ", el_size = " << d_out_stream_el_size_bytes <<
- ", lo_Bytes = " << t_leftover_bytes <<
- ", t_lo_bits = " << t_leftover_bits << "\n" <<
- "Desired # output items = " << noutput_items << "\n";
-#endif
- if (t_leftover_bits != 0) {
- // should never get here!
-#if 1
- assert (0);
-#else
- int t_ndx = t_out_buf_ndx - t_leftover_bytes;
- size_t t_n_copy = t_leftover_bytes + ((t_out_bit_shift != 0) ? 1 : 0);
- assert (t_n_copy <= d_out_stream_el_size_bytes);
-// copy the leftover into the save buffer
- for (size_t n = 0; n < d_n_code_inputs; n++) {
- bcopy (&(out_buf[n][t_ndx]), d_save_buffer[n], t_n_copy);
+ if (DO_PRINT_DEBUG_FSM) {
+ std::cout << "Ending FSM Decoder Viterbi Doing Term\n";
}
- t_noutput_items = t_ndx / d_out_stream_el_size_bytes;
- d_n_saved_bits = t_leftover_bits;
-#if DO_PRINT_DEBUG_EXIT
- std::cout << "Copied " << t_n_copy << " Byte" <<
- (t_n_copy != 1 ? "s" : "") << " from o_b[][" << t_ndx <<
- "] into each save buffer.\n" <<
- "Actual #output items = " << t_noutput_items <<
- ", # saved bit(s) = " << d_n_saved_bits << "\n";
-#endif
-#endif
+ break;
+ default:
+ assert (0);
}
-#endif
-
-#if DO_TIME_THOUGHPUT
- u_long d_t = end_timer (&t_tp);
-
- std::cout << "dec_blk_conv_soft_full: Completed " << t_ninput_items <<
- " bits in " << d_t << " usec => " <<
- 1e6*(((double)(t_ninput_items))/((double) d_t)) <<
- " b/s\n";
-#endif
-}
-
#if 0
+ if (DO_TIME_THOUGHPUT) {
+ u_long d_t = end_timer (&t_tp);
-void
-decoder_viterbi::encode_loop_up ()
-{
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Starting fsm_dec_viterbi_doing_up\n";
+ std::cout << "dec_blk_conv_soft_full: Completed " << t_ninput_items <<
+ " bits in " << d_t << " usec => " <<
+ 1e6*(((double)(t_ninput_items))/((double) d_t)) <<
+ " b/s\n";
+ }
#endif
-
- // set the number of up_down indices
-
- size_t t_n_up_down_ndx = 1 << (d_n_code_inputs *
- d_time_count);
-
-// stay in this state until the correct number of input symbols are
-// reached; exit also if we run out of input symbols to process
- while ((d_time_count < d_total_n_delays) &
- (t_in_buf_ndx < t_ninput_items)) {
-#if DO_PRINT_DEBUG_UP_0
- std::cout << "Doing 'while' loop:\n" <<
- "t_n_up_down_ndx = " << t_n_up_down_ndx << "\n" <<
- "d_time_count = " << d_time_count << "\n" <<
- "d_total_n_delays = " << d_total_n_delays << "\n" <<
- "t_in_buf_ndx = " << t_in_buf_ndx << "\n" <<
- "t_ninput_items = " << t_ninput_items << "\n";
-#endif
-// use the "from" states, loop over all inputs and compute the metric for
-// each & store it in the "to" state at the end of the connection.
-// no need to compare metrics yet, since none join into any given state
-
-#if 0
-// reset the "to" state's metrics
-// probably don't need to do this; try removing later
- reset_metrics (d_states_ndx ^ 1);
-#if DO_PRINT_DEBUG_UP
- std::cout << "Reset Metrics\n";
-#endif
-#endif
-
-// reset the state's index for each set of new inputs
- size_t* t_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx];
- size_t* t_next_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx ^ 1];
-// loop over all current stored "up" states
- for (size_t n = 0; n < t_n_up_down_ndx; n++) {
- size_t t_state_ndx = *t_state_ndx_ptr++;
-// get a pointer to this state's structure
- state_t_ptr t_state = &(d_states[d_states_ndx][t_state_ndx]);
-// get the connections for all inputs
- connection_t_ptr t_connection = t_state->d_connections;
-#if DO_PRINT_DEBUG_UP_0
- std::cout << "Looping over all 'up' states:\n" <<
- "n = " << n << "\n" <<
- "t_n_up_down_ndx = " << t_n_up_down_ndx << "\n" <<
- "d_states_ndx = " << d_states_ndx << "\n" <<
- "t_state_ndx = " << t_state_ndx << "\n" <<
- "d_n_input_combs = " << d_n_input_combinations << "\n" <<
- "t_state = " << t_state << "\n" <<
- "t_connection = " << t_connection << "\n";
-#endif
-// loop over all possible input values, 1 bit per input stream
- for (size_t q = 0; q < d_n_input_combinations; q++, t_connection++) {
-// find the "to" state for this connection
- state_t_ptr t_to_state = t_connection->d_to;
-// get the output bits for this connection
- float* t_output_bit = t_connection->d_output_bits;
-// start with this state's metric
- float t_metric = t_state->d_max_metric;
-#if DO_PRINT_DEBUG_UP_0
- std::cout <<
- "to state index = " << t_connection->d_to_ndx << "\n" <<
- "current metric = " << t_metric << "\n";
-#endif
- if (d_do_mux_inputs == true) {
-// if using mux'ed input streams, handle differently
- const float* t_in_buf = &(in_buf[0][t_in_buf_ndx]);
-// loop over all encoder-output values
- for (size_t r = d_n_code_outputs; r > 0; r--) {
-#if DO_PRINT_DEBUG_UP
- std::cout << "in_sym = " << *t_in_buf << ", code_out_bit = " <<
- *t_output_bit << " ==> metric -> ";
-#endif
- t_metric += ((*t_in_buf++) * (*t_output_bit++));
-#if DO_PRINT_DEBUG_UP
- std::cout << t_metric << "\n";
-#endif
- }
- } else {
-// loop over all encoder-output values
- for (size_t r = 0; r < d_n_code_outputs; r++) {
-#if DO_PRINT_DEBUG_UP
- std::cout << "in_sym = " << in_buf[r][t_in_buf_ndx] <<
- ", code_out_bit = " << *t_output_bit << " ==> metric -> ";
-#endif
- t_metric += (in_buf[r][t_in_buf_ndx] * (*t_output_bit++));
-#if DO_PRINT_DEBUG_UP
- std::cout << t_metric << "\n";
-#endif
- }
- }
-// get the "to" state index
- size_t t_to_ndx = t_connection->d_to_ndx;
-// store the metric in the "to" state; should not have been used before
- t_to_state->d_max_metric = t_metric;
-// add the "to" state index to the "up" state list
- *t_next_state_ndx_ptr++ = t_to_ndx;
-// update the traceback structure, depending on which variety it is
-// doing full trellis before decoding; use d_out_buf
-// simple: get the current state & output state
- traceback_t_ptr t_out_buf = &(d_out_buf[d_time_count]
- [t_state_ndx]);
- traceback_t_ptr t_next_out_buf = &(d_out_buf[d_time_count+1]
- [t_to_ndx]);
-#if DO_PRINT_DEBUG_UP_1
- std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n" <<
- "ndx[" << n << "] == " << t_state_ndx <<
- ", s[" << n2bs(t_state_ndx,t_state_print_bits) <<
- "]: max_ndx = " <<
- n2bs(t_state->d_max_state_ndx,t_state_print_bits) <<
- ", input = " << n2bs(q, d_n_code_inputs+1) <<
- ": " << t_next_out_buf << " => " << t_out_buf << "\n";
-#endif
-// and connect output to the current, set inputs on output
- t_next_out_buf->d_prev = t_out_buf;
- t_next_out_buf->d_inputs = q;
-// finished (for) this input value
- }
-// finished (for) this "up_term" state
- }
-// increment the in_buf index, depending on mux'ing or not
- t_in_buf_ndx += (d_do_mux_inputs == false) ? 1 : d_n_code_outputs;
-// increment the time counter
- d_time_count++;
-// update the number of "up_term" states
- d_up_term_ndx ^= 1;
-// increase the number of using states
- t_n_up_down_ndx <<= d_n_code_inputs;
-// change which d_states' index to use as starting
- d_states_ndx ^= 1;
-// finished (while) staying in this fsm state or not
- }
-// if reached the end of doing the "up" part of the trellis,
-// switch states into the middle
- if (d_time_count == d_total_n_delays) {
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Setting FSM to fsm_dec_viterbi_doing_middle\n";
-#endif
- d_fsm_state = fsm_dec_viterbi_doing_middle;
- }
-#if DO_PRINT_DEBUG_FSM
- std::cout << "Exited fsm_dec_viterbi_doing_up\n";
-#endif
}
-#endif
+
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -26,181 +26,164 @@
#include "decoder.h"
#include "encoder_convolutional.h"
-#if 0
-template<typename pdf_fcn_io_t>
-class code_metrics_decoder;
+const bool G_LIBECC_DECODE_FULL = true;
+const bool G_LIBECC_DECODE_PARTIAL = false;
-template<typename pdf_fcn_io_t>
-libecc_code_metrics_create_decoder
-(code_convolutional_trellis* trellis,
- code_metrics_table<pdf_fcn_io_t>* table = 0,
- int sample_precision = 0);
-
-
- // compute all output-bit combinations of the incoming symbols' metrics
-
- void compute_all_outputs (pdf_fcn_io_t* syms, std::vector<unsigned long>&
out);
- void compute_all_outputs (pdf_fcn_io_t* syms, std::vector<float>& out);
-
- size_t d_n_code_outputs;
- std::vector<unsigned long> in_l[2];
- std::vector<float> in_f[2];
-#endif
-
+template<typename computation_t>
class decoder_viterbi : public decoder
{
public:
/*!
- * \brief Decode the incoming metrics streams using the Viterbi algorithm.
+ * \brief Decode the incoming metrics streams using the Viterbi
+ * algorithm. The actual algorithm used here is similar to the "Lazy"
+ * method: instead of expanded all nodes for each incoming set of
+ * metrics, expand only the node with the minimum metric. In the
+ * worst case ("low" SNR), all nodes will be expanded - just like the
+ * standard Viterbi algorithm. In the best case ("high" SRN), one
+ * node per set of input metrics will be expanded.
*
- * input: streams of metrics, 2 streams per n_code_outputs - one each for
- * a 0- and 1-bit metric.
- *
- * output: streams of char, one stream per n_code_inputs, using only
- * the right-most justified bit as the single bit per output item.
- *
- * sample_precision: precision of the incoming metrics
- * if == 0, then use soft precision (32 bit float);
- * otherwise, use an integer up to 32 bits, already sign-extended
- * to the nearest power-of-2-sized type (char, short, long).
- *
- * l_encoder: pointer to an encoder class from which to determine the
- * trellis transitions (states and i/o bits).
+ * NOTE: This class is not instantiated directly, but instead through
+ * a call to "libecc_decoder_viterbi_create".
*/
- decoder_viterbi (int sample_precision,
- const encoder_convolutional* l_encoder);
+ // decoder_viterbi: instantiation method
+ //
+ // encoder: the encoder which was used to create the incoming data
+ //
+ // sample_precision: incoming data are metrics with the given precision:
+ // 0 : float
+ // 1 through 8: u_int8_t
+ // 9 through 16: u_int16_t
+ // 17 through 32: u_int32_t
+ //
+ // NOTE1: Any integer precision beyond 8 or so will provide marginal
+ // benefit to the decoding algorithm in terms of lower error rate
+ // for a given SNR.
+ //
+ // NOTE2: float precision is somewhat slower than integer precision;
+ // use integer whenever possible.
+ //
+ // full_or_partial: type of decoding to perform;
+ // full decoding: requires block coding, and decodes the whole
+ // block (plus any termination bits). Requires more memory than
+ // partial block, even though there is less bookkeeping for each
+ // output bit.
+ //
+ // partial decoding: works on block or stream data, and parses
+ // only a fixed number of input time-metrics before deciding each
+ // output time-bit. Requires less memory than full block
+ // decoding, but also more bookkeeping for each output bit.
+ //
+ // n_bits_before_decode: For partial decoding only; will be ignored
+ // for full block decoding. The number of time-metrics (code output
+ // bits) to process before deciding on an output bit.
+ // 0: use 5.3 constriant-length bits
+ // otherwise: use the number of bits provided
+ //
- virtual ~decoder_viterbi ();
+ decoder_viterbi (const encoder_convolutional* encoder,
+ u_int8_t sample_precision = 10,
+ bool full_or_partial = G_LIBECC_DECODE_PARTIAL,
+ u_int32_t n_bits_before_decode = 0);
+ virtual ~decoder_viterbi () {};
+
protected:
-/*
- * state_t: describes a given memory state
- *
- * d_connections: a pointer to an array of these structures
- * will be used to describes a given time-bit's memory state;
- * an entry will be referenced via "state_add_to", to find the
- * connections to the next time-bit memory states. There is
- * one entry per each input bit combination -> 2^#I connections in all.
- * e.g. [0] means the all 0 input;
- * [1] means that input #1 was 1 while all the others were 0;
- * [2] means that input #2 was 1, while all the others were 0;
- * [3] means that inputs #1 and #2 were 1, while the others were 0.
- *
- * d_max_metric: the maximum metric thus far for this state
- *
- * d_max_state: the state from which the maximum metric was attained
- *
- * d_max_input: the input bits from which the maximum metric was attained
- */
+ // reset the state trellis; requires that
+ // "d_n_state_trellis_time_bits" be set beforehand, and depends on
+ // the exact declaration of the trellis.
- typedef struct state_t {
- struct state_t* d_connections;
- float d_max_metric;
- int d_max_state_ndx;
- int d_max_input;
- } state_t, *state_t_ptr;
+ virtual void reset_state_trellis () = 0;
-/*
- * state_get_from(v,i,k): use to retrieve a given bit-memory state,
- * from the inputs:
- *
- * memory_t v: the value from which to retrieve the given state
- * size_t i: for which input stream (0 to #I-1)
- * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
- */
+ // expand_node: expand the provided node
- inline memory_t state_get_from (memory_t v,
- size_t i,
- size_t k)
- {return (((v)>>((i)*(k)))&((1<<(k))-1));};
+ void expand_node (void* node);
+ virtual void expand_node__input (void* node) = 0;
+ virtual void expand_node__term (void* node) = 0;
-/*
- * state_add_to(s,v,i,k): use to create a given bit-memory state,
- * from the inputs:
- *
- * memory_t s: the state value to modify
- * memory_t v: value to set the state to for this input
- * size_t i: for which input stream (0 to #I-1)
- * size_t k: the number of memory slots per input (e.g. 1+D^2 -> 2)
- */
+ // get the relative bit-time for the given node, to check for doing
+ // termination
- inline void state_add_to (memory_t s,
- memory_t v,
- size_t i,
- size_t k)
- {(s)|=(((v)&((1<<(k))-1))<<((i)*(k)));};
+ virtual size_t get_time (void* node) = 0;
-/*
- * fsm_dec_viterbi_t: finite state machine for the Viterbi decoder
- *
- * fsm_dec_viterbi_init: initialize for a new block / 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
- */
+ // add_node: add the provided out_note to the appropriate list,
+ // given its originating in_node and metric relative to that
+ // originating node
+ virtual void add_node (void* in_node,
+ void* out_node,
+ memory_t out_bits) = 0;
+
+ // get the next time slot to work with; will vary depending on the
+ // actual implementation
+
+ virtual size_t get_next_time (size_t in_time) = 0;
+
+ // check the given node for membership in the trellis
+
+ virtual void check_node (void** in_node) = 0;
+
+ // the init routine; for when a block is finished and things need to
+ // be reset
+
+ virtual void do_init ();
+
+ // fsm_dec_viterbi_t: finite state machine for the Viterbi decoder
+ //
+ // fsm_dec_viterbi_init: initialize for a new block / block; this is
+ // already done at instantiation, so do it only at the end of a
+ // block.
+ //
+ // fsm_dec_viterbi_doing_input: working on encoded inputs
+ //
+ // fsm_dec_viterbi_doing_term: working on encoded termination bits
+
enum fsm_dec_viterbi_t {
- fsm_dec_viterbi_init, fsm_dec_viterbi_doing_up,
- fsm_dec_viterbi_doing_middle, fsm_dec_viterbi_doing_term
+ fsm_dec_viterbi_init, fsm_dec_viterbi_doing_input,
+ fsm_dec_viterbi_doing_term
};
virtual void decode_private ();
#if 0
virtual void decode_loop (size_t* which_counter, size_t how_many);
#endif
- virtual void get_next_inputs () {
- d_in_buf->read_items ((void*)(&(d_current_inputs[0])));
- d_in_buf->increment_indices ();
- };
+ virtual void get_next_inputs (size_t time_ndx = 0) = 0;
virtual void write_output_bits () {
d_out_buf->write_items ((void*)(&(d_current_outputs[0])));
d_out_buf->increment_indices ();
};
- void encode_loop_up ();
-
- virtual void update_traceback__up (size_t from_state_ndx,
- size_t to_state_ndx,
- size_t l_input) = 0;
- virtual void update_traceback__middle () = 0;
- virtual void update_traceback__term () = 0;
-
- void reset_metrics (u_char which);
- void zero_metrics (u_char which);
-
encoder_convolutional* d_encoder;
code_convolutional_trellis* d_trellis;
fsm_dec_viterbi_t d_fsm_state;
- size_t d_time_count, d_n_total_inputs_per_stream;
+ size_t d_time_count, d_total_n_inputs_per_stream;
size_t d_n_saved_bits, d_n_saved_bits_start_ndx, d_n_traceback_els;
- size_t d_n_states, d_n_input_combinations, d_total_n_delays;
- size_t d_states_ndx, d_up_term_ndx;
- bool d_do_termination;
+ size_t d_n_states, d_n_input_combinations, d_n_bits_to_term;
+ size_t d_states_ndx, d_total_n_nodes_to_alloc;
+ size_t d_n_code_outputs, d_n_code_inputs;
+ size_t d_n_state_trellis_time_bits, d_n_bits_before_decode;
+ bool d_do_termination, d_do_streaming, d_do_full_or_partial;
+
+ // for termination, need to keep around the current and next term
+ // states, so-as to be able to quicly lookup the correct inputs to
+ // terminate the trellis for the given state
+
+ u_int8_t d_which_term;
+ std::vector<memory_t> d_term_states_ndx[2];
+ size_t d_term_ndx[2];
+ size_t d_n_term_bits;
+
#if 1
- state_t_ptr d_states[2];
- size_t* d_up_term_states_ndx[2];
char **d_save_buffer;
#else
- std::vector<state_t> d_states[2];
- std::vector<size_t> d_up_term_states_ndx[2];
std::vector<char **> d_save_buffer; ???
#endif
- // "inputs" are the current input symbols as soft-floats, to be
- // converted to metrics internally
+ // "outputs" are the current output bits,
+ // in the LSB (&1) of each "u_int8_t"
- std::vector<float> d_current_inputs;
-
- // "outputs" are the current output bits, in the LSB (&1) of each "char"
-
- std::vector<char> d_current_outputs;
+ std::vector<u_int8_t> d_current_outputs;
};
#endif /* INCLUDED_DECODER_VITERBI_H */
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.cc
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.h
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.cc
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,305 @@
+/* -*- 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 <decoder_viterbi_lazy.h>
+#include <assert.h>
+#include <iostream>
+
+#define DO_TIME_THOUGHPUT 0
+#define DO_PRINT_DEBUG 0
+#define DO_PRINT_DEBUG_VARS 0
+#define DO_PRINT_DEBUG_FSM 0
+
+#include <mld/mld_timer.h>
+#include <mld/n2bs.h>
+
+decoder_viterbi_lazy::decoder_viterbi_lazy
+(const encoder_convolutional* encoder,
+ u_int8_t sample_precision,
+ bool full_or_partial,
+ u_int32_t n_bits_before_decode) :
+ decoder_viterbi<computation_t> (encoder,
+ sample_precision,
+ full_or_partial,
+ n_bits_before_decode)
+{
+ if (sample_precision == 0) {
+ std::cerr << "decoder_viterbi_lazy:: Error: The Lazy Viterbi Decoder "
+ " must use integer precision for the metrics.\n";
+ assert (0);
+ }
+
+ // set up the nodes
+
+ d_nodes.resize (d_total_n_nodes_to_alloc);
+
+ // set up the shadow heads ... depends on the sample precision
+
+ d_n_shadow_heads = (1 << sample_precision) * d_n_code_outputs;
+
+ // set up so that the trellis' init state contains the first node,
+ // in all the various structures
+
+ d_current_shadow_head_ndx = 0;
+ node_dll_t_ptr t_node = d_nodes.checkout ();
+ t_node->d_item.d_this_state = d_encoder->start_memory_state ();
+ add_node (0, t_node, 0);
+}
+
+void
+decoder_viterbi_lazy::reset_state_trellis
+()
+{
+ // reset the state trellis structures
+
+ // resize the first dimension (time)
+
+ d_state_trellis.resize (d_n_state_trellis_time_bits);
+
+ // resize all second dimensions (# of states)
+
+ for (size_t m = 0; m < d_n_state_trellis_time_bits; m++)
+ d_state_trellis[m].resize (d_n_states);
+}
+
+void
+decoder_viterbi_lazy::expand_node__input
+(void* node)
+{
+ // given the input node, expand it out per the trellis
+
+ node_dll_t_ptr in_node_dll = (node_dll_t_ptr) node;
+ node_t_ptr in_node = &(in_node_dll->d_item);
+ memory_t in_state = in_node->d_this_state;
+ size_t in_time = in_node->d_this_time;
+ size_t out_time = get_next_time (in_time);
+
+ for (memory_t m = 0; m < d_n_input_combinations; m++) {
+ // get an unused node to add
+
+ node_dll_t_ptr t_add_node_dll = d_nodes.checkout ();
+ node_t_ptr t_add_node = &(t_add_node_dll->d_item);
+
+ // and set it's variables
+
+ t_add_node->d_previous_node = in_node;
+ t_add_node->d_inputs = m;
+ t_add_node->d_this_state = in_state; // this will be updated by the lookup
+ t_add_node->d_this_time = out_time;
+
+ // using the trellis, find the output state and bits
+
+ memory_t out_bits = 0;
+ d_trellis->encode_lookup (t_add_node->d_this_state,
+ (const memory_t) m, out_bits);
+
+ // add the new node to the trellis or shadow list, with the
+ // relative metric provided by its branch
+
+ add_node (node, (void*) t_add_node_dll, out_bits);
+ }
+}
+
+void
+decoder_viterbi_lazy::expand_node__term
+(void* node)
+{
+ // given the input node, expand it out per the trellis
+
+ node_dll_t_ptr in_node_dll = (node_dll_t_ptr) node;
+ node_t_ptr in_node = &(in_node_dll->d_item);
+ memory_t in_state = in_node->d_this_state;
+ size_t in_time = in_node->d_this_time;
+ size_t out_time = get_next_time (in_time);
+
+ // get an unused node to add
+
+ node_dll_t_ptr t_add_node_dll = d_nodes.checkout ();
+ node_t_ptr t_add_node = &(t_add_node_dll->d_item);
+
+ // and set it's variables
+
+ t_add_node->d_previous_node = in_node;
+ t_add_node->d_this_state = in_state; // this will be updated by the lookup
+ t_add_node->d_this_time = out_time;
+
+ // get the termination inputs for this state and term bit #
+
+ memory_t term_start_state = d_term_states_ndx[d_which_term][in_state];
+ memory_t t_term_inputs = t_add_node->d_inputs =
+ d_trellis->get_termination_inputs (term_start_state, d_n_term_bits);
+
+ // using the trellis, find the output state and bits
+
+ memory_t out_bits = 0;
+ d_trellis->encode_lookup (term_start_state,
+ (const memory_t) t_term_inputs,
+ out_bits);
+
+ // add the new node to the trellis or shadow list, with the
+ // relative metric provided by its branch
+
+ add_node (node, (void*) t_add_node_dll, out_bits);
+}
+
+void
+decoder_viterbi_lazy::add_node
+(void* in_node,
+ void* out_node,
+ memory_t out_bits)
+{
+ // add the provided note to the trellis or shadow list, as
+ // appropriate for the particular implementation: for the standard
+ // viterbi decoder, this means the trellis.
+
+ size_t relative_metric = 0;
+
+ if (in_node) {
+ node_dll_t_ptr in_node_dll = (node_dll_t_ptr) in_node;
+ size_t in_time = in_node_dll->d_item.d_this_time;
+
+ // metrics are relative to the current shadow head index
+
+ relative_metric = (size_t) d_branch_metrics[in_time][out_bits];
+ }
+
+ size_t which_head = d_current_shadow_head_ndx + relative_metric;
+
+ // wrap around if necessary
+
+ if (which_head >= d_n_shadow_heads)
+ which_head -= d_n_shadow_heads;
+
+ // add to the computed shadow head's list
+
+ shadow_head_t& t_head = d_shadow_heads[which_head];
+ shadow_node_dll_t_ptr t_shadow_node_dll = d_shadow_nodes.checkout ();
+ shadow_node_t_ptr t_list_node = &(t_shadow_node_dll->d_item);
+ t_list_node->d_node = (node_dll_t_ptr) out_node;
+
+ if ((t_head.d_n_items)++ == 0) {
+ // nothing in this list yet; start it
+ t_head.d_head = t_head.d_tail = t_shadow_node_dll;
+ } else {
+ // list is active; add to the tail
+ t_head.d_tail->d_next = t_shadow_node_dll;
+ t_head.d_tail = t_shadow_node_dll;
+ }
+}
+
+void
+decoder_viterbi_lazy::check_node
+(void** node)
+{
+ node_dll_t_ptr in_node_dll = (node_dll_t_ptr)(*node);
+ node_t_ptr in_node = &(in_node_dll->d_item);
+
+ // check to see if this node's slot is already occupied
+
+ if (d_state_trellis[in_node->d_this_time][in_node->d_this_state] == 0) {
+
+ // no: then fill it, and return this node
+
+ d_state_trellis[in_node->d_this_time][in_node->d_this_state] =
+ in_node;
+
+ } else {
+
+ // yes: release this node from use; make it available for re-use
+
+ d_nodes.release (in_node_dll);
+
+ // reset the (referenced) pointer to 0
+
+ *node = 0;
+ }
+}
+
+void
+decoder_viterbi_lazy::do_init
+()
+{
+ decoder_viterbi<computation_t>::do_init ();
+
+ // reset the nodes, shadow heads, trellis
+
+ reset_shadow_nodes ();
+ d_nodes.reset ();
+ reset_state_trellis ();
+
+ // reset the max time index
+
+ d_max_time_ndx = 0;
+}
+
+node_dll_t_ptr
+decoder_viterbi_lazy::find_minimum_metric_node
+()
+{
+ // start with the current shadow head index, looking for any non-0
+ // heads in the shadow_heads list; wrap around as needed since the
+ // list is relative to the current head index. When a non-0 entry
+ // is found, pop off the head, then check to make sure it's valid.
+
+ node_dll_t_ptr node_dll = 0;
+
+ while (node_dll == 0) {
+
+ // find the next used shadow head
+
+ while (d_shadow_heads[d_current_shadow_head_ndx].d_head == 0)
+ if (++d_current_shadow_head_ndx > d_n_shadow_heads)
+ d_current_shadow_head_ndx = 0;
+
+ // get the head, list node, and node
+
+ shadow_head_t& t_head = d_shadow_heads[d_current_shadow_head_ndx];
+ shadow_node_dll_t_ptr list_node_dll = t_head.d_head;
+ shadow_node_t_ptr list_node = &(list_node_dll->d_item);
+ node_dll = list_node->d_node;
+
+ // remove this shadow node from this head
+
+ if (--(t_head.d_n_items) == 0) {
+ // only item; 0 everything
+ t_head.d_head = t_head.d_tail = 0;
+ } else {
+ // more than one item; reset the head to the next item
+ t_head.d_head = list_node_dll->d_item.d_next;
+ list_node_dll->d_item.d_next = 0;
+ }
+
+ // release the shadow DLL enclosure for reuse
+
+ d_shadow_nodes.release (list_node_dll);
+
+ // check the node for membership in the trellis
+
+ check_node ((void**)(&node_dll));
+ }
+
+ return (node_dll);
+}
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.h
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,215 @@
+/* -*- 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_DECODER_VITERBI_LAZY_H
+#define INCLUDED_DECODER_VITERBI_LAZY_H
+
+#include "decoder_viterbi.h"
+#include "doubly_linked_list.h"
+
+typedef unsigned long computation_t;
+
+// a node is an element in the state trellis, which gets compared
+// with on each iteration of inputs it contains the current best
+// metric for this node, as well as the state and inputs which
+// achieved this best metric. This single structure handles
+// everything, from keeping the computed metrics to the (basic)
+// traceback. For partial decoding, YA structure is desired to do
+// accounting for how many current paths are in each time slot and such.
+
+typedef struct node {
+ struct node* d_previous_node;
+ memory_t d_inputs;
+ memory_t d_this_state;
+ size_t d_this_time;
+} node_t, *node_t_ptr;
+
+typedef struct dll<node_t> node_dll_t, *node_dll_t_ptr;
+
+class decoder_viterbi_lazy : public decoder_viterbi<computation_t>
+{
+public:
+/*!
+ * \brief Decode the incoming metrics streams using the Viterbi
+ * algorithm. The actual algorithm used here is the "Lazy" method:
+ * instead of expanded all nodes for each incoming set of metrics,
+ * expand only the node with the minimum metric. In the worst case
+ * ("low" SNR), all nodes will be expanded - just like the standard
+ * Viterbi algorithm. In the best case ("high" SRN), one node per set
+ * of input metrics will be expanded.
+ *
+ * Note that the Lazy method requires the use of integer metrics.
+ */
+
+ // decoder_viterbi_lazy: instantiation method
+ //
+ // encoder: the encoder which was used to create the incoming data
+ //
+ // sample_precision: incoming data are metrics with the given precision:
+ // 1 through 8: u_int8_t
+ // 9 through 16: u_int16_t
+ // 17 through 32: u_int32_t
+ //
+ // NOTE: Any integer precision beyond 8 or so will provide marginal
+ // benefit to the decoding algorithm in terms of lower error rate
+ // for a given SNR.
+ //
+ // full_or_partial: type of decoding to perform;
+ // full decoding: requires block coding, and decodes the whole
+ // block (plus any termination bits). Requires more memory than
+ // partial block, even though there is less bookkeeping for each
+ // output bit.
+ //
+ // partial decoding: works on block or stream data, and parses
+ // only a fixed number of input time-metrics before deciding each
+ // output time-bit. Requires less memory than full block
+ // decoding, but also more bookkeeping for each output bit.
+ //
+ // n_bits_before_decode: For partial decoding only; will be ignored
+ // for full block decoding. The number of time-metrics (code output
+ // bits) to process before deciding on an output bit.
+ // 0: use 5.3 constriant-length bits
+ // otherwise: use the number of bits provided
+ //
+
+ decoder_viterbi_lazy (const encoder_convolutional* encoder,
+ u_int8_t sample_precision = 10,
+ bool full_or_partial = G_LIBECC_DECODE_PARTIAL,
+ u_int32_t n_bits_before_decode = 0);
+
+ virtual ~decoder_viterbi_lazy () {};
+
+protected:
+ // the state trellis is a two dimensional "matrix", where the first
+ // dimension is the "time", and the second is a state node entry.
+
+ std::vector<std::vector<node_t_ptr> > d_state_trellis;
+
+ doubly_linked_list<node_t> d_nodes;
+
+ // a shadow_node is a doubly linked list of the current nodes which
+ // have not been accepted into the actual state trellis structure.
+
+ struct shadow_node;
+ doubly_linked_list<struct shadow_node> d_shadow_nodes;
+ typedef struct dll<struct shadow_node> shadow_node_dll_t,
+ *shadow_node_dll_t_ptr;
+
+ typedef struct shadow_node {
+ shadow_node_dll_t_ptr d_next;
+ node_dll_t_ptr d_node;
+ } shadow_node_t, *shadow_node_t_ptr;
+
+ // the shadow_head contains the head and tail of the linked list of
+ // shadow_node's, in order to quickly find and move items around.
+
+ typedef struct shadow_head {
+ shadow_node_dll_t_ptr d_head, d_tail;
+ size_t d_n_items;
+ } shadow_head_t, *shadow_head_t_ptr;
+
+ std::vector<shadow_head_t> d_shadow_heads;
+
+ // "branch_metrics" are the converted metrics for each branch,
+ // ordered as a two dimensional "matrix". The first dimension is
+ // "time", and the second is the combined output number. The first
+ // dimension varies depending on which type of processing is taking
+ // place: full or partial. For the former, there need to be
+ // (d_block_size_bits + any termination bit) # of time entries. For
+ // the latter, the user defines how many time bits to keep. All of
+ // these branch metrics must be kept around because of the way in
+ // which the "lazy" style Viterbi decoder jumps back and forth in time.
+
+ std::vector<std::vector<computation_t> > d_branch_metrics;
+
+ // reset_shadow_nodes: reset (or setup, same difference) the shadow
+ // nodes for the desired # of pre-allocated list items as found in
+ // d_n_shadow_heads.
+
+ inline void reset_shadow_nodes ()
+ {d_shadow_heads.resize (d_n_shadow_heads);};
+
+ // find_minimum_metric_node: find the minimum metric node; this can
+ // be implemented differently for other decoding methods
+
+ node_dll_t_ptr find_minimum_metric_node ();
+
+ // reset the state trellis; requires that
+ // "d_n_state_trellis_time_bits" be set beforehand, and depends on
+ // the exact declaration of the trellis.
+
+ virtual void reset_state_trellis ();
+
+ // expand_node: expand the provided node, for where the given
+ // to-be-encoded bits came from (input or termination)
+
+ virtual void expand_node__input (void* node);
+ virtual void expand_node__term (void* node);
+
+ // get the relative bit-time for the given node,
+ // to check for doing termination
+
+ inline virtual size_t get_time (void* node) {
+ node_dll_t_ptr node_dll = (node_dll_t_ptr) node;
+ return (node_dll->d_item.d_this_time);
+ };
+
+ // add_node: add the provided out_note to the appropriate list,
+ // given its originating in_node and metric relative to that
+ // originating node
+
+ virtual void add_node (void* in_node,
+ void* out_node,
+ memory_t out_bits);
+
+ // get the next time slot to work with; must check for loop-around
+ // for partial decoding
+
+ inline virtual size_t get_next_time (size_t in_time) {
+ if (++in_time > d_n_state_trellis_time_bits)
+ in_time = 0;
+ return (in_time);
+ };
+
+ // check the given node for membership in the trellis
+
+ virtual void check_node (void** in_node);
+
+ // the init routine; for when a block is finished and things need to
+ // be reset
+
+ virtual void do_init ();
+
+ // get the next inputs; for the lazy method, those are stored
+
+ virtual void get_next_inputs (size_t time_ndx = 0) {
+ if (time_ndx <= d_max_time_ndx)
+ return;
+ d_in_buf->read_items ((void*)(&(d_branch_metrics[time_ndx])));
+ d_in_buf->increment_indices ();
+ };
+
+ size_t d_max_time_ndx, d_n_shadow_heads;
+ size_t d_current_shadow_head_ndx;
+};
+
+#endif /* INCLUDED_DECODER_VITERBI_LAZY_H */
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy_alt.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy_alt.cc
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_lazy_alt.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,97 @@
+/* -*- 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 <decoder_viterbi_lazy_alt.h>
+#include <assert.h>
+#include <iostream>
+
+#define DO_PRINT_DEBUG 0
+
+#include <mld/n2bs.h>
+
+decoder_viterbi_lazy_alt::decoder_viterbi_lazy_alt
+(const encoder_convolutional* encoder,
+ u_int8_t sample_precision,
+ bool full_or_partial,
+ u_int32_t n_bits_before_decode) :
+ decoder_viterbi_lazy (encoder,
+ sample_precision,
+ full_or_partial,
+ n_bits_before_decode)
+{
+ d_is_shadow.resize ();
+}
+
+void
+decoder_viterbi_lazy_alt::do_init
+()
+{
+ // do the inherited init
+
+ decoder_viterbi_lazy::do_init ();
+
+ // set all of the trellis nodes "is_shadow" to false
+
+ for (size_t m = 0; m < d_n_state_trellis_time_bits; m++)
+ d_is_shadow[m].assign (d_n_states, true);
+}
+
+void
+decoder_viterbi_lazy::add_node
+(void* node,
+ computation_t relative_metric)
+{
+ node_dll_t_ptr in_node_dll = (node_dll_t_ptr) node;
+ node_t_ptr in_node = in_node_dll->d_item;
+
+ // check to see if this node is a shadow node or not
+
+ if (d_is_shadow[in_node->d_this_time][in_node->d_this_state] == false) {
+ // node has already been accepted as a minimum; ignore the provided node
+
+ d_nodes.release (in_node_dll);
+
+ // reset the (referenced) pointer to 0
+
+ node = 0;
+ } else {
+
+
+ }
+}
+
+void
+decoder_viterbi_lazy_alt::check_node
+(void*& node)
+{
+ node_dll_t_ptr in_node_dll = (node_dll_t_ptr) node;
+ node_t_ptr in_node = in_node_dll->d_item;
+
+ // node is already in place;
+ // just set its "is_shadow" property to false
+
+ d_is_shadow[in_node->d_this_time][in_node->d_this_state] = false;
+}
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.cc
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,14 @@
+template<typename computation_t>
+void
+decoder_viterbi<computation_t>::add_node
+(node_dll_t_ptr node,
+ memory_t out_bits)
+{
+ // add the provided note to the trellis or shadow list, as
+ // appropriate for the particular implementation: for the standard
+ // viterbi decoder, this means the trellis.
+
+ computation_t relative_metric = d_branch_metrics[out_bits];
+
+
+}
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.h
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_standard.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,145 @@
+/* -*- 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_DECODER_VITERBI_STANDARD_H
+#define INCLUDED_DECODER_VITERBI_STANDARD_H
+
+#include "decoder_viterbi.h"
+
+template<typename computation_t>
+class decoder_viterbi : public decoder
+{
+public:
+/*!
+ * \brief Decode the incoming metrics streams using the Viterbi
+ * algorithm. The actual algorithm used here is similar to the "Lazy"
+ * method: instead of expanded all nodes for each incoming set of
+ * metrics, expand only the node with the minimum metric. In the
+ * worst case ("low" SNR), all nodes will be expanded - just like the
+ * standard Viterbi algorithm. In the best case ("high" SRN), one
+ * node per set of input metrics will be expanded.
+ *
+ * NOTE: This class is not instantiated directly, but instead through
+ * a call to "libecc_decoder_viterbi_create".
+ */
+
+ // decoder_viterbi: instantiation method
+ //
+ // encoder: the encoder which was used to create the incoming data
+ //
+ // sample_precision: incoming data are metrics with the given precision:
+ // 0 : float
+ // 1 through 8: u_int8_t
+ // 9 through 16: u_int16_t
+ // 17 through 32: u_int32_t
+ //
+ // NOTE1: Any integer precision beyond 8 or so will provide marginal
+ // benefit to the decoding algorithm in terms of lower error rate
+ // for a given SNR.
+ //
+ // NOTE2: float precision is somewhat slower than integer precision;
+ // use integer whenever possible.
+ //
+ // full_or_partial: type of decoding to perform;
+ // full decoding: requires block coding, and decodes the whole
+ // block (plus any termination bits). Requires more memory than
+ // partial block, even though there is less bookkeeping for each
+ // output bit.
+ //
+ // partial decoding: works on block or stream data, and parses
+ // only a fixed number of input time-metrics before deciding each
+ // output time-bit. Requires less memory than full block
+ // decoding, but also more bookkeeping for each output bit.
+ //
+ // n_bits_before_decode: For partial decoding only; will be ignored
+ // for full block decoding. The number of time-metrics (code output
+ // bits) to process before deciding on an output bit.
+ // 0: use 5.3 constriant-length bits
+ // otherwise: use the number of bits provided
+ //
+
+ decoder_viterbi (const encoder_convolutional* encoder,
+ u_int8_t sample_precision = 10,
+ bool full_or_partial = G_LIBECC_DECODE_PARTIAL,
+ u_int32_t n_bits_before_decode = 0);
+
+ virtual ~decoder_viterbi () {};
+
+protected:
+ // a node is an element in the state trellis, which gets compared
+ // with on each iteration of inputs it contains the current best
+ // metric for this node, as well as the state and inputs which
+ // achieved this best metric. This single structure handles
+ // everything, from keeping the computed metrics to the (basic)
+ // traceback. For partial decoding, YA structure is desired to do
+ // accounting for how many current paths are in each time slot and such.
+
+ typedef struct node {
+ struct node* d_previous_node;
+ computation_t d_metric;
+ memory_t d_inputs;
+ } node_t, *node_t_ptr;
+
+ // the state trellis is a two dimensional "matrix", where the first
+ // dimension is the "time", and the second is a state node entry.
+
+ std::vector<std::vector<node_t> > d_state_trellis;
+
+ // "branch_metrics" are the converted metrics for each branch for a
+ // given bit-time period.
+
+ std::vector<computation_t> d_branch_metrics;
+
+ // find_minimum_metric_node: find the minimum metric node; this can
+ // be implemented differently for other decoding methods
+
+ node_dll_t_ptr find_minimum_metric_node ();
+
+ // expand_node: expand the starting node referred to by the pair
+ // (bit_time, start_state_ndx), given the branch metrics for that
+ // bit_time.
+
+ void expand_node (node_dll_t_ptr in_node_dll);
+ void expand_node__input (node_dll_t_ptr in_node_dll);
+ void expand_node__term (node_dll_t_ptr in_node_dll);
+
+ // add_node: add the provided note to the trellis or shadow list, as
+ // appropriate for the particular implementation
+
+ virtual void add_node (node_dll_t_ptr in_node_dll,
+ computation_t relative_metric);
+
+ // reset the state trellis; requires that
+ // "d_n_state_trellis_time_bits" be set beforehand.
+
+ void reset_state_trellis ();
+
+ // get the next time slot to work with
+
+ virtual size_t get_next_time (size_t in_time);
+
+ // check the given node for membership in the trellis
+
+ virtual void check_node (node_dll_t_ptr& node_dll);
+};
+
+#endif /* INCLUDED_DECODER_VITERBI_STANDARD_H */
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/doubly_linked_list.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/doubly_linked_list.h
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/doubly_linked_list.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,123 @@
+/* -*- 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_DOUBLY_LINKED_LIST_H
+#define INCLUDED_DOUBLY_LINKED_LIST_H
+
+#include <assert.h>
+#include <iostream>
+
+template<typename item_t>
+struct dll {
+ struct dll* d_next;
+ struct dll* d_prev;
+ item_t d_item;
+};
+
+template<typename item_t>
+class doubly_linked_list
+{
+public:
+ typedef struct dll<item_t> dll_t, *dll_t_ptr;
+
+ inline doubly_linked_list () {};
+
+ inline ~doubly_linked_list () {
+ d_items.resize (0);
+ };
+
+ inline size_t n_in_use () {return (d_n_in_use);};
+ inline size_t n_available () {return (d_n_available);};
+ inline void reset () {resize (d_n_alloced);};
+
+ dll_t_ptr checkout () {
+ if (d_n_available == 0) {
+ std::cerr << "doubly_linked_list::checkout: Error: "
+ "no more items available.\n";
+ assert (0);
+ }
+ d_n_in_use++;
+ dll_t_ptr t_node = d_items_available;
+ if (--d_n_available == 0) {
+ d_items_available = 0;
+ } else {
+ dll_t_ptr t_next = t_node->d_next;
+ dll_t_ptr t_prev = t_node->d_prev;
+ t_next->d_prev = t_prev;
+ t_prev->d_next = t_next;
+ }
+ if (d_items_in_use == 0) {
+ d_items_in_use = t_node->d_prev = t_node->d_next = t_node;
+ } else {
+ dll_t_ptr t_next = t_node->d_next = d_items_in_use->d_next;
+ dll_t_ptr t_prev = t_node->d_prev = d_items_in_use->d_prev;
+ t_prev->d_next = t_next->d_prev = t_node;
+ }
+ return (t_node);
+ };
+
+ void release (dll_t_ptr t_node) {
+ if (d_n_in_use == d_n_alloced)
+ return;
+ d_n_available++;
+ if (--d_n_in_use == 0) {
+ d_items_in_use = 0;
+ } else {
+ dll_t_ptr t_next = t_node->d_next;
+ dll_t_ptr t_prev = t_node->d_prev;
+ t_next->d_prev = t_prev;
+ t_prev->d_next = t_next;
+ }
+ if (d_items_available == 0) {
+ d_items_available = t_node->d_prev = t_node->d_next = t_node;
+ } else {
+ dll_t_ptr t_next = t_node->d_next = d_items_available->d_next;
+ dll_t_ptr t_prev = t_node->d_prev = d_items_available->d_prev;
+ t_prev->d_next = t_next->d_prev = t_node;
+ }
+ };
+
+ inline dll_t& operator[] (size_t n) {return (d_items[n]);};
+
+ void resize (size_t n_to_alloc) {
+ d_items.resize (n_to_alloc);
+ d_n_alloced = d_n_available = n_to_alloc;
+ d_n_in_use = 0;
+ d_items_in_use = 0;
+ dll_t_ptr current = d_items_available = &(d_items[0]);
+ for (size_t m = 1; m < d_n_alloced; m++) {
+ dll_t_ptr next = &(d_items[m]);
+ current->d_next = next;
+ next->d_prev = current;
+ }
+ d_items_available->d_prev = current;
+ current->d_next = d_items_available;
+ };
+
+protected:
+ size_t d_n_alloced, d_n_in_use, d_n_available;
+ std::vector<dll_t> d_items;
+ dll_t_ptr d_items_in_use;
+ dll_t_ptr d_items_available;
+};
+
+#endif /* INCLUDED_DOUBLY_LINKED_LIST_H */
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -94,7 +94,7 @@
start_memory_state &= t_mask;
}
- d_init_state = start_memory_state;
+ d_start_memory_state = start_memory_state;
// reset the inputs and outputs, both to get the correct size() and
// for the sake of zeroing them out.
@@ -133,7 +133,7 @@
// copy the init states to the current memory
- d_memory = d_init_state;
+ d_memory = d_start_memory_state;
// if not doing streaming, things to do; else nothing more do
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h
2006-08-21 16:48:00 UTC (rev 3362)
@@ -159,6 +159,9 @@
inline const size_t total_n_delays () {return (d_total_n_delays);};
inline const size_t n_bits_to_term () {return (d_n_bits_to_term);};
inline const code_convolutional_trellis* trellis() {return (d_trellis);};
+ inline const memory_t start_memory_state () {return (d_start_memory_state);};
+ inline const memory_t end_memory_state () {
+ return (d_trellis->end_memory_state());};
protected:
/*
@@ -262,10 +265,10 @@
code_convolutional_trellis* d_trellis;
- // "init_states" are the user-provided init states,
- // interpreted w/r.t. the actual trellis;
+ // "start_memory_state" is the user-provided starting memory
+ // state, interpreted w/r.t. the actual trellis;
- memory_t d_init_state;
+ memory_t d_start_memory_state;
// "term_state" is the ending state before termination, used by the
// trellis to determine the correct input-bit sequences needed to
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc
2006-08-21 16:48:00 UTC (rev 3362)
@@ -270,7 +270,7 @@
// start state is 0, same feedback, no termination
const static int t2_code_generator[] = {1, 0, 0, 1, 5, 6};
-const static size_t t2_code_feedback[] = {0, 0, 0, 0, 7, 7};
+const static int t2_code_feedback[] = {0, 0, 0, 0, 7, 7};
const static int t2_encode_soai = 1;
const static char t2_in_0[] =
@@ -1285,7 +1285,7 @@
// start state is 0, same feedback, no termination
const static int t25_code_generator[] = {1, 0, 0, 1, 5, 6};
-const static size_t t25_code_feedback[] = {0, 0, 0, 0, 7, 7};
+const static int t25_code_feedback[] = {0, 0, 0, 0, 7, 7};
const static int t25_encode_soai = 1;
const static char t25_in_0[] =
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/lib/qa_ecc.py
Modified:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/Makefile.am
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/Makefile.am
2006-08-21 01:02:37 UTC (rev 3361)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/Makefile.am
2006-08-21 16:48:00 UTC (rev 3362)
@@ -23,8 +23,7 @@
EXTRA_DIST = run_tests.in
-# Disable qa checks due to non-standard directory structure (eb)
-# TESTS = run_tests
+TESTS = run_tests
noinst_PYTHON = qa_test_coding_1.py qa_test_coding_2.py
Added:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_ecc.py
===================================================================
---
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_ecc.py
(rev 0)
+++
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_ecc.py
2006-08-21 16:48:00 UTC (rev 3362)
@@ -0,0 +1,42 @@
+#!/usr/bin/env python
+#
+# 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.
+#
+
+from gnuradio import gr, gr_unittest
+# the local library must be imported from local directory so that make
+# check can run before installation
+import ecc
+
+class qa_ecc (gr_unittest.TestCase):
+
+ def setUp (self):
+ self.fg = gr.flow_graph ()
+
+ def tearDown (self):
+ self.fg = None
+
+ def test_000_nop (self):
+ """Just see if we can import the module...
+ They may not have drivers, etc. Don't try to run anything"""
+ pass
+
+if __name__ == '__main__':
+ gr_unittest.main ()
Property changes on:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_ecc.py
___________________________________________________________________
Name: svn:executable
+ *
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_coding_1.py
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_coding_2.py
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_encoder_convolutional_1.py
Deleted:
gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src/python/qa_test_encoder_convolutional_2.py
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Commit-gnuradio] r3362 - in gnuradio/branches/developers/michaelld/wip/gr-error-correcting-codes/src: lib lib/libecc lib/libecc/tests python,
michaelld <=