diff options
author | jcorgan | 2006-08-03 04:51:51 +0000 |
---|---|---|
committer | jcorgan | 2006-08-03 04:51:51 +0000 |
commit | 5d69a524f81f234b3fbc41d49ba18d6f6886baba (patch) | |
tree | b71312bf7f1e8d10fef0f3ac6f28784065e73e72 /gr-error-correcting-codes/src/lib/libecc | |
download | gnuradio-5d69a524f81f234b3fbc41d49ba18d6f6886baba.tar.gz gnuradio-5d69a524f81f234b3fbc41d49ba18d6f6886baba.tar.bz2 gnuradio-5d69a524f81f234b3fbc41d49ba18d6f6886baba.zip |
Houston, we have a trunk.
git-svn-id: http://gnuradio.org/svn/gnuradio/trunk@3122 221aa14e-8319-0410-a670-987f0aec2ac5
Diffstat (limited to 'gr-error-correcting-codes/src/lib/libecc')
35 files changed, 7330 insertions, 0 deletions
diff --git a/gr-error-correcting-codes/src/lib/libecc/Makefile.am b/gr-error-correcting-codes/src/lib/libecc/Makefile.am new file mode 100644 index 000000000..e2fa9eca5 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/Makefile.am @@ -0,0 +1,60 @@ +# +# 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. +# + +include $(top_srcdir)/Makefile.common + +SUBDIRS = mld . tests + +INCLUDES = $(STD_DEFINES_AND_INCLUDES) -I.. + +noinst_LTLIBRARIES = libecc.la + +libecc_la_SOURCES = \ + code_convolutional_trellis.cc \ + code_metrics.cc \ + encoder.cc \ + encoder_convolutional.cc \ + encoder_convolutional_ic1_ic1.cc \ + encoder_turbo.cc \ + decoder.cc \ + decoder_viterbi.cc \ + decoder_viterbi_full_block.cc \ + decoder_viterbi_full_block_i1_ic1.cc + +noinst_HEADERS = \ + code_types.h code_metrics.h \ + code_convolutional_trellis.h \ + encoder.h encoder_turbo.h \ + encoder_convolutional.h \ + encoder_convolutional_ic1_ic1.h \ + decoder.h decoder_viterbi.h \ + decoder_viterbi_full_block.h \ + decoder_viterbi_full_block_i1_ic1.h + +# link the library against the c++ standard library +libecc_la_LIBADD = \ + mld/libmld.la \ + $(PYTHON_LDFLAGS) \ + -lstdc++ + +MOSTLYCLEANFILES = *.loT *~ + +CONFIG_CLEAN_FILES = *.in diff --git a/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc b/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc new file mode 100644 index 000000000..72b8adbf7 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.cc @@ -0,0 +1,1028 @@ +/* -*- 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_convolutional_trellis.h" +#include <assert.h> +#include <iostream> + +#define DO_TIME_THOUGHPUT 0 +#define DO_PRINT_DEBUG 1 +#define DO_PRINT_DEBUG_ENCODE 1 + +#include <mld/mld_timer.h> +#include <mld/n2bs.h> + +static const int g_max_block_size_bits = 10000000; +static const int g_max_num_streams = 10; +static const int g_num_bits_per_byte = 8; + +/* + * sum_bits_mod2: + * sum the number of set bits, mod 2, for the output bit + */ + +char +code_convolutional_trellis::sum_bits_mod2 +(memory_t in_mem, + size_t max_memory) +{ + // there are faster ways to do this, but this works for now; could + // certainly do a single inline asm, which most processors provide + // to deal with summing the bits in an integer. + // this routine can be overridden by another method if desired. + + char t_out_bit = (char)(in_mem & 1); + for (size_t r = max_memory; r > 0; r--) { + in_mem >>= 1; + t_out_bit ^= ((char)(in_mem & 1)); + } + return (t_out_bit); +} + +void +code_convolutional_trellis::code_convolutional_trellis_init +(int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int>& code_generators, + const std::vector<int>* code_feedback, + bool do_termination, + int end_memory_state) +{ + // do error checking on the input arguments + + // make sure the block length makes sense + + if ((block_size_bits < 0) | (block_size_bits > g_max_block_size_bits)) { + std::cerr << "code_convolutional_trellis: " << + "Requested block length (" << block_size_bits << + " bits) must be between 0 and " << g_max_block_size_bits << + " bits, with 0 being a streaming encoder.\n"; + assert (0); + } + + // check to make sure the number of input streams makes sense + + if ((n_code_inputs <= 0) | (n_code_inputs > g_max_num_streams)) { + std::cerr << "code_convolutional_trellis: " << + "Requested number of input streams (" << + n_code_inputs << ") must be between 1 and " << + g_max_num_streams << ".\n"; + assert (0); + } + + // check to make sure the number of output streams makes sense + + if ((n_code_outputs <= 0) | (n_code_outputs > g_max_num_streams)) { + std::cerr << "code_convolutional_trellis: " << + "Requested number of output streams (" << + n_code_outputs << ") must be between 1 and " << + g_max_num_streams << ".\n"; + assert (0); + } + + // make sure the code_generator is the correct length + + if (code_generators.size () != + ((size_t)(n_code_inputs * n_code_outputs))) { + std::cerr << "code_convolutional_trellis: " << + "Number of code generator entries (" << code_generators.size () << + ") is not equal to the product of the number of input and output" << + " streams (" << (n_code_inputs * n_code_outputs) << ").\n"; + assert (0); + } + + // check for feedback (== NULL or not) + + d_do_feedback = (code_feedback != NULL); + + // create the class block variables + + d_block_size_bits = block_size_bits; + d_n_code_inputs = n_code_inputs; + d_n_code_outputs = n_code_outputs; + d_do_streaming = (block_size_bits == 0); + d_do_termination = (d_do_streaming == true) ? false : do_termination; + + if (DO_PRINT_DEBUG) { + std::cout << + "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_streaming = " << + ((d_do_streaming == true) ? "true" : "false") << "\n" + "d_do_termination = " << + ((d_do_termination == true) ? "true" : "false") << "\n" + "d_do_feedback = " << + ((d_do_feedback == true) ? "true" : "false") << "\n"; + } + + // allocate the vectors for doing the encoding. use memory_t (an + // interger type, at least 32 bits) bits to represent memory and the + // code, as it makes the operations quite simple the state vectors. + + // d_states is a "matrix" [#input by #outputs] containing indices + // to memory_t's; this is done to make feedback function properly, + // and doesn't effect the computation time for feedforward. The + // issue is that any code with the same feedback can use the same + // memory - thus reducing the actual number of memories required. + // These overlapping encoders will use the same actual memory, but + // given that there is no way to know a-priori where they are, use + // pointers over the full I/O matrix-space to make sure each I/O + // encoder uses the correct memory. + // reference the matrix using "maoi(i,o)" ... see .h file. + + // code generators (feedforward part) are [#inputs x #outputs], + // always - one for each I/O combination. + // reference the matrix using "maoi(i,o)" ... see .h file + + d_code_generators.assign (d_n_code_inputs * d_n_code_outputs, 0); + + // check the feedback for correctness, before anything else, since + // any feedback impacts the total # of delays in the encoder: + // without feedback, this is the sum of the individual delays max'ed + // over each input (if siao) or output (if soai). + + if (d_do_feedback == true) { + memory_t t_OR_all_feedback = 0; + for (size_t n = 0; n < d_n_code_outputs; n++) { + for (size_t m = 0; m < d_n_code_inputs; m++) { + memory_t t_in_code = (*code_feedback)[maoi(m,n)]; + + // OR this feedback with the overall, + // to check for any delays used at all + + t_OR_all_feedback |= t_in_code; + } + } + + // check to see if all the feedback entries were either "0" or "1", + // which implies no feedback; warn the user in that case and reset + // the do_feedback parameter to false. + + if ((t_OR_all_feedback | 1) == 1) { + std::cout << "code_convolutional_trellis: Warning: " << + "No feedback is required, ignoring feedback.\n"; + d_do_feedback = false; + } + } + + // copy over the FF code generators + + for (size_t n = 0; n < d_n_code_outputs; n++) + for (size_t m = 0; m < d_n_code_inputs; m++) + d_code_generators[maio(m,n)] = code_generators[maio(m,n)]; + + // check the input FF (and FB) code generators for correctness, and + // find the minimum memory configuration: combining via a single + // input / all outputs (SIAO), or a single output / all inputs (SOAI). + // + // for FF only, look over both the SOAI and SIAO realizations to + // find the minimum total # of delays, and use that realization + // (SOAI is preferred if total # of delays is equal, since it's much + // simpler to implement). + // + // for FB: + // for SIAO, check each input row (all outputs for a given input) + // for unique feedback; duplicate feedback entries can be + // combined into a single computation to reduce total # of delays. + // for SOAI: check each output column (all inputs for a given + // output) for unique feedback; duplicate feedback entries can + // be combined into a simgle computation (ditto). + + // check for SOAI all '0' output + + for (size_t n = 0; n < d_n_code_outputs; n++) { + memory_t t_all_inputs_zero = 0; + for (size_t m = 0; m < d_n_code_inputs; m++) + t_all_inputs_zero |= d_code_generators[maio(m,n)]; + + // check this input to see if all encoders were '0'; this might be + // OK for some codes, but warn the user just in case + + if (t_all_inputs_zero == 0) { + std::cout << "code_convolutional_trellis: Warning:" + "Output " << n+1 << " (of " << d_n_code_outputs << + ") will always be 0.\n"; + } + } + + // check for SIAO all '0' input + + for (size_t m = 0; m < d_n_code_inputs; m++) { + memory_t t_all_outputs_zero = 0; + for (size_t n = 0; n < d_n_code_outputs; n++) + t_all_outputs_zero |= d_code_generators[maio(m,n)]; + + // check this input to see if all encoders were '0'; this might be + // OK for some codes, but warn the user just in case + + if (t_all_outputs_zero == 0) { + std::cout << "code_convolutional_trellis: Warning:" + "Input " << m+1 << " (of " << d_n_code_inputs << + ") will not be used; all encoders are '0'.\n"; + } + } + + // check and compute memory requirements in order to determine which + // realization uses the least memory; create and save findings to + // not have to re-do these computations later. + + // single output, all inputs (SOAI) realization: + // reset the global parameters + + d_code_feedback.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_n_delays.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_io_num.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_states_ndx.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_max_delay = d_total_n_delays = d_n_memories = 0; + d_do_encode_soai = true; + + for (size_t n = 0; n < d_n_code_outputs; n++) { + size_t t_max_mem = 0; + size_t t_n_unique_fb_prev_start = d_n_memories; + + for (size_t m = 0; m < d_n_code_inputs; m++) { + get_memory_requirements (m, n, t_max_mem, + t_n_unique_fb_prev_start, code_feedback); + if (d_do_feedback == false) { + d_states_ndx[maio(m,n)] = n; + } + } + if (d_do_feedback == false) { + // not feedback; just store memory requirements for this output + d_total_n_delays += t_max_mem; + d_n_delays[n] = t_max_mem; + d_io_num[n] = n; + } + } + if (d_do_feedback == false) { + d_n_memories = d_n_code_outputs; + } + + // store the parameters for SOAI + + std::vector<size_t> t_fb_generators_soai, t_n_delays_soai, t_io_num_soai; + std::vector<size_t> t_states_ndx_soai; + size_t t_max_delay_soai, t_total_n_delays_soai, t_n_memories_soai; + + t_fb_generators_soai.assign (d_code_feedback.size (), 0); + t_fb_generators_soai = d_code_feedback; + t_n_delays_soai.assign (d_n_delays.size (), 0); + t_n_delays_soai = d_n_delays; + t_io_num_soai.assign (d_io_num.size (), 0); + t_io_num_soai = d_io_num; + t_states_ndx_soai.assign (d_states_ndx.size (), 0); + t_states_ndx_soai = d_states_ndx; + + t_n_memories_soai = d_n_memories; + t_total_n_delays_soai = d_total_n_delays; + t_max_delay_soai = d_max_delay; + + // single input, all outputs (SIAO) realization + // reset the global parameters + + d_code_feedback.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_n_delays.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_io_num.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_states_ndx.assign (d_n_code_inputs * d_n_code_outputs, 0); + d_max_delay = d_total_n_delays = d_n_memories = 0; + d_do_encode_soai = false; + + for (size_t m = 0; m < d_n_code_inputs; m++) { + size_t t_max_mem = 0; + size_t t_n_unique_fb_prev_start = d_n_memories; + + for (size_t n = 0; n < d_n_code_outputs; n++) { + get_memory_requirements (m, n, t_max_mem, + t_n_unique_fb_prev_start, code_feedback); + if (d_do_feedback == false) { + d_states_ndx[maio(m,n)] = m; + } + } + if (d_do_feedback == false) { + // not feedback; just store memory requirements for this output + d_total_n_delays += t_max_mem; + d_n_delays[m] = t_max_mem; + d_io_num[m] = m; + } + } + if (d_do_feedback == false) { + d_n_memories = d_n_code_inputs; + } + + if (DO_PRINT_DEBUG) { + std::cout << + " t_total_n_delays_siao = " << d_total_n_delays << "\n" + " t_total_n_delays_soai = " << t_total_n_delays_soai << "\n"; + } + + // pick which realization to use; soai is preferred since it's faster + // ... but unfortunately it's also less likely + + if (d_total_n_delays < t_total_n_delays_soai) { + // use siao + // nothing else to do, since the global variables already hold + // the correct values. + } else { + // use soai + d_do_encode_soai = true; + d_code_feedback = t_fb_generators_soai; + d_n_delays = t_n_delays_soai; + d_io_num = t_io_num_soai; + d_states_ndx = t_states_ndx_soai; + d_n_memories = t_n_memories_soai; + d_total_n_delays = t_total_n_delays_soai; + d_max_delay = t_max_delay_soai; + } + + // make sure the block length makes sense, #2 + + if ((d_do_streaming == false) & (d_block_size_bits < d_max_delay)) { + std::cerr << "code_convolutional_trellis: " << + "Requested block length (" << d_block_size_bits << + " bit" << (d_block_size_bits > 1 ? "s" : "") << + ") must be at least 1 memory length (" << d_max_delay << + " bit" << (d_max_delay > 1 ? "s" : "") << + " for this code) when doing block coding.\n"; + assert (0); + } + + // check & mask off the init states + + d_n_states = (1 << d_total_n_delays); + d_n_input_combinations = (1 << d_n_code_inputs); + + memory_t t_mask = (memory_t)((2 << d_total_n_delays) - 1); + + if (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; + } + + // create the max_mem_mask to be used in encoding + + d_max_mem_masks.assign (d_n_memories, 0); + + for (size_t m = 0; m < d_n_memories; m++) { + if (d_n_delays[m] == sizeof (memory_t) * g_num_bits_per_byte) + d_max_mem_masks[m] = ((memory_t) -1); + else + d_max_mem_masks[m] = (memory_t)((2 << (d_n_delays[m])) - 1); + } + + if (DO_PRINT_DEBUG) { + std::cout << + " d_n_memories = " << d_n_memories << "\n" + " d_total_n_delays = " << d_total_n_delays << "\n" + " d_max_delay = " << d_max_delay << "\n" + " d_do_encode_soai = " << + ((d_do_encode_soai == true) ? "true" : "false") << "\n"; + } + + // zero the memories + + d_memory.assign (d_n_memories, 0); + + // create the inputs and outputs buffers + + d_current_inputs.assign (d_n_code_inputs, 0); + d_current_outputs.assign (d_n_code_outputs, 0); + + // create the trellis for this code: + + create_trellis (); + + if (d_do_termination == true) { + + // create the termination lookup table + + create_termination_table (end_memory_state); + } +} + +void +code_convolutional_trellis::get_memory_requirements +(size_t m, // input number + size_t n, // output number + size_t& t_max_mem, + size_t& t_n_unique_fb_prev_start, + const std::vector<int>* code_feedback) +{ + size_t t_in_code = d_code_generators[maio(m,n)]; + + // find the memory requirement for this code generator + + size_t t_code_mem_ff = max_bit_position (t_in_code); + + // check to see if this is bigger than any others in this row/column + + if (t_code_mem_ff > t_max_mem) + t_max_mem = t_code_mem_ff; + + if (DO_PRINT_DEBUG) { + std::cout << "c_g[" << m << "][" << n << "]{" << + maio(m,n) << "} = " << n2bs(t_in_code, 8) << + ", code_mem = " << t_code_mem_ff; + } + + // check the feedback portion, if it exists; + // for soai, check all the inputs which generate this output for + // uniqueness; duplicate entries can be combined to reduce total + // # of memories as well as required computations. + + if (d_do_feedback == true) { + if (DO_PRINT_DEBUG) { + std::cout << "\n"; + } + + // get the FB code; AND off the LSB for correct functionality + // during internal computations. + + t_in_code = ((memory_t)((*code_feedback)[maio(m,n)])); + t_in_code &= ((memory_t)(-2)); + + // find the memory requirement + + size_t t_code_mem_fb = max_bit_position (t_in_code); + + if (DO_PRINT_DEBUG) { + std::cout << "c_f[" << m << "][" << n << "]{" << + maio(m,n) << "} = " << n2bs(t_in_code, 8) << + ", code_mem = " << t_code_mem_fb; + } + + // check to see if this feedback is unique + + size_t l_n_unique_fb = t_n_unique_fb_prev_start; + while (l_n_unique_fb < d_n_memories) { + if (d_code_feedback[l_n_unique_fb] == t_in_code) + break; + l_n_unique_fb++; + } + if (l_n_unique_fb == d_n_memories) { + + // this is a unique feedback; + + d_code_feedback[l_n_unique_fb] = t_in_code; + d_n_delays[l_n_unique_fb] = t_code_mem_fb; + + // increase the number of unique feedback codes + + d_n_memories++; + + // store memory requirements for this output + + if (t_max_mem < t_code_mem_fb) + t_max_mem = t_code_mem_fb; + d_total_n_delays += t_max_mem; + + if (DO_PRINT_DEBUG) { + std::cout << ", uq # " << l_n_unique_fb << + ", tot_mem = " << d_total_n_delays; + } + } else { + // not a unique feedback, but the FF might require more memory + + if (DO_PRINT_DEBUG) { + std::cout << ", !uq # " << l_n_unique_fb << + " = " << d_n_delays[l_n_unique_fb]; + } + + if (d_n_delays[l_n_unique_fb] < t_code_mem_ff) { + d_total_n_delays += (t_code_mem_ff - d_n_delays[l_n_unique_fb]); + d_n_delays[l_n_unique_fb] = t_code_mem_ff; + + if (DO_PRINT_DEBUG) { + std::cout << " => " << d_n_delays[l_n_unique_fb] << + ", tot_mem = " << d_total_n_delays; + } + } + } + d_io_num[l_n_unique_fb] = ((d_do_encode_soai == true) ? n : m); + d_states_ndx[maio(m,n)] = l_n_unique_fb; + } + if (DO_PRINT_DEBUG) { + std::cout << "\n"; + } + if (d_max_delay < t_max_mem) + d_max_delay = t_max_mem; +} + +void +code_convolutional_trellis::create_trellis +() +{ + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << "c_t: # states = " << d_n_states << + ", d_n_input_combinations = " << d_n_input_combinations << "\n"; + } + + // first dimension is the number of states + + d_trellis.resize (d_n_states); + + // second dimension (one per first dimension) is the number of input + // combinations + + for (size_t m = 0; m < d_n_states; m++) { + d_trellis[m].resize (d_n_input_combinations); + for (size_t n = 0; n < d_n_input_combinations; n++) { + connection_t_ptr t_connection = &(d_trellis[m][n]); + t_connection->d_output_bits.resize (d_n_code_outputs); + } + } + + // fill in the trellis + + for (size_t m = 0; m < d_n_states; m++) { + for (size_t n = 0; n < d_n_input_combinations; n++) { + connection_t_ptr t_connection = &(d_trellis[m][n]); + encode_single (m, n, t_connection->d_to_state, + t_connection->d_output_bits); + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << "set d_t[" << n2bs(m,d_total_n_delays) << "][" << + n2bs(n,d_n_code_inputs) << "] : to_st = " << + n2bs(t_connection->d_to_state,d_total_n_delays) << "\n"; + } + } + } +} + +void +code_convolutional_trellis::demux_state +(memory_t in_state, + std::vector<memory_t>& memories) +{ + // de-mux bits for the given memory state; + // copy them into the provided vector; + // assumes state bits start after the LSB (not at &1) + + memories.resize (d_n_memories); + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << "in_st = " << n2bs(in_state,d_total_n_delays) << " ->\n"; + } + for (size_t m = 0; m < d_n_memories; m++) { + memories[m] = (in_state << 1) & d_max_mem_masks[m]; + in_state >>= d_n_delays[m]; + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << " #d = " << d_n_delays[m] << ", mem[" << m << "] = " << + n2bs(memories[m], d_n_delays[m]+1) << "\n"; + } + } +} + +memory_t +code_convolutional_trellis::mux_state +(const std::vector<memory_t>& memories) +{ + // mux bits for the given memory states in d_memory + // assumes state bits start after the LSB (not at &1) + memory_t t_state = 0; + size_t shift = 0; + for (size_t m = 0; m < d_n_memories; m++) { + t_state |= (memories[m] >> 1) << shift; + shift += d_n_delays[m]; + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << " #d = " << d_n_delays[m] << ", mem[" << m << "] = " << + n2bs(memories[m], d_n_delays[m]+1) << " -> st = " << + n2bs(t_state, d_total_n_delays) << "\n"; + } + } + return (t_state); +} + +void +code_convolutional_trellis::demux_inputs +(memory_t inputs, + std::vector<char>& in_vec) +{ + for (size_t m = 0; m < d_n_code_inputs; m++, inputs >>= 1) { + in_vec[m] = (char)(inputs & 1); + } +} + +memory_t +code_convolutional_trellis::mux_inputs +(const std::vector<char>& in_vec) +{ + size_t bit_shift = 0; + memory_t inputs = 0; + for (size_t m = 0; m < in_vec.size(); m++, bit_shift++) { + inputs |= (((memory_t)(in_vec[m]&1)) << bit_shift); + } + return (inputs); +} + +void +code_convolutional_trellis::encode_single +(memory_t in_state, + size_t inputs, + memory_t& out_state, + std::vector<char>& out_bits) +{ + // set input parameters + + demux_state (in_state, d_memory); + demux_inputs (inputs, d_current_inputs); + + // call the correct function to do the work + + if (d_do_encode_soai == true) { + if (d_do_feedback == true) { + encode_single_soai_fb (); + } else { + encode_single_soai (); + } + } else { + if (d_do_feedback == true) { + encode_single_siao_fb (); + } else { + encode_single_siao (); + } + } + + // retrieve the output parameters + + out_state = mux_state (d_memory); + out_bits = d_current_outputs; +} + +void +code_convolutional_trellis::encode_lookup +(memory_t& state, + const std::vector<char>& inputs, + std::vector<char>& out_bits) +{ + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << "using d_t[" << state << "][" << mux_inputs(inputs) << + "] = "; + std::cout.flush (); + } + + connection_t_ptr t_connection = &(d_trellis[state][mux_inputs(inputs)]); + + if (DO_PRINT_DEBUG_ENCODE) { + std::cout << t_connection << ": to_state = " + << t_connection->d_to_state << "\n"; + } + + state = t_connection->d_to_state; + out_bits = t_connection->d_output_bits; +} + +void +code_convolutional_trellis::get_termination_inputs +(memory_t term_start_state, + size_t bit_num, + std::vector<char>& inputs) +{ + inputs.resize (d_n_code_inputs); + for (size_t m = 0; m < d_n_code_inputs; m++) { + inputs[m] = ((d_term_inputs[term_start_state][m]) >> bit_num) & 1; + } +} + +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 + // std::vector<memory_t> of length n_states, once per path required + // to get from the given state to the desired termination state. + // + // each entry represents the bits required to terminate that + // particular state, listed in order from LSB for the first input + // bit to the MSB for the last input bit. + +#if 0 + // create a reverse trellis + // it's temporary, just for doing the termination, so just do it locally + + trellis_t t_trellis; + + // first dimension is the number of states + + t_trellis.resize (d_n_states); + + // second dimension (one per first dimension) is the number of input + // combinations + + for (size_t m = 0; m < d_n_states; m++) { + t_trellis[m].resize (d_n_input_combinations); + } + + std::vector<char> outputs (d_n_code_outputs); + memory_t to_state; + + // fill in the trellis + + for (memory_t m = 0; m < d_n_states; m++) { + for (memory_t n = 0; n < d_n_input_combinations; n++) { + encode_single (m, n, to_state, outputs); + + connection_t_ptr t_connection = &(t_trellis[to_state][n]); + t_connection->d_to_state = m; +#if 0 + t_connection->d_output_bits.resize (d_n_code_outputs); + t_connection->d_output_bits = outputs; +#endif + } + } + + // create the output vectors + + term_input_t t_term_inputs; + t_term_inputs.resize (d_n_states); + for (size_t m = 0; m < d_n_states; m++) { + t_term_inputs[m].assign (d_n_code_inputs, 0); + } + + + std::vector<memory_t> t_used_states; + t_used_states.assign (d_n_states, 0); + + // setup the first state + + t_states[0] = end_memory_state; + size_t n_states = 1; + + for (size_t m = 0; m < d_total_n_delays; m++) { + for (size_t n = 0; n < n_states; n++) { + memory_t t_end_state = t_states[n]; + for (size_t p = 0; p < d_n_code_inputs; p++) { + connection_t_ptr t_connection = &(t_trellis[t_end_state][p]); + memory_t_ptr t_mem = &(t_term_inputs[t_end_state][p]); + + + + + } + } + + t_inputs[0] = t_trellis +#endif +} + +void +code_convolutional_trellis::encode_single_soai +() +{ + // single-output, all inputs; no feedback + + if (DO_PRINT_DEBUG) { + std::cout << "Starting encode_single_soai.\n"; + } + + // shift memories down by 1 bit to make room for feedback; no + // masking required. + + for (size_t p = 0; p < d_n_memories; p++) { + if (DO_PRINT_DEBUG) { + std::cout << "m_i[" << p << "] = " << + n2bs(d_memory[p], 1+d_n_delays[p]); + } + + d_memory[p] >>= 1; + + if (DO_PRINT_DEBUG) { + std::cout << " >>= 1 -> " << + n2bs(d_memory[p], 1+d_n_delays[p]) << "\n"; + } + } + + // for each input bit, if that bit's a '1', then XOR the code + // generators into the correct state's memory. + + for (size_t m = 0; m < d_n_code_inputs; m++) { + if (DO_PRINT_DEBUG) { + std::cout << "c_i[" << m << "] = " << + n2bs(d_current_inputs[m],1); + } + if (d_current_inputs[m] == 1) { + if (DO_PRINT_DEBUG) { + std::cout << "\n"; + } + for (size_t n = 0; n < d_n_code_outputs; n++) { + if (DO_PRINT_DEBUG) { + std::cout << "m_i[s_ndx[" << m << "][" << n << "] == " << + d_states_ndx[maio(m,n)] << "] = " << + n2bs(d_memory[d_states_ndx[maio(m,n)]], + 1+d_n_delays[d_states_ndx[maio(m,n)]]); + } + + d_memory[d_states_ndx[maio(m,n)]] ^= d_code_generators[maio(m,n)]; + + if (DO_PRINT_DEBUG) { + std::cout << " ^= c_g[][] == " << + n2bs(d_code_generators[maio(m,n)], + 1+d_n_delays[d_states_ndx[maio(m,n)]]) << + " -> " << n2bs(d_memory[d_states_ndx[maio(m,n)]], + 1+d_n_delays[d_states_ndx[maio(m,n)]]) << "\n"; + } + } + } else if (DO_PRINT_DEBUG) { + std::cout << " ... nothing to do\n"; + } + } + + for (size_t p = 0; p < d_n_code_outputs; p++) { + d_current_outputs[p] = 0; + } + + // create the output bits, by XOR'ing the individual unique + // memory(ies) into the correct output bit + + for (size_t p = 0; p < d_n_memories; p++) { + d_current_outputs[d_io_num[p]] ^= ((char)(d_memory[p] & 1)); + } + + if (DO_PRINT_DEBUG) { + std::cout << "ending encode_single_soai.\n"; + } +} + +void +code_convolutional_trellis::encode_single_soai_fb +() +{ + // single-output, all inputs; with feedback + + if (DO_PRINT_DEBUG) { + std::cout << "Starting encode_single_soai_fb.\n"; + } + + // shift memories down by 1 bit to make room for feedback; no + // masking required. + + for (size_t p = 0; p < d_n_memories; p++) { + if (DO_PRINT_DEBUG) { + std::cout << "m_i[" << p << "] = " << d_memory[p]; + } + + d_memory[p] >>= 1; + + if (DO_PRINT_DEBUG) { + std::cout << " -> " << d_memory[p] << "\n"; + } + } + + // for each input bit, if that bit's a '1', then XOR the code + // generators into the correct state's memory. + + for (size_t m = 0; m < d_n_code_inputs; m++) { + if (d_current_inputs[m] == 1) { + for (size_t n = 0; n < d_n_code_outputs; n++) { + d_memory[d_states_ndx[maio(m,n)]] ^= d_code_generators[maio(m,n)]; + } + } + } + + for (size_t p = 0; p < d_n_code_outputs; p++) { + d_current_outputs[p] = 0; + } + + // create the output bits, by XOR'ing the individual unique + // memory(ies) into the correct output bit + + for (size_t p = 0; p < d_n_memories; p++) { + d_current_outputs[d_io_num[p]] ^= ((char)(d_memory[p] & 1)); + } + + // now that the output bits are fully created, XOR the FB back + // into the memories; the feedback bits have the LSB (&1) masked + // off already so that it doesn't contribute. + + for (size_t p = 0; p < d_n_memories; p++) { + if (d_current_outputs[d_io_num[p]] == 1) { + d_memory[p] ^= d_code_feedback[p]; + } + } + + if (DO_PRINT_DEBUG) { + std::cout << "ending encode_single_soai.\n"; + } +} + +void +code_convolutional_trellis::encode_single_siao +() +{ + // single input, all outputs; no feedback + + if (DO_PRINT_DEBUG) { + std::cout << "starting encode_single_siao.\n"; + } + + // update the memories with the current input bits; + + // for each unique memory (1 per input), shift the delays and mask + // off the extra high bits; then XOR in the input bit. + + for (size_t p = 0; p < d_n_memories; p++) { + d_memory[p] |= ((memory_t)(d_current_inputs[d_io_num[p]])); + } + + // create the output bits: for each output, loop over all inputs, + // find the output bits for each encoder, and XOR each together + // then sum (would usually be sum then XOR, but they're mutable in + // base-2 and it's faster this way). + + for (size_t n = 0; n < d_n_code_outputs; n++) { + memory_t t_mem = 0; + for (size_t m = 0; m < d_n_code_inputs; m++) { + t_mem ^= ((d_memory[d_states_ndx[maio(m,n)]]) & + d_code_generators[maio(m,n)]); + } + d_current_outputs[n] = sum_bits_mod2 (t_mem, d_max_delay); + } + + // post-shift & mask the memory to guarantee that output + // state is in the correct bit positions (1 up, not the LSB) + + for (size_t p = 0; p < d_n_memories; p++) { + d_memory[p] = (d_memory[p] << 1) & d_max_mem_masks[p]; + } + + if (DO_PRINT_DEBUG) { + std::cout << "ending encode_single_siao.\n"; + } +} + +void +code_convolutional_trellis::encode_single_siao_fb +() +{ + // single input, all outputs; with feedback + + if (DO_PRINT_DEBUG) { + std::cout << "starting encode_single_siao_fb.\n"; + } + + // update the memories with the current input bits; + + // for each unique memory (1 per input), shift the delays and mask + // off the extra high bits; then XOR in the input bit. + // with FB: find the feedback bit, and OR it into the input bit's slot; + + for (size_t p = 0; p < d_n_memories; p++) { + memory_t t_mem = d_memory[p]; + memory_t t_fb = t_mem & d_code_feedback[p]; + char t_fb_bit = sum_bits_mod2 (t_fb, d_max_delay); + t_mem |= ((memory_t) t_fb_bit); + d_memory[p] = t_mem ^ ((memory_t)(d_current_inputs[d_io_num[p]])); + } + + // create the output bits: for each output, loop over all inputs, + // find the output bits for each encoder, and XOR each together + // then sum (would usually be sum then XOR, but they're mutable in + // base-2 and it's faster this way). + + for (size_t n = 0; n < d_n_code_outputs; n++) { + memory_t t_mem = 0; + for (size_t m = 0; m < d_n_code_inputs; m++) { + t_mem ^= ((d_memory[d_states_ndx[maio(m,n)]]) & + d_code_generators[maio(m,n)]); + } + d_current_outputs[n] = sum_bits_mod2 (t_mem, d_max_delay); + } + + // post-shift & mask the memory to guarantee that output + // state is in the correct bit positions (1 up, not the LSB) + + for (size_t p = 0; p < d_n_memories; p++) { + d_memory[p] = (d_memory[p] << 1) & d_max_mem_masks[p]; + } + + if (DO_PRINT_DEBUG) { + std::cout << "ending encode_loop_siao_fb.\n"; + } +} diff --git a/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h b/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h new file mode 100644 index 000000000..205ccc03d --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/code_convolutional_trellis.h @@ -0,0 +1,372 @@ +/* -*- 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_CONVOLUTIONAL_TRELLIS_H +#define INCLUDED_CODE_CONVOLUTIONAL_TRELLIS_H + +#include "code_types.h" +#include <vector> + +/* + * connection_t: describes an output connection from the current + * time-bit memory state to the next time-bit memory state + * + * d_to_state: memory configuration of the "to" state + * + * d_output_bits: the output bits for this connection + */ + +typedef struct connection_t { + memory_t d_to_state; + std::vector<char> d_output_bits; +} connection_t, *connection_t_ptr; + +/* + * trellis_t: describes a single set of trellis connections, from a + * time-bit to the next, forward transitions only + * + * This is a 2d "matrix", where the first dimention is the starting + * memory state, and the second is the (combined) input as an + * integer: e.g. for a 2 input code, if I1 = 0 and I2 = 1, then + * the combined input is the "number" found by appending I2 and I1 + * together, in this case 10b = 3. + * + * The trellis is used to lookup information: given a starting state + * and inputs, return the output bits and next state. + */ + +typedef std::vector<std::vector<connection_t> > trellis_t, *trellis_t_ptr; + +class code_convolutional_trellis +{ +/*! + * class code_convolutional_trellis + * + * Create a convolutional code trellis structure, but encoding, + * decoding, determining termination transitions, and anything else + * which might be useful. + * + * block_size_bits: if == 0, then do streaming encoding ("infinite" + * trellis); otherwise this is the block size in bits to encode + * before terminating the trellis. This value -does not- include + * any termination bits. + * + * n_code_inputs: + * n_code_outputs: + * code_generator: vector of integers (32 bit) representing the code + * to be implemented. E.g. "4" in binary is "100", which would be + * "D^2" for code generation. "6" == 110b == "D^2 + D" + * ==> The vector is listed in order for each output stream, so if there + * are 2 input streams (I1, I2) [specified in "n_code_inputs"] + * and 2 output streams (O1, O2) [specified in "n_code_outputs"], + * then the vector would be the code generator for: + * [I1->O1, I2->O1, I1->O2, I2->O2] + * with each element being an integer representation of the code. + * The "octal" representation is used frequently in the literature + * (e.g. [015, 06] == [1101, 0110] in binary) due to its close + * relationship with binary (each number is 3 binary digits) + * ... but any integer representation will suffice. + * + * do_termination: valid only if block_size_bits != 0, and defines + * whether or not to use trellis termination. Default is to use + * termination when doing block coding. + * + * start_memory_state: when starting a new block, the starting memory + * state to begin encoding; there will be a helper function to + * assist in creating this value for a given set of inputs; + * default is the "all zero" state. + * + * end_memory_state: when terminating a block, the ending memory + * state to stop encoding; there will be a helper function to + * assist in creating this value for a given set of inputs; + * default is the "all zero" state. + */ + +public: + inline code_convolutional_trellis + (int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + bool do_termination = true, + int end_memory_state = 0) + {code_convolutional_trellis_init (block_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + NULL, + do_termination, + end_memory_state);}; + +/*! + * Encoder with feedback. + * + * code_feedback: vector of integers (32 bit) representing the code + * feedback to be implemented (same as for the code_generator). + * For this feedback type, the LSB ("& 1") is ignored (set to "1" + * internally, since it's always 1) ... this (effectively) + * represents the input bit for the given encoder, without which + * there would be no encoding! Each successive higher-order bit + * represents the output of that delay block; for example "6" == + * 110b == "D^2 + D" means use the current input bit + the output + * of the second delay block. Listing order is the same as for + * the code_generator. + */ + + inline code_convolutional_trellis + (int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + const std::vector<int> &code_feedback, + bool do_termination = true, + int end_memory_state = 0) + {code_convolutional_trellis_init (block_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + &code_feedback, + do_termination, + end_memory_state);}; + + virtual ~code_convolutional_trellis () {}; + +/* for remote access to internal info */ + + inline size_t block_size_bits () {return (d_block_size_bits);}; + inline size_t n_code_inputs () {return (d_n_code_inputs);}; + inline size_t n_code_outputs () {return (d_n_code_outputs);}; + inline const bool do_termination () {return (d_do_termination);}; + inline const bool do_feedback () {return (d_do_feedback);}; + inline const bool do_streaming () {return (d_do_streaming);}; + inline const size_t total_n_delays () {return (d_total_n_delays);}; + + 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); + + void encode_lookup (memory_t& state, + const std::vector<char>& inputs, + std::vector<char>& out_bits); + + void demux_state (memory_t in_state, std::vector<memory_t>& memories); + memory_t mux_state (const std::vector<memory_t>& memories); + void demux_inputs (memory_t inputs, std::vector<char>& in_vec); + memory_t mux_inputs (const std::vector<char>& in_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. + * + * 'i' is the 1st dimension - faster memory - the code input + * 'o' is the 2nd dimension - slower memory - the code output + * + * returns ((o*n_code_inputs) + i) + */ + + inline size_t maio(size_t i, size_t o) {return ((o*d_n_code_inputs) + i);}; + +/* + * maoi(i,o): matrix access into a vector, knowing the # of code + * inputs (from inside the class). References into a vector with + * code outputs ordered by code input. + * + * 'o' is the 1st dimension - faster memory - the code output + * 'i' is the 2nd dimension - slower memory - the code input + * + * returns ((i*n_code_outputs) + o) + */ + + inline size_t maoi(size_t i, size_t o) {return ((i*d_n_code_outputs) + o);}; + +/* + * max_bit_position (x): returns the bit-number of the highest "1" bit + * in the provided value, such that the LSB would return 0 and the MSB + * of a long would return 31. + */ + + inline size_t max_bit_position (memory_t x) + { + size_t t_code_mem = 0; + memory_t t_in_code = x >> 1; + while (t_in_code != 0) { + t_in_code >>= 1; + t_code_mem++; + } + + return (t_code_mem); + } + + // methods defined in this class + + void code_convolutional_trellis_init + (int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int>& code_generators, + const std::vector<int>* code_generators, + bool do_termination, + int end_memory_state); + + void create_trellis (); + void create_termination_table (memory_t end_memory_state); + void encode_single (memory_t in_state, + memory_t inputs, + memory_t& out_state, + std::vector<char>& out_bits); + virtual void encode_single_soai (); + virtual void encode_single_siao (); + virtual void encode_single_soai_fb (); + virtual void encode_single_siao_fb (); + + void get_memory_requirements (size_t m, + size_t n, + size_t& t_max_mem, + size_t& t_n_unique_fb_prev_start, + const std::vector<int>* code_feedback); + + // variables + + size_t d_block_size_bits, d_n_code_outputs; + size_t d_n_code_inputs, d_n_input_combinations; + bool d_do_streaming, d_do_termination, d_do_feedback, d_do_encode_soai; + + // "max_delay" is the max # of delays for all unique generators (ff and fb), + // needed to determine (e.g.) termination + + size_t d_max_delay; + + // "n_memories" is the number of unique memories as determined by + // either the feedforward or feedback generators (not both). For + // FF, this number equals either the number of code inputs (for + // SIAO) or outputs (for SOAI). + + size_t d_n_memories; + + // "total_n_delays" is the total # of delays, needed to determine the + // # of states in the decoder + // "n_states" = (2^n_delays) - 1 .. the number of memory states + + size_t d_total_n_delays, d_n_states; + + // "code generators" are stored internally in "maXY(i,o)" order this + // allows for looping over all a single output and computing all + // input parts sequentially. + + std::vector<memory_t> d_code_generators; + + // "feedback" are found as "d_n_memories" unique entries, and stored + // in at most 1 entry per I/O combination. Listed in the same order + // as "d_io_num" entries show. + + std::vector<memory_t> d_code_feedback; + + // "n_delays" is a vector, the number of delays for the FB generator + // in the same [] location; also relates directly to the + // "max_mem_masks" in the same [] location. + + std::vector<size_t> d_n_delays; + + // "io_num" is a vector, mapping which FB in SIAO goes with which + // input, or which FB in SOAI goes with which output + + std::vector<size_t> d_io_num; + + // "max_mem_masks" are the memory masks, one per unique FB for SIAO; + // otherwise not used. + + std::vector<size_t> d_states_ndx; + + // "memory" are the actual stored delay bits, one memory for each + // unique FF or FB code generator; + // interpreted w/r.t. the actual FF and FB code generators and + // SOAI / SIAO realization; + + std::vector<memory_t> d_max_mem_masks; + + // "states_ndx" is a "matrix" whose contents are the indices into + // the "io_num" vector, telling which input goes with which + // state; uses the same "maXY(i,o)" as the code generators. + + std::vector<memory_t> d_memory; + + // "term_inputs" are the inputs required to terminate the trellis - + // interpreted w/r.t. the actual FF and FB code generators and + // SOAI / SIAO realization; + // first dimension is the memory state #; + // second dimension is the input stream #; + // bits are packed, with the first input being the LSB and the last + // input being closest to the MSB. + + typedef std::vector<std::vector<memory_t> > term_input_t; + term_input_t d_term_inputs; + + // "inputs" are the current input bits, in the LSB (&1) of each "char" + + std::vector<char> d_current_inputs; + + // "outputs" are the current output bits, in the LSB (&1) of each "char" + + std::vector<char> d_current_outputs; + + // "trellis" is the single-stage memory state transition ("trellis") + // representation for this code; forward paths only + + trellis_t d_trellis; +}; + +#endif /* INCLUDED_CODE_CONVOLUTIONAL_TRELLIS_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/code_metrics.cc b/gr-error-correcting-codes/src/lib/libecc/code_metrics.cc new file mode 100644 index 000000000..392450863 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/code_metrics.cc @@ -0,0 +1,445 @@ +/* -*- 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.h> +#include <iostream> +#include <math.h> +#include <assert.h> + +code_metric_ff::code_metric_ff +(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) +{ + if (n_samples < 2) { + fprintf (stderr, "code_metric_f32:: n_samples " + "must be at least 2.\n"); + assert (0); + } + if (min_sample >= max_sample) { + fprintf (stderr, "code_metric_f32:: min_sample must be " + "less than max_sample.\n"); + assert (0); + } + if (! pdf_fcn_0_bit) { + fprintf (stderr, "code_metric_f32:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (! pdf_fcn_1_bit) { + fprintf (stderr, "code_metric_f32:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + + d_n_samples = n_samples; + d_max_sample = max_sample; + d_min_sample = min_sample; + d_delta = (max_sample - min_sample) / (n_samples - 1); + d_pdf_fcn_0_bit = pdf_fcn_0_bit; + d_pdf_fcn_1_bit = pdf_fcn_1_bit; + d_metric_table_0_bit.assign (n_samples, 0); + d_metric_table_1_bit.assign (n_samples, 0); + + pdf_fcn_io_t l_val = min_sample; + for (size_t m = 0; m < n_samples; m++) { + d_metric_table_0_bit[m] = logf ((*pdf_fcn_0_bit)(l_val)); + d_metric_table_1_bit[m] = logf ((*pdf_fcn_1_bit)(l_val)); + l_val += d_delta; + } +} + +void code_metric_ff::lookup +(pdf_fcn_io_t sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + if (sym <= d_min_sample) { + *l_bit_0 = d_metric_table_0_bit[0]; + *l_bit_1 = d_metric_table_1_bit[0]; + return; + } + if (sym >= 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) roundf ((sym - d_min_sample) / d_delta); + *l_bit_0 = d_metric_table_0_bit[l_ndx]; + *l_bit_1 = d_metric_table_1_bit[l_ndx]; +} + +void code_metric_ff::convert +(size_t n_syms, + pdf_fcn_io_t* sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + for (size_t m = n_syms; m > 0; m--) + lookup (*sym++, (void*) l_bit_0++, (void*) l_bit_1++); +} + +code_metric_fl::code_metric_fl +(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) +{ + if (n_samples < 2) { + fprintf (stderr, "code_metric_fl:: n_samples " + "must be at least 2.\n"); + assert (0); + } + if (min_sample >= max_sample) { + fprintf (stderr, "code_metric_fl:: min_sample must be " + "less than max_sample.\n"); + assert (0); + } + if (! pdf_fcn_0_bit) { + fprintf (stderr, "code_metric_fl:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (! pdf_fcn_1_bit) { + fprintf (stderr, "code_metric_fl:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (sample_precision < 16 || sample_precision > 32) { + fprintf (stderr, "code_metric_fl:: sample_precision must be " + "between 16 and 32 for this class.\n"); + assert (0); + } + + d_sample_precision = sample_precision; + d_n_samples = n_samples; + d_max_sample = max_sample; + d_min_sample = min_sample; + d_delta = (max_sample - min_sample) / (n_samples - 1); + d_pdf_fcn_0_bit = pdf_fcn_0_bit; + d_pdf_fcn_1_bit = pdf_fcn_1_bit; + d_metric_table_0_bit.assign (n_samples, 0); + d_metric_table_1_bit.assign (n_samples, 0); + + // get the scale factor for converting from float to sample_precision + // maps: + // logf (pdf_fcn_0_bit->eval (d_min_sample)) -> l_min_map + // logf (pdf_fcn_0_bit->eval (d_max_sample)) -> l_max_map + + metric_t l_min_map = - (1 << (sample_precision - 1)); + + pdf_fcn_io_t l_min_log_val_0 = logf ((*pdf_fcn_0_bit)(d_min_sample)); + pdf_fcn_io_t l_max_log_val_0 = logf ((*pdf_fcn_0_bit)(d_max_sample)); + pdf_fcn_io_t l_slope_0 = (powf (2.0, (pdf_fcn_io_t)(d_sample_precision)) / + (l_max_log_val_0 - l_min_log_val_0)); + pdf_fcn_io_t l_min_log_val_1 = logf ((*pdf_fcn_1_bit)(d_min_sample)); + pdf_fcn_io_t l_max_log_val_1 = logf ((*pdf_fcn_1_bit)(d_max_sample)); + pdf_fcn_io_t l_slope_1 = (powf (2.0, (pdf_fcn_io_t)(d_sample_precision)) / + (l_max_log_val_1 - l_min_log_val_1)); + + pdf_fcn_io_t l_val = d_min_sample; + for (size_t m = 0; m < d_n_samples; m++) { + d_metric_table_0_bit[m] = + (metric_t) roundf (((pdf_fcn_io_t) l_min_map) + + (l_slope_0 * (logf ((*pdf_fcn_0_bit)(l_val)) - + l_min_log_val_0))); + d_metric_table_1_bit[m] = + (metric_t) roundf (((pdf_fcn_io_t) l_min_map) + + (l_slope_1 * (logf ((*pdf_fcn_1_bit)(l_val)) - + l_min_log_val_1))); + l_val += d_delta; + } +} + +void code_metric_fl::lookup +(pdf_fcn_io_t sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + if (sym <= d_min_sample) { + *l_bit_0 = d_metric_table_0_bit[0]; + *l_bit_1 = d_metric_table_1_bit[0]; + return; + } + if (sym >= 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) roundf ((sym - d_min_sample) / d_delta); + *l_bit_0 = d_metric_table_0_bit[l_ndx]; + *l_bit_1 = d_metric_table_1_bit[l_ndx]; +} + +void code_metric_fl::convert +(size_t n_syms, + pdf_fcn_io_t* sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + for (size_t m = n_syms; m > 0; m--) + lookup (*sym++, (void*) l_bit_0++, (void*) l_bit_1++); +} + +code_metric_fs::code_metric_fs +(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) +{ + if (n_samples < 2) { + fprintf (stderr, "code_metric_fs:: n_samples " + "must be at least 2.\n"); + assert (0); + } + if (min_sample >= max_sample) { + fprintf (stderr, "code_metric_fs:: min_sample must be " + "less than max_sample.\n"); + assert (0); + } + if (! pdf_fcn_0_bit) { + fprintf (stderr, "code_metric_fs:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (! pdf_fcn_1_bit) { + fprintf (stderr, "code_metric_fs:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (sample_precision < 9 || sample_precision > 16) { + fprintf (stderr, "code_metric_fs:: sample_precision must be " + "between 9 and 16 for this class.\n"); + assert (0); + } + + d_sample_precision = sample_precision; + d_n_samples = n_samples; + d_max_sample = max_sample; + d_min_sample = min_sample; + d_delta = (max_sample - min_sample) / (n_samples - 1); + d_pdf_fcn_0_bit = pdf_fcn_0_bit; + d_pdf_fcn_1_bit = pdf_fcn_1_bit; + d_metric_table_0_bit.assign (n_samples, 0); + d_metric_table_1_bit.assign (n_samples, 0); + + // get the scale factor for converting from float to sample_precision + // maps: + // logf (pdf_fcn_0_bit->eval (d_min_sample)) -> l_min_map + // logf (pdf_fcn_0_bit->eval (d_max_sample)) -> l_max_map + + metric_t l_min_map = - (1 << (sample_precision - 1)); + + pdf_fcn_io_t l_min_log_val_0 = logf ((*pdf_fcn_0_bit)(d_min_sample)); + pdf_fcn_io_t l_max_log_val_0 = logf ((*pdf_fcn_0_bit)(d_max_sample)); + pdf_fcn_io_t l_slope_0 = (powf (2.0, (pdf_fcn_io_t)(d_sample_precision)) / + (l_max_log_val_0 - l_min_log_val_0)); + pdf_fcn_io_t l_min_log_val_1 = logf ((*pdf_fcn_1_bit)(d_min_sample)); + pdf_fcn_io_t l_max_log_val_1 = logf ((*pdf_fcn_1_bit)(d_max_sample)); + pdf_fcn_io_t l_slope_1 = (powf (2.0, (pdf_fcn_io_t)(d_sample_precision)) / + (l_max_log_val_1 - l_min_log_val_1)); + + pdf_fcn_io_t l_val = d_min_sample; + for (size_t m = 0; m < d_n_samples; m++) { + d_metric_table_0_bit[m] = + (metric_t) roundf (((pdf_fcn_io_t) l_min_map) + + (l_slope_0 * (logf ((*pdf_fcn_0_bit)(l_val)) - + l_min_log_val_0))); + d_metric_table_1_bit[m] = + (metric_t) roundf (((pdf_fcn_io_t) l_min_map) + + (l_slope_1 * (logf ((*pdf_fcn_1_bit)(l_val)) - + l_min_log_val_1))); + l_val += d_delta; + } +} + +void code_metric_fs::lookup +(pdf_fcn_io_t sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + if (sym <= d_min_sample) { + *l_bit_0 = d_metric_table_0_bit[0]; + *l_bit_1 = d_metric_table_1_bit[0]; + return; + } + if (sym >= 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) roundf ((sym - d_min_sample) / d_delta); + *l_bit_0 = d_metric_table_0_bit[l_ndx]; + *l_bit_1 = d_metric_table_1_bit[l_ndx]; +} + +void code_metric_fs::convert +(size_t n_syms, + pdf_fcn_io_t* sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + for (size_t m = n_syms; m > 0; m--) + lookup (*sym++, (void*) l_bit_0++, (void*) l_bit_1++); +} + +code_metric_fb::code_metric_fb +(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) +{ + if (n_samples < 2) { + fprintf (stderr, "code_metric_fb:: n_samples " + "must be at least 2.\n"); + assert (0); + } + if (min_sample >= max_sample) { + fprintf (stderr, "code_metric_fb:: min_sample must be " + "less than max_sample.\n"); + assert (0); + } + if (! pdf_fcn_0_bit) { + fprintf (stderr, "code_metric_fb:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (! pdf_fcn_1_bit) { + fprintf (stderr, "code_metric_fb:: pdf_fcn_0_bit must be " + "a non-null pointer to function.\n"); + assert (0); + } + if (sample_precision < 1 || sample_precision > 8) { + fprintf (stderr, "code_metric_fb:: sample_precision must be " + "between 1 and 8 for this class.\n"); + assert (0); + } + + d_sample_precision = sample_precision; + d_n_samples = n_samples; + d_max_sample = max_sample; + d_min_sample = min_sample; + d_delta = (max_sample - min_sample) / (n_samples - 1); + d_pdf_fcn_0_bit = pdf_fcn_0_bit; + d_pdf_fcn_1_bit = pdf_fcn_1_bit; + d_metric_table_0_bit.assign (n_samples, 0); + d_metric_table_1_bit.assign (n_samples, 0); + + // get the scale factor for converting from float to sample_precision + // maps: + // logf (pdf_fcn_0_bit->eval (d_min_sample)) -> l_min_map + // logf (pdf_fcn_0_bit->eval (d_max_sample)) -> l_max_map + + metric_t l_min_map = - (1 << (sample_precision - 1)); + + pdf_fcn_io_t l_min_log_val_0 = logf ((*pdf_fcn_0_bit)(d_min_sample)); + pdf_fcn_io_t l_max_log_val_0 = logf ((*pdf_fcn_0_bit)(d_max_sample)); + pdf_fcn_io_t l_slope_0 = (powf (2.0, (pdf_fcn_io_t)(d_sample_precision)) / + (l_max_log_val_0 - l_min_log_val_0)); + pdf_fcn_io_t l_min_log_val_1 = logf ((*pdf_fcn_1_bit)(d_min_sample)); + pdf_fcn_io_t l_max_log_val_1 = logf ((*pdf_fcn_1_bit)(d_max_sample)); + pdf_fcn_io_t l_slope_1 = (powf (2.0, (pdf_fcn_io_t)(d_sample_precision)) / + (l_max_log_val_1 - l_min_log_val_1)); + + pdf_fcn_io_t l_val = d_min_sample; + for (size_t m = 0; m < d_n_samples; m++) { + d_metric_table_0_bit[m] = + (metric_t) roundf (((pdf_fcn_io_t) l_min_map) + + (l_slope_0 * (logf ((*pdf_fcn_0_bit)(l_val)) - + l_min_log_val_0))); + d_metric_table_1_bit[m] = + (metric_t) roundf (((pdf_fcn_io_t) l_min_map) + + (l_slope_1 * (logf ((*pdf_fcn_1_bit)(l_val)) - + l_min_log_val_1))); + l_val += d_delta; + } +} + +void code_metric_fb::lookup +(pdf_fcn_io_t sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + if (sym <= d_min_sample) { + *l_bit_0 = d_metric_table_0_bit[0]; + *l_bit_1 = d_metric_table_1_bit[0]; + return; + } + if (sym >= 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) roundf ((sym - d_min_sample) / d_delta); + *l_bit_0 = d_metric_table_0_bit[l_ndx]; + *l_bit_1 = d_metric_table_1_bit[l_ndx]; +} + +void code_metric_fb::convert +(size_t n_syms, + pdf_fcn_io_t* sym, + void* bit_0, + void* bit_1) +{ + metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0; + metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1; + + for (size_t m = n_syms; m > 0; m--) + lookup (*sym++, (void*) l_bit_0++, (void*) l_bit_1++); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/code_metrics.h b/gr-error-correcting-codes/src/lib/libecc/code_metrics.h new file mode 100644 index 000000000..9530dd640 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/code_metrics.h @@ -0,0 +1,155 @@ +/* -*- 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_METRIC_H +#define INCLUDED_CODE_METRIC_H + +#include <sys/types.h> +#include <vector> + +class code_metrics +{ +public: + typedef float pdf_fcn_io_t; + + code_metrics () {}; + virtual ~code_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; + + virtual void convert (size_t n_syms, + pdf_fcn_io_t* syms, + void* bit_0, + void* bit_1) = 0; +}; + +class code_metric_ff : public code_metrics +{ + typedef pdf_fcn_io_t (*pdf_fcn_t) (pdf_fcn_io_t); + typedef float metric_t, *metric_ptr_t; + +private: + 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<metric_t> d_metric_table_0_bit; + std::vector<metric_t> d_metric_table_1_bit; + +public: + code_metric_ff (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); + ~code_metric_ff () {}; + + 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); +}; + +class code_metric_fl : public code_metrics +{ + typedef float pdf_fcn_io_t; + typedef pdf_fcn_io_t (*pdf_fcn_t) (pdf_fcn_io_t); + typedef long metric_t, *metric_ptr_t; + +private: + char d_sample_precision; + size_t d_n_samples, d_sample_mask; + 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<metric_t> d_metric_table_0_bit; + std::vector<metric_t> d_metric_table_1_bit; + +public: + code_metric_fl (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 = 32); + ~code_metric_fl () {}; + + 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); +}; + +class code_metric_fs : public code_metrics +{ + typedef float pdf_fcn_io_t; + typedef pdf_fcn_io_t (*pdf_fcn_t) (pdf_fcn_io_t); + typedef short metric_t, *metric_ptr_t; + +private: + char d_sample_precision; + size_t d_n_samples, d_sample_mask; + 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<metric_t> d_metric_table_0_bit; + std::vector<metric_t> d_metric_table_1_bit; + +public: + code_metric_fs (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 = 16); + ~code_metric_fs () {}; + + 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); +}; + +class code_metric_fb : public code_metrics +{ + typedef float pdf_fcn_io_t; + typedef pdf_fcn_io_t (*pdf_fcn_t) (pdf_fcn_io_t); + typedef char metric_t, *metric_ptr_t; + +private: + char d_sample_precision; + size_t d_n_samples, d_sample_mask; + 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<metric_t> d_metric_table_0_bit; + std::vector<metric_t> d_metric_table_1_bit; + +public: + code_metric_fb (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 = 8); + ~code_metric_fb () {}; + + 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); +}; + +#endif /* INCLUDED_CODE_METRIC_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/code_types.h b/gr-error-correcting-codes/src/lib/libecc/code_types.h new file mode 100644 index 000000000..cc7714358 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/code_types.h @@ -0,0 +1,31 @@ +/* + * 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_TYPES_H +#define INCLUDED_CODE_TYPES_H + +#include <sys/types.h> + +// the following is the type used for encoder memory + +typedef unsigned long memory_t, *memory_ptr_t; + +#endif /* INCLUDED_CODE_TYPES_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder.cc b/gr-error-correcting-codes/src/lib/libecc/decoder.cc new file mode 100644 index 000000000..0b77f779e --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder.cc @@ -0,0 +1,117 @@ +/* -*- 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.h> +#include <assert.h> +#include <iostream> + +#define DO_PRINT_DEBUG 1 + +#if DO_PRINT_DEBUG +#include <mld/n2bs.h> +#endif + +/* + * decode a certain number of output bits + * + * the 'in_buf' and 'out_buf' must have enough memory to handle the + * number of input metrics and output bits; no error checking is done! + * + * n_bits_to_output: the number of bits per output stream to output. + * + * returns the actual number of metrics used per input stream. + */ + +size_t +decoder::decode +(const char** in_buf, + char** out_buf, + size_t n_bits_to_output) +{ + // set the class-internal number of input metrics + // and output bits left to decode + + size_t saved_n_input_metrics; + saved_n_input_metrics = d_n_input_metrics_left = + compute_n_input_metrics (n_bits_to_output); + d_n_output_bits_left = n_bits_to_output; + + // call the private decode function + + decode_private (in_buf, out_buf); + + if (DO_PRINT_DEBUG) { + std::cout << "n_input_metrics_used = " << + (saved_n_input_metrics - d_n_input_metrics_left) << "\n" + "n_output_bits_used = " << + (n_bits_to_output - d_n_output_bits_left) << '\n'; + } + + // return the actual number of input metrics used + + return (saved_n_input_metrics - d_n_input_metrics_left); +} + +/* + * decode a certain number of input metrics + * + * the 'in_buf' and 'out_buf' must have enough memory to handle the + * number of input metrics and output bits; no error checking is done! + * + * n_metrics_to_input: the number of metrics per input stream to decode + * + * returns the actual number of bits written per output stream + */ + +size_t +decoder::decode +(const char** in_buf, + size_t n_metrics_to_input, + char** out_buf) +{ + // set the class-internal number of input metrics and + // output bits left to decode + + size_t saved_n_output_bits; + saved_n_output_bits = d_n_output_bits_left = + compute_n_output_bits (n_metrics_to_input); + d_n_input_metrics_left = n_metrics_to_input; + + // call the private decode function + + decode_private (in_buf, out_buf); + + if (DO_PRINT_DEBUG) { + std::cout << "n_input_metrics_used = " << + (n_metrics_to_input - d_n_input_metrics_left) << '\n'; + std::cout << "n_output_bits_used = " << + (saved_n_output_bits - d_n_output_bits_left) << '\n'; + } + + // return the actual number of output bits written + + return (saved_n_output_bits - d_n_output_bits_left); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder.h b/gr-error-correcting-codes/src/lib/libecc/decoder.h new file mode 100644 index 000000000..76a24b20a --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder.h @@ -0,0 +1,59 @@ +/* -*- 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_H +#define INCLUDED_DECODER_H + +#include "code_types.h" + +// the 'decoder' class is a virtual class upon which all decoder types +// can be built. + +class decoder +{ +public: + decoder () {}; + virtual ~decoder () {}; + + virtual size_t compute_n_input_metrics (size_t n_output_bits) = 0; + virtual size_t compute_n_output_bits (size_t n_input_metrics) = 0; + virtual size_t decode (const char** in_buf, + char** out_buf, + size_t n_bits_to_output); + virtual size_t decode (const char** in_buf, + size_t n_metrics_to_input, + char** out_buf); + +protected: + virtual void decode_private (const char** in_buf, char** out_buf) = 0; + virtual char get_next_input (const char** in_buf, size_t code_input_n) = 0; + virtual void output_bit (char t_out_bit, char** out_buf, + size_t t_output_stream) = 0; + + size_t d_block_size_bits, d_n_code_inputs, d_n_code_outputs; + size_t d_n_dec_bits; + size_t d_in_buf_ndx, d_out_buf_ndx; + size_t d_in_bit_shift, d_out_bit_shift; + size_t d_n_input_metrics_left, d_n_output_bits_left; +}; + +#endif /* INCLUDED_DECODER_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc new file mode 100644 index 000000000..bce2cacb2 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.cc @@ -0,0 +1,1060 @@ +/* -*- 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.h> +#include <assert.h> +#include <iostream> + +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 + +#if DO_TIME_THOUGHPUT +#include <mld/mld_timer.h> +#endif +#if DO_PRINT_DEBUG +#include <mld/n2bs.h> +#endif + +decoder_viterbi::decoder_viterbi +(int sample_precision, + encoder_convolutional* l_encoder) +{ + // make sure the sample precitions makes sense + + if ((sample_precision < 0) | (sample_precision > 32)) { + std::cerr << "decoder_viterbi: " + "Requested sample_precision (" << sample_precision << + "must be between 0 and 32.\n"; + assert (0); + } + + // make sure that the encoder is "valid" + + if (! l_encoder) { + std::cerr << "decoder_viterbi: Error: Encoder is a NULL pointer.\n"; + assert (0); + } + + // keep around a pointer to the encoder + + d_encoder = l_encoder; + + // fill the class variables + + d_block_size_bits = d_encoder->block_size_bits (); + d_do_streaming = (d_block_size_bits == 0); + 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 (); +#if 0 + d_total_memory = d_encoder->total_memory (); +#endif + + // NOTE: d_n_states is a 'long', and thus is quite limited in terms + // of max memory and # of input streams to 2^32 states This is OK, + // since that many states would be impossibly slow to decode! might + // make this a "long long" (64 bits) in the future + + d_n_states = 1 << d_total_memory; + d_n_input_combinations = 1 << d_n_code_inputs; + + // 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. + + 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_streaming = " << + ((d_do_streaming == true) ? "true" : "false") << "\n" << + "d_do_termination = " << + ((d_do_termination == true) ? "true" : "false") << "\n" << + "d_total_memory = " << d_total_memory << "\n" << + "d_n_states = " << d_n_states << "\n" << + "d_n_input_combinations = " << d_n_input_combinations << "\n"; + } + + // always start the fsm in the "init" state + + d_fsm_state = fsm_dec_viterbi_init; + + // create a vector of indexes to states when doing "up" or "termination"; + + d_up_term_states_ndx[0] = new size_t [d_n_states]; + d_up_term_states_ndx[1] = new size_t [d_n_states]; + + // get the total number of out bits per stream + + d_n_total_inputs_per_stream = d_block_size_bits; + if (d_do_termination == true) + d_n_total_inputs_per_stream += d_max_memory; + + + +} + +decoder_viterbi::~decoder_viterbi +() +{ + // reverse over from allocation + + delete [] d_up_term_states_ndx[0]; + delete [] d_up_term_states_ndx[1]; + + // delete the state's structures + + 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; + } + 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; + } + delete [] d_states[1]; + + // delete the save buffer + + char** t_save_buffer = d_save_buffer; + for (size_t n = 0; n < d_n_code_inputs; n++) { + delete [] (*t_save_buffer++); + } + delete [] d_save_buffer; +} + +void +decoder_viterbi::reset_metrics +(u_char which) +{ + 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 + } +} + +void +decoder_viterbi::zero_metrics +(u_char which) +{ + 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 + } +} + +//FIXME + +char +decoder_viterbi::get_next_input +(const char** in_buf, +size_t code_input_n) +{ + return (0); +} + +void +decoder_viterbi::decode_private +(const char** in_buf, + char** out_buf) +{ +#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_memory + 1; + size_t t_mem_print_bits = d_max_memory + 2; +#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_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 + +// 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); + } +// 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 DO_PRINT_DEBUG_FSM + std::cout << "Starting fsm_dec_viterbi_doing_up\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_max_memory) & + (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_max_memory = " << d_max_memory << "\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_max_memory) { +#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 + 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. + +// 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_max_memory - (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_max_memory - t_time_count + 1) << + " of " << d_max_memory << "; 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. + +// 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 + +// 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_max_memory << " bit" << + ((d_max_memory != 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_max_memory; 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. + +// 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 + } +// done (while) there are inputs + } + +// 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); + +// 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); + } + 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 + } + +#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 +} diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h new file mode 100644 index 000000000..66a6ba405 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi.h @@ -0,0 +1,189 @@ +/* -*- 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_H +#define INCLUDED_DECODER_VITERBI_H + +#include "decoder.h" +#include "encoder_convolutional.h" + +class decoder_viterbi : public decoder +{ +public: +/*! + * \brief Decode the incoming metrics streams using the Viterbi algorithm. + * + * 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). + */ + + decoder_viterbi (int sample_precision, + encoder_convolutional* l_encoder); + + virtual ~decoder_viterbi (); + +protected: + struct state_t; + +/* + * connection_t: describes an output connection from the current + * time-bit memory state to the next time-bit memory state + * + * d_to: state pointer to which this connection going + * + * d_to_ndx: index of the "to" state + * + * d_output_bits: what are the output bits, coverted into + * 1->+1.0, 0->-1.0, for this connection + */ + + typedef struct connection_t { + struct state_t *d_to; + int d_to_ndx; + float* d_output_bits; + } connection_t, *connection_t_ptr; + +/* + * 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 + */ + + typedef struct state_t { + connection_t_ptr d_connections; + float d_max_metric; + int d_max_state_ndx; + int d_max_input; + } state_t, *state_t_ptr; + +/* + * 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)));}; + +/* + * 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 + */ + + enum fsm_dec_viterbi_t { + fsm_dec_viterbi_init, fsm_dec_viterbi_doing_up, + fsm_dec_viterbi_doing_middle, fsm_dec_viterbi_doing_term + }; + + virtual void decode_private (const char** in_buf, char** out_buf); + virtual char get_next_input (const char** in_buf, size_t code_input_n); +#if 0 + virtual void decode_loop (const char** in_buf, char** out_buf, + size_t* which_counter, size_t how_many); + + virtual char get_next_input__up (const char** in_buf, + size_t code_input_n) = 0; + virtual char get_next_input__middle (const char** in_buf, + size_t code_input_n) = 0; + virtual char get_next_input__term (size_t code_input_n) = 0; +#endif + virtual void increment_input_indices (bool while_decoding) = 0; + virtual void increment_output_indices (bool while_decoding) = 0; + 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; + fsm_dec_viterbi_t d_fsm_state; + size_t d_max_memory, d_total_memory; + size_t d_time_count, d_n_total_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; + size_t d_states_ndx, d_up_term_ndx; + bool d_do_streaming, d_do_termination; + std::vector<memory_t> d_init_states, d_term_states; + char **d_save_buffer; + state_t_ptr d_states[2]; + size_t* d_up_term_states_ndx[2]; +}; + +#endif /* INCLUDED_DECODER_VITERBI_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.cc b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.cc new file mode 100644 index 000000000..308d2775b --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.cc @@ -0,0 +1,1120 @@ +/* -*- 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_full_block.h" +#include <assert.h> +#include <iostream> +#include <math.h> + +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_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 1 + +#if DO_TIME_THOUGHPUT +#include <mld/mld_timer.h> +#endif +#if DO_PRINT_DEBUG +#include <mld/n2bs.h> +#endif + +decoder_viterbi_full_block::decoder_viterbi_full_block +(int sample_precision, + encoder_convolutional* l_encoder) + : decoder_viterbi (sample_precision, l_encoder) +{ + // verify that the block size is non-zero + + if (d_block_size_bits == 0) { + std::cerr << "decoder_viterbi_full_block: Error: " + "Block size is 0, and must be positive for block decoding.\n"; + assert (0); + } + + // the traceback buffers are specific to the type of decoding + // (full/block, partial/block, partial/stream) + + // create the traceback buffers; for full/block, use the total # of + // bits to decode + 1: each bit is represented by a transition + // between traceback elements. + + d_n_traceback_els = d_n_total_inputs_per_stream + 1; + + // create the output buffers: + // this is a 2d matrix structure, where the first dimension + // is the number of output bits; the second dimension is + // the number of states. + // When doing full blocks, each bit-time's state's traceback + // contains just the pointer to the previous bit-time's state's traceback + // as well as the inputs for that connection. + // No further work is required because each reverse-path is unique + // once a given end-bit-time's state is determined to be "the one". + + traceback_t_hdl t_out_buf = + d_out_buf = new traceback_t_ptr [d_n_traceback_els]; + for (size_t n = d_n_traceback_els; n > 0; n--) { + (*t_out_buf++) = new traceback_t [d_n_states]; + } + + if (DO_PRINT_DEBUG_INST) { + std::cout << + "total # in bits / stream = " << d_n_total_inputs_per_stream << "\n" << + "d_n_traceback_els = " << d_n_traceback_els << "\n"; + } + + if (DO_PRINT_DEBUG_INST) { + traceback_t_hdl t_out_bufs = d_out_buf; + for (size_t n = 0; n < d_n_traceback_els; n++, *t_out_bufs++) { + traceback_t_ptr t_out_buf = *t_out_bufs; + for (size_t m = 0; m < d_n_states; m++, t_out_buf++) { + std::cout << "tb[" << n << "] = " << t_out_bufs << + ", &tb[" << n << "][" << m << "] = " << (&d_out_buf[n][m]) << + ", tb[" << n << "," << m << "] = " << t_out_buf << "\n"; + } + } + } +} + +decoder_viterbi_full_block::~decoder_viterbi_full_block +() +{ + // delete the traceback buffers + + traceback_t_hdl t_out_buf = d_out_buf; + for (size_t n = d_n_traceback_els; n > 0; n--) { + delete [] (*t_out_buf++); + } + delete [] d_out_buf; +} + +void +decoder_viterbi_full_block::update_traceback__up +(size_t from_state_ndx, + size_t to_state_ndx, + size_t l_input) +{ +#if 0 +#if DO_PRINT_DEBUG + size_t t_state_print_bits = d_total_memory + 1; + size_t t_mem_print_bits = d_max_memory + 2; +#endif + // update the traceback structure, depending on which variety it is + // doing full trellis before decoding; use d_out_buf + + // get the current state & output state + + traceback_t_ptr t_out_buf = &(d_out_buf[d_time_count] + [from_state_ndx]); + traceback_t_ptr t_next_out_buf = &(d_out_buf[d_time_count+1] + [to_state_ndx]); + if (DO_PRINT_DEBUG_UP_1) { + std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n" << + "ndx[" << n << "] == " << from_state_ndx << + ", s[" << n2bs(from_state_ndx,t_state_print_bits) << + "]: max_ndx = " << + n2bs(t_state->d_max_state_ndx,t_state_print_bits) << + ", input = " << n2bs(l_input, d_n_code_inputs+1) << + ": " << t_next_out_buf << " => " << t_out_buf << "\n"; + } + + // 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 = l_input; +#endif +} + +void +decoder_viterbi_full_block::update_traceback__middle +() +{ +#if 0 + +#if DO_PRINT_DEBUG + size_t t_state_print_bits = d_total_memory + 1; + size_t t_mem_print_bits = d_max_memory + 2; +#endif + // 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 + + state_t_ptr 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"; + } + + 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"; + } + + t_out_buf->d_prev = t_prev_out_buf; + t_out_buf->d_inputs = t_state->d_max_input; + } + +#endif +} + +void +decoder_viterbi_full_block::update_traceback__term +() +{ +#if 0 + +#if DO_PRINT_DEBUG + size_t t_state_print_bits = d_total_memory + 1; + size_t t_mem_print_bits = d_max_memory + 2; +#endif +// 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 + } + +#endif +} + +void +decoder_viterbi_full_block::decode_private +(const char** in_buf, + char** out_buf) +{ +#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_memory + 1; + size_t t_mem_print_bits = d_max_memory + 2; +#endif +// setup variables for quicker access + int t_in_buf_ndx = 0, t_out_buf_ndx = 0; + int t_out_bit_shift = 0; + int t_ninput_items = fixed_rate_noutput_to_ninput (noutput_items); + int t_noutput_bytes = noutput_items * d_out_stream_el_size_bytes; + +#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 + +// 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); + } +// 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 == fsm_dec_init ? "init" : + (d_fsm == fsm_dec_doing_up ? "up" : + (d_fsm == fsm_dec_doing_middle ? "middle" : + (d_fsm == fsm_dec_doing_term ? "term" : + (d_fsm == fsm_dec_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 == fsm_dec_init ? "init" : + (d_fsm == fsm_dec_doing_up ? "up" : + (d_fsm == fsm_dec_doing_middle ? "middle" : + (d_fsm == fsm_dec_doing_term ? "term" : + (d_fsm == fsm_dec_output ? "output" : "unknown"))))) << "'\n"; +#endif +// jump to the correct state in the fsm + switch (d_fsm) { + case fsm_dec_doing_up: +#if DO_PRINT_DEBUG_FSM + std::cout << "Starting fsm_dec_doing_up\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_max_memory) & + (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_max_memory = " << d_max_memory << "\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 + + update_traceback__up (t_state, t_to_state, q); + + // next (for) input value + } + + // next (for) "up_term" state + } + + // increment the input buffer indices + + increment_input_indices (false); + + // increment the time counter + + d_time_count++; + + // change which up-term index to use + + d_up_term_ndx ^= 1; + + // increase the number of states to be used + + t_n_up_down_ndx <<= d_n_code_inputs; + + // change which d_states' index to use as starting + + d_states_ndx ^= 1; + + // next (while) input + } + + // if reached the end of doing the "up" part of the trellis, + // switch states into the middle + + if (d_time_count == d_max_memory) { + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Setting FSM to fsm_dec_doing_middle\n"; + } + d_fsm = fsm_dec_doing_middle; + } + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Exited fsm_dec_doing_up\n"; + } + break; + + case (fsm_dec_doing_middle): + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Entered fsm_dec_doing_middle\n"; + } + + // stay in this state until a full block (+ optional + // termination) of input metrics is reached, or until there are + // no more input metrics to parse + + while ((d_time_count < d_block_size_bits) & + (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. + + // 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 << "\nd_states_ndx = " << d_states_ndx << "\n"; + } + + // 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"; + } + + 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"; + } + + // 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"; + } + 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; + } + // next (for) input value + } + // next (for) state + } + + // done with all states and all inputs; + // update the traceback buffers + + update_traceback__middle (); + + // increment the input buffer indices + + increment_input_indices (); + + // increment the time counter + + d_time_count++; + + // check (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_doing_term\n"; + } + d_fsm = fsm_dec_doing_term; + } + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Exited fsm_dec_doing_middle\n"; + } + break; + + case (fsm_dec_doing_term): + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Entered fsm_dec_doing_term\n"; + } + + // set the "next" up_down index to the end of their states + + size_t t_time_count = d_max_memory - (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 metrics + // are reached; exit if we run out of input metrics to process + + while ((t_time_count > 0) & + (t_in_buf_ndx < t_ninput_items)) { + + if (DO_PRINT_DEBUG_TERM) { + std::cout << "Doing time " << (d_max_memory - t_time_count + 1) << + " of " << d_max_memory << "; starting buf[" << t_in_buf_ndx << + "] of [" << t_ninput_items << "]\n"; + } + + // FIXME: loop over just the "0" inputs + + // use the "to" states, and compute the metric for each, + // compare & store it in the "to" state at the end of the + // connection. + + // 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"; + } + + // 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"; + } + 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 + } + + // update the traceback buffers + + update_traceback__term (); + increment_input_indices (false); + + // 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_output\n"; + } + d_fsm = fsm_dec_output; + } + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Exited fsm_dec_doing_term\n"; + } + break; + + case (fsm_dec_output): + if (DO_PRINT_DEBUG_FSM) { + std::cout << "Entered fsm_dec_output.\n"; + } + + // 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 + + // 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_max_memory << " bit" << + ((d_max_memory != 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_max_memory; 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_init\n"; +#endif + d_fsm = fsm_dec_init; +#if DO_PRINT_DEBUG_FSM + std::cout << "Exited fsm_dec_output\n"; +#endif + break; + case (fsm_dec_init): +#if DO_PRINT_DEBUG_FSM + std::cout << "Entered fsm_dec_init\n"; +#endif +// this is called immediately (first input bit upon startup), +// or after termination of a trellis. + +// 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_doing_up\n"; +#endif + d_fsm = fsm_dec_doing_up; +#if DO_PRINT_DEBUG_FSM + std::cout << "Exited fsm_dec_init\n"; +#endif + break; +// should never get here! + default: + assert (0); +// done (switch) with FSM + } +// done (while) there are inputs + } + +// 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 == fsm_dec_init ? "init" : + (d_fsm == fsm_dec_doing_up ? "up" : + (d_fsm == fsm_dec_doing_middle ? "middle" : + (d_fsm == fsm_dec_doing_term ? "term" : + (d_fsm == fsm_dec_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); + +// 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); + } + 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 + } + +#endif + +#if DO_TIME_THOUGHPUT + u_long d_t = end_timer (&t_tp); + + std::cout << "decoder_viterbi_full_block: Completed " << t_ninput_items << + " bits in " << d_t << " usec => " << + 1e6*(((double)(t_ninput_items))/((double) d_t)) << + " b/s\n"; +#endif +} diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.h b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.h new file mode 100644 index 000000000..531b7a6c6 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block.h @@ -0,0 +1,78 @@ +/* -*- 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_FULL_BLOCK_H +#define INCLUDED_DECODER_VITERBI_FULL_BLOCK_H + +#include "decoder_viterbi.h" + +class decoder_viterbi_full_block : public decoder_viterbi +{ +/*! + * \brief Decode the incoming streams using a Viterbi-style decoder, + * doing full trellis block decoding before putting out + * any bits + * + * input: streams of metrics, two per code output: one for the 0-bit + * metrics and the other for the 1-bit metric. + * + * output: stream(s) of output bits + */ + +public: + decoder_viterbi_full_block (int sample_precision, + encoder_convolutional* l_encoder); + + virtual ~decoder_viterbi_full_block (); + +protected: + virtual void decode_private (const char** in_buf, char** out_buf); + virtual void update_traceback__up (size_t from_state_ndx, + size_t to_state_ndx, + size_t l_input); + virtual void update_traceback__middle (); + virtual void update_traceback__term (); + +/* + * traceback_t: used to store all encode-input bits for + * all possible paths, when computing all trellis bits before + * determining the ML decode-output sequence. + * + * d_prev: the connection to the previous bit's traceback structure + * + * d_inputs: the inputs (one per bit) for this connection + */ + + typedef struct traceback_t { + struct traceback_t *d_prev; + int d_inputs; + } traceback_t, *traceback_t_ptr, **traceback_t_hdl; + +/* + * d_n_total_inputs_per_stream: how many bits to store for each + * state to determine the best decoder-output (encoder-input) bits + */ + size_t d_n_inputs_per_stream; + traceback_t_hdl d_out_buf; +}; + +#endif /* INCLUDED_DECODER_VITERBI_FULL_BLOCK_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block_i1_ic1.cc b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block_i1_ic1.cc new file mode 100644 index 000000000..b0fc4f364 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block_i1_ic1.cc @@ -0,0 +1,162 @@ +/* -*- 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_full_block_i1_ic1.h" +#include <assert.h> +#include <iostream> +#include <math.h> + +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_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 1 + +#if DO_TIME_THOUGHPUT +#include <mld/mld_timer.h> +#endif +#if DO_PRINT_DEBUG +#include <mld/n2bs.h> +#endif + +// FIXME + +size_t +decoder_viterbi_full_block_i1_ic1::compute_n_output_bits +(size_t n_input_items) +{ + assert (0); + return (0); +} + +/* + * Compute the number of input items (metrics) needed to produce + * 'noutput' bits. For convolutional decoders, there is 1 + * bit output per metric input per stream, with the addition of a some + * metrics for trellis termination if selected. Without termination, + * there is exactly 1:1 input to output (1 metric in to 1 bit out), + * no matter the encoding type. + * + * if (not terminating), then get the number of output bits. + * + * otherwise, find the number of blocks (not necessarily an integer), + * and then compute the number of input metrics (including termination) + * required to produce those blocks. Subtract the number of bits + * leftover from the previous computation, then find the number of input + * metrics, ceil'd to make sure there are enough. + */ + +size_t +decoder_viterbi_full_block_i1_ic1::compute_n_input_metrics +(size_t n_output_bits) +{ + int t_ninput_items = 0; + int t_noutput_bits = ((int) n_output_bits) - ((int) d_n_saved_bits); + + // if there are enough saved bits, just use those, no inputs required + + if (t_noutput_bits <= 0) + return (0); + + // remove any bits already in the decoding trellis + + if (d_time_count != 0) { + int t_time_bits = ((d_time_count > d_block_size_bits) ? 0 : + d_block_size_bits - d_time_count); + t_noutput_bits -= t_time_bits; + t_ninput_items += t_time_bits; + } + // if completing this trellis doesn't create enough outputs ... + + if (t_noutput_bits > 0) { + + // there is a 1:1 ratio between input symbols and output bits (per + // stream), except for termination bits which are already taken + // into account in the total # of input bits per stream class + // variable; need to round the # output bits to the + + // find the number of blocks, ceil'd to the next higher integer + + int t_nblocks = (int) ceilf (((float) t_noutput_bits) / + ((float) d_block_size_bits)); + + // find the number of required input bits + + t_ninput_items += t_nblocks * d_n_total_inputs_per_stream; + } + + return (t_ninput_items); +} + +// FIXME, from here down dummies to get correct compiling; for testing +// purposes only. + +void +decoder_viterbi_full_block_i1_ic1::increment_input_indices +(bool while_decoding) +{ + if (while_decoding) + std::cout << "foo!"; + +#if 0 +// 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; +#endif +} + +void +decoder_viterbi_full_block_i1_ic1::increment_output_indices +(bool while_decoding) +{ + if (while_decoding) + std::cout << "bar!"; +} + +void +decoder_viterbi_full_block_i1_ic1::output_bit +(char t_out_bit, + char** out_buf, + size_t t_output_stream) +{ + if (t_out_bit) + std::cout << "mop!"; +} diff --git a/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block_i1_ic1.h b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block_i1_ic1.h new file mode 100644 index 000000000..a7afeb396 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/decoder_viterbi_full_block_i1_ic1.h @@ -0,0 +1,66 @@ +/* -*- 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_FULL_BLOCK_IC1_H +#define INCLUDED_DECODER_VITERBI_FULL_BLOCK_IC1_H + +#include "decoder_viterbi_full_block.h" + +class decoder_viterbi_full_block_i1_ic1 : public decoder_viterbi_full_block +{ +/*! + * class decoder_viterbi_full_block_i1_ic1 : + * public decoder_viterbi_full_block + * + * Decode the incoming metrics using a Viterbi-style decoder, doing + * full trellis block decoding before putting out any bits + * + * input is "i1": one stream per input (as defined by the + * code-output), with one metric per input item. + * + * output is "ic1": streams of char, one stream per output (as defined + * by the code-input), using only the right-most justified (LSB?) + * bit as the single output bit per output item. + * + * The rest of the options are outlined in the inherited classes' + * header files. + */ + +public: + inline decoder_viterbi_full_block_i1_ic1 + (int sample_precision, + encoder_convolutional* l_encoder) + : decoder_viterbi_full_block (sample_precision, l_encoder) {}; + + virtual ~decoder_viterbi_full_block_i1_ic1 () {}; + + virtual size_t compute_n_input_metrics (size_t n_output_bits); + virtual size_t compute_n_output_bits (size_t n_input_metrics); + +protected: + virtual void increment_input_indices (bool while_decoding); + virtual void output_bit (char t_out_bit, char** out_buf, + size_t t_output_stream); + virtual void increment_output_indices (bool while_decoding); +}; + +#endif /* INCLUDED_DECODER_VITERBI_FULL_BLOCK_I1_IC1_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder.cc b/gr-error-correcting-codes/src/lib/libecc/encoder.cc new file mode 100644 index 000000000..5bc97e7fc --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder.cc @@ -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. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <encoder.h> +#include <iostream> + +#define DO_PRINT_DEBUG 0 + +/* + * encode a certain number of output bits + * + * the 'in_buf' and 'out_buf' must have enough memory to handle the + * number of input and output bits; no error checking is done! + * + * n_bits_to_output: the number of bits per output stream to encode + * + * returns the actual number of bits used per input stream + */ + +size_t +encoder::encode +(const char** in_buf, + char** out_buf, + size_t n_bits_to_output) +{ + if (DO_PRINT_DEBUG) { + std::cout << "encode{out}(): Starting:"; + } + + // set the class-internal number of input bits and + // output bits left to encode + + size_t saved_n_input_bits; + saved_n_input_bits = d_n_input_bits_left = + compute_n_input_bits (n_bits_to_output); + d_n_output_bits_left = n_bits_to_output; + + if (DO_PRINT_DEBUG) { + std::cout << + "# output bits provided = " << d_n_output_bits_left << "\n" + "# input bits computed = " << d_n_input_bits_left << "\n"; + } + + // call the private encode function + + encode_private (in_buf, out_buf); + + if (DO_PRINT_DEBUG) { + std::cout << + "n_input_bits_used = " << + (saved_n_input_bits - d_n_input_bits_left) << "\n" + "n_output_bits_used = " << + (n_bits_to_output - d_n_output_bits_left) << '\n'; + } + + // return the actual number of input bits used + + return (saved_n_input_bits - d_n_input_bits_left); +} + +/* + * encode a certain number of input bits + * + * the 'in_buf' and 'out_buf' must have enough memory to handle the + * number of input and output bits; no error checking is done! + * + * n_bits_to_input: the number of bits per input stream to encode + * + * returns the actual number of bits written per output stream + */ + +size_t +encoder::encode +(const char** in_buf, + size_t n_bits_to_input, + char** out_buf) +{ + // set the class-internal number of input and + // output bits left to encode + + size_t saved_n_output_bits; + saved_n_output_bits = d_n_output_bits_left = + compute_n_output_bits (n_bits_to_input); + d_n_input_bits_left = n_bits_to_input; + + // call the private encode function + + encode_private (in_buf, out_buf); + + if (DO_PRINT_DEBUG) { + std::cout << "n_input_bits_used = " << + (n_bits_to_input - d_n_input_bits_left) << '\n'; + std::cout << "n_output_bits_used = " << + (saved_n_output_bits - d_n_output_bits_left) << '\n'; + } + + // return the actual number of output bits written + + return (saved_n_output_bits - d_n_output_bits_left); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder.h b/gr-error-correcting-codes/src/lib/libecc/encoder.h new file mode 100644 index 000000000..2c3dde13a --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder.h @@ -0,0 +1,72 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef INCLUDED_ENCODER_H +#define INCLUDED_ENCODER_H + +#include "code_types.h" + +// the 'encoder' class is a virtual class upon which all encoder types +// can be built. + +class encoder +{ +public: + encoder () {}; + virtual ~encoder () {}; + + virtual size_t compute_n_input_bits (size_t n_output_bits) = 0; + virtual size_t compute_n_output_bits (size_t n_input_bits) = 0; + virtual size_t encode (const char** in_buf, + char** out_buf, + size_t n_bits_to_output); + virtual size_t encode (const char** in_buf, + size_t n_bits_to_input, + char** out_buf); + +/* for remote access to internal info */ + + inline size_t block_size_bits () {return (d_block_size_bits);}; + inline size_t n_code_inputs () {return (d_n_code_inputs);}; + inline size_t n_code_outputs () {return (d_n_code_outputs);}; + +protected: + /* encode_private: encode the given in_buf and write the output bits + * to the out_buf, using internal class variables. This function is + * called from the publically available "encode()" methods, which + * first set the internal class variables before executing. + */ + + virtual void encode_private (const char** in_buf, char** out_buf) = 0; + + /* inheriting methods need to figure out what makes the most sense + * for them in terms of getting new inputs and writing outputs. + */ + + size_t d_block_size_bits, d_n_code_inputs, d_n_code_outputs; + size_t d_n_enc_bits, d_total_n_enc_bits; + size_t d_in_buf_ndx, d_out_buf_ndx; + size_t d_in_bit_shift, d_out_bit_shift; + size_t d_n_input_bits_left, d_n_output_bits_left; +}; + +#endif /* INCLUDED_ENCODER_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc new file mode 100644 index 000000000..b7bd87de0 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.cc @@ -0,0 +1,290 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include "encoder_convolutional.h" +#include <assert.h> +#include <iostream> + +#define DO_TIME_THOUGHPUT 0 +#define DO_PRINT_DEBUG 1 + +#include <mld/mld_timer.h> +#include <mld/n2bs.h> + +static const int g_max_block_size_bits = 10000000; +static const int g_max_num_streams = 10; +static const int g_num_bits_per_byte = 8; + +void encoder_convolutional::encoder_convolutional_init +(int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int>& code_generators, + const std::vector<int>* code_feedback, + bool do_termination, + int start_memory_state, + int end_memory_state) +{ + // error checking on the input arguments is done by the trellis class + + if (code_feedback) + d_trellis = new code_convolutional_trellis + (block_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + *code_feedback, + do_termination, + end_memory_state); + else + d_trellis = new code_convolutional_trellis + (block_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + do_termination, + end_memory_state); + + // set the initial FSM state to 'init' + + d_fsm_state = fsm_enc_conv_init; + + // create the class block variables + + d_block_size_bits = block_size_bits; + d_n_code_inputs = n_code_inputs; + d_n_code_outputs = n_code_outputs; + d_do_streaming = d_trellis->do_streaming (); + d_do_termination = d_trellis->do_termination (); + d_total_n_delays = d_trellis->total_n_delays (); + + // parse the init state + + memory_t t_mask = (memory_t)((2 << d_total_n_delays) - 1); + size_t t_n_states = (1 << d_total_n_delays); + + if (start_memory_state & t_mask) { + std::cout << "encoder_convolutional: Warning: " << + "provided end memory state out (" << end_memory_state << + ") is out of the state range [0, " << + (t_n_states-1) << "]; masking off the unused bits.\n"; + + start_memory_state &= t_mask; + } + + d_init_state = start_memory_state; + + d_current_inputs.assign (d_n_code_inputs, 0); + d_current_outputs.assign (d_n_code_outputs, 0); +} + +void +encoder_convolutional::encode_private +(const char** in_buf, + char** out_buf) +{ + struct timeval t_tp; + if (DO_TIME_THOUGHPUT) { + start_timer (&t_tp); + } + + // reset buffer indices + + d_total_n_enc_bits = d_in_buf_ndx = d_out_buf_ndx = + d_in_bit_shift = d_out_bit_shift = 0; + + if (DO_PRINT_DEBUG) { + std::cout << "Beginning this encode() call; starting parameters.\n"; + std::cout << "d_n_input_bits_left = " << d_n_input_bits_left << '\n'; + std::cout << "d_n_output_bits_left = " << d_n_output_bits_left << '\n'; + } + + // while there are inputs and outputs left to process ... + + while ((d_n_input_bits_left != 0) & (d_n_output_bits_left != 0)) { + + // jump to the correct state in the fsm + + switch (d_fsm_state) { + + case fsm_enc_conv_init: + + // copy the init states to the current memory + + d_memory = d_init_state; + + // if not doing streaming, things to do; else nothing more do + + if (d_do_streaming == false) { + + // reset the number of encoded bits in this block (which is + // used to compare with the number of bits in the block) + + d_n_enc_bits = 0; + } + + // move to the 'input' state + + d_fsm_state = fsm_enc_conv_doing_input; + break; + + case fsm_enc_conv_doing_input: + + // working through the trellis section which requires input bits + // from external sources; loop up to the block size (before + // termination bits, if any), counting down the number of + // available input bits. + + encode_loop (in_buf, out_buf, &d_n_input_bits_left, d_block_size_bits); + + // finished this loop; check for jumping to the next state + + if ((d_n_enc_bits == d_block_size_bits) & (d_do_streaming == false)) { + + // jump to another state, depending on termination requirement + + if (d_do_termination == true) { + d_n_enc_bits = 0; + d_fsm_state = fsm_enc_conv_doing_term; + } else { + d_fsm_state = fsm_enc_conv_init; + } + } + break; + + case fsm_enc_conv_doing_term: + + // terminating the trellis, trying to get to a specific state; + // better get here only when do_termination is true, but check + // just in case; lop up to the max memory, counting down the + // number of output bits left + + if (d_do_termination == true) { + encode_loop (in_buf, out_buf, &d_n_output_bits_left, d_total_n_delays); + + // finished this loop; check for jumping to the next state + + if (d_n_enc_bits == d_total_n_delays) + d_fsm_state = fsm_enc_conv_init; + + } else { + // should never get here! + assert (0); + } + break; + + default: + // better never get here! + assert (0); + break; + + // done (switch) with FSM + } + + // done (while) there are inputs and outputs + } + + if (DO_PRINT_DEBUG) { + std::cout << "Done with this encode() call; ending parameters.\n" + "d_in_bit_shift = " << d_in_bit_shift << "\n" + "d_out_bit_shift = " << d_out_bit_shift << "\n" + "d_in_buf_ndx = " << d_in_buf_ndx << "\n" + "d_out_buf_ndx = " << d_out_buf_ndx << "\n" + "d_n_input_bits_left = " << d_n_input_bits_left << "\n" + "d_n_output_bits_left = " << d_n_output_bits_left << "\n" + "d_total_n_enc_bits = " << d_total_n_enc_bits << "\n"; + } + + if (DO_TIME_THOUGHPUT) { + // compute the throughput for this particular function call + u_long d_t = end_timer (&t_tp); + std::cout << "Completed " << d_total_n_enc_bits << + " bits in " << d_t << " usec => " << + 1e6*(((double) d_total_n_enc_bits)/((double) d_t)) << + " b/s\n"; + } +} + +void +encoder_convolutional::encode_loop +(const char** in_buf, + char** out_buf, + size_t* which_counter, + size_t how_many) +{ + // generic encode_loop + + if (DO_PRINT_DEBUG) { + std::cout << "Starting encode_loop.\n"; + } + + while (((*which_counter) > 0) & (d_n_enc_bits < how_many)) { + if (DO_PRINT_DEBUG) { + std::cout << "*w_c = " << (*which_counter) << ", " + "# enc_bits = " << d_n_enc_bits << " of " << how_many << ".\n" + "Getting new inputs.\n"; + } + + // get the next set of input bits from all streams; + // written into d_current_inputs + + get_next_inputs (in_buf); + + // use the trellis to do the encoding; + // updates the input memory to the new memory state for the given input + // and writes the output bits to the current_outputs + + d_trellis->encode_lookup (d_memory, d_current_inputs, d_current_outputs); + + // write the bits in d_current_outputs into the output buffer + + write_output_bits (out_buf); + + // increment the number of encoded bits for the current block, and + // the total number of bits for this running of "encode()" + + d_n_enc_bits++; + d_total_n_enc_bits++; + } + + if (DO_PRINT_DEBUG) { + std::cout << "ending encode_loop.\n"; + } +} + +void +encoder_convolutional::get_next_inputs__term +() +{ + // FIXME: how to figure out which term bit to get? + // loop to set each entry of "d_current_inputs" + + // need to do feedback separately, since it involves determining the + // FB bit value & using that as the input value to cancel it out + + d_current_inputs.assign (d_n_code_inputs, 0); + // return (d_term_states[code_input_n] & 1); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h new file mode 100644 index 000000000..4a0d479ac --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional.h @@ -0,0 +1,230 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef INCLUDED_ENCODER_CONVOLUTIONAL_H +#define INCLUDED_ENCODER_CONVOLUTIONAL_H + +#include "encoder.h" +#include "code_convolutional_trellis.h" + +class encoder_convolutional : public encoder +{ +/*! + * class encoder_convolutional : public encoder + * + * Encode the incoming streams using a convolutional encoder; This is + * a virtual class which defines the basics of a convolutional + * encoder, but not how input and output bits are handled, nor + * feedback in the encoder. These features are all defined by + * overriding methods appropriately. + * + * block_size_bits: if == 0, then do streaming encoding ("infinite" + * trellis); otherwise this is the block size in bits to encode + * before terminating the trellis. This value -does not- include + * any termination bits. + * + * n_code_inputs: + * n_code_outputs: + * code_generator: vector of integers (32 bit) representing the code + * to be implemented. E.g. "4" in binary is "100", which would be + * "D^2" for code generation. "6" == 110b == "D^2 + D" + * ==> The vector is listed in order for each output stream, so if there + * are 2 input streams (I1, I2) [specified in "n_code_inputs"] + * and 2 output streams (O1, O2) [specified in "n_code_outputs"], + * then the vector would be the code generator for: + * [I1->O1, I2->O1, I1->O2, I2->O2] + * with each element being an integer representation of the code. + * The "octal" representation is used frequently in the literature + * (e.g. [015, 06] == [1101, 0110] in binary) due to its close + * relationship with binary (each number is 3 binary digits) + * ... but any integer representation will suffice. + * + * do_termination: valid only if block_size_bits != 0, and defines + * whether or not to use trellis termination. Default is to use + * termination when doing block coding. + * + * start_memory_state: when starting a new block, the starting memory + * state to begin encoding; there will be a helper function to + * assist in creating this value for a given set of inputs; + * default is the "all zero" state. + * + * end_memory_state: when terminating a block, the ending memory + * state to stop encoding; there will be a helper function to + * assist in creating this value for a given set of inputs; + * default is the "all zero" state. + */ + +public: + inline encoder_convolutional + (int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + bool do_termination = true, + int start_memory_state = 0, + int end_memory_state = 0) + {encoder_convolutional_init (block_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + 0, + do_termination, + start_memory_state, + end_memory_state);}; + +/*! + * Encoder with feedback. + * + * code_feedback: vector of integers (32 bit) representing the code + * feedback to be implemented (same as for the code_generator). + * For this feedback type, the LSB ("& 1") is ignored (set to "1" + * internally, since it's always 1) ... this (effectively) + * represents the input bit for the given encoder, without which + * there would be no encoding! Each successive higher-order bit + * represents the output of that delay block; for example "6" == + * 110b == "D^2 + D" means use the current input bit + the output + * of the second delay block. Listing order is the same as for + * the code_generator. + */ + + inline encoder_convolutional + (int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int>& code_generators, + const std::vector<int>& code_feedback, + bool do_termination = true, + int start_memory_state = 0, + int end_memory_state = 0) + {encoder_convolutional_init (block_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + &code_feedback, + do_termination, + start_memory_state, + end_memory_state);}; + + virtual ~encoder_convolutional () {delete d_trellis;}; + +/* for remote access to internal info */ + + inline const bool do_termination () {return (d_do_termination);}; + inline const bool do_feedback () {return (d_trellis->do_feedback());}; + inline const bool do_streaming () {return (d_do_streaming);}; + inline const size_t total_n_delays () {return (d_total_n_delays);}; + +protected: +/* + * fsm_enc_conv_t: finite state machine for the convolutional encoder; + * output happens all the time, so that's built-in to each state. + * + * fsm_enc_conv_init: initialize for a new block / block; this is already + * done at instantiation, so do it only at the end of a block. + * + * fsm_enc_conv_doing_input: doing encoding inside the trellis + * + * fsm_enc_conv_doing_term: termination trellis, if requested + */ + + enum fsm_enc_conv_t { + fsm_enc_conv_init, fsm_enc_conv_doing_input, fsm_enc_conv_doing_term + }; + + // methods defined in this class + + void encoder_convolutional_init (int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int>& code_generators, + const std::vector<int>* code_generators, + bool do_termination, + int start_memory_state, + int end_memory_state); + + virtual void encode_private (const char** in_buf, char** out_buf); + + virtual void encode_loop (const char** in_buf, char** out_buf, + size_t* which_counter, size_t how_many); + + inline void get_next_inputs (const char** in_buf) { + switch (d_fsm_state) { + case fsm_enc_conv_doing_input: + get_next_inputs__input (in_buf); + break; + case fsm_enc_conv_doing_term: + get_next_inputs__term (); + break; + default: + assert (0); + break; + } + }; + + virtual void get_next_inputs__term (); + + void get_memory_requirements (size_t m, + size_t n, + size_t& t_max_mem, + size_t& t_n_unique_fb_prev_start, + const std::vector<int>* code_feedback); + + // methods which are required by classes which inherit from this + // one; primarily just the parts which deal with getting input bits + // and writing output bits, changing the indices for those buffers. + + virtual void write_output_bits (char** out_buf) = 0; + virtual void get_next_inputs__input (const char** in_buf) = 0; + + // variables + + fsm_enc_conv_t d_fsm_state; + bool d_do_streaming, d_do_termination; + + // "total_n_delays" is the total # of delays, needed to determine the + // # of states in the decoder + + size_t d_total_n_delays; + + // the current state of the encoder (all delays / memories) + + memory_t d_memory; + + // "inputs" are the current input bits, in the LSB (&1) of each "char" + + std::vector<char> d_current_inputs; + + // "outputs" are the current output bits, in the LSB (&1) of each "char" + + std::vector<char> d_current_outputs; + + // "trellis" is the code trellis for the given input parameters + + code_convolutional_trellis* d_trellis; + + // "init_states" are the user-provided init states, + // interpreted w/r.t. the actual trellis; + + memory_t d_init_state; +}; + +#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic1_ic1.cc b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic1_ic1.cc new file mode 100644 index 000000000..aa83c0762 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic1_ic1.cc @@ -0,0 +1,188 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <encoder_convolutional_ic1_ic1.h> +#include <assert.h> +#include <iostream> +#include <mld/n2bs.h> + +#define DO_PRINT_DEBUG 0 + +static const int g_num_bits_per_byte = 8; + +// FIXME +size_t +encoder_convolutional_ic1_ic1::compute_n_output_bits +(size_t n_input_bits) +{ + assert (0); + return (0); +} + +/* + * Compute the number of input bits needed to produce + * 'n_output' bits. For convolutional encoders, there is + * 1 bit output per bit input per stream, with the addition of a some + * bits for trellis termination if selected. Thus the input:output + * bit ratio will be: + * + * if (streaming | no termination), 1:1 + * + * if (not streaming & termination), roughly 1:(1+X), where "X" is the + * total memory size of the code divided by the block length in bits. + * But this also depends on the state of the FSM ... how many bits are + * left before termination. + * + * The returned value will also depend on whether bits are packed, as + * well as whether streams are mux'ed together. + */ + +size_t +encoder_convolutional_ic1_ic1::compute_n_input_bits +(size_t n_output_bits) +{ + size_t t_n_output_bits, t_n_input_bits; + t_n_output_bits = t_n_input_bits = n_output_bits; + + if (d_do_termination == true) { + + // not streaming, doing termination; find the number of bits + // currently available with no required inputs, if any + + size_t n_extra = 0; + if (d_fsm_state == fsm_enc_conv_doing_term) { + n_extra = d_total_n_delays - d_n_enc_bits; + } + + // check to see if this is enough; return 0 if it is. + + if (n_extra >= t_n_output_bits) + return (0); + + // remove those which require no input + + t_n_output_bits -= n_extra; + + // find the number of blocks of data which could be processed + + size_t t_n_output_bits_per_block = d_block_size_bits + d_total_n_delays; + + // get the base number of input items required for the given + // number of blocks to be generated + + size_t t_n_blocks = t_n_output_bits / t_n_output_bits_per_block; + t_n_input_bits = t_n_blocks * d_block_size_bits; + + // add to that the number of leftover inputs needed to generate + // the remainder of the outputs within the remaining block, up to + // the given block size (since anything beyond that within this + // block requires no inputs) + + size_t t_leftover_bits = t_n_output_bits % t_n_output_bits_per_block; + t_n_input_bits += ((t_leftover_bits > d_block_size_bits) ? + d_block_size_bits : t_leftover_bits); + } + + return (t_n_input_bits); +} + +void +encoder_convolutional_ic1_ic1::write_output_bits +(char** out_buf) +{ + // write all the outputs bits in d_current_outputs LSB (&1) to the + // given output buffer. + + // one bit per output 'char' for "ic1" type output + + for (size_t n = 0; n < d_n_code_outputs; n++) { + if (DO_PRINT_DEBUG) { + std::cout << "Starting output_bit:\n" + " O_i[" << n << "][" << d_out_buf_ndx << "] = " << + n2bs (out_buf[n][d_out_buf_ndx], g_num_bits_per_byte) << + ", b_out = " << n2bs (d_current_outputs[n], 1) << ", "; + } + + out_buf[n][d_out_buf_ndx] = d_current_outputs[n]; + + if (DO_PRINT_DEBUG) { + std::cout << "O_o[][] = " << + n2bs (out_buf[n][d_out_buf_ndx], g_num_bits_per_byte) << + "\n"; + } + } + + if (DO_PRINT_DEBUG) { + std::cout << "Ending write_output_bits.\n"; + } + + // decrement the number of output bits left on all streams + + d_n_output_bits_left--; + + // increment the output index (not the bit shift index) for the next + // write + + d_out_buf_ndx++; +} + +void +encoder_convolutional_ic1_ic1::get_next_inputs__input +(const char** in_buf) +{ + // get the next set of input bits, moved into the LSB (&1) of + // d_current_inputs + + // one bit per input 'char' for "ic1" type input + + for (size_t m = 0; m < d_n_code_inputs; m++) { + d_current_inputs[m] = ((in_buf[m][d_in_buf_ndx]) & 1); + + if (DO_PRINT_DEBUG) { + std::cout << "I[" << m << "][" << d_in_buf_ndx << "] = " << + n2bs (d_current_inputs[m], 1) << "\n"; + } + } + + // decrement the number of bits left on all streams + + if (DO_PRINT_DEBUG) { + std::cout << "# in bits left: " << d_n_input_bits_left << + " -> " << (d_n_input_bits_left-1) << "\n"; + } + + d_n_input_bits_left--; + + // increment the input index (not the bit shift index) for the next + // read + + if (DO_PRINT_DEBUG) { + std::cout << "# in buf ndx: " << d_in_buf_ndx << + " -> " << (d_in_buf_ndx+1) << "\n"; + } + + d_in_buf_ndx++; +} diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic1_ic1.h b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic1_ic1.h new file mode 100644 index 000000000..a742b097a --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic1_ic1.h @@ -0,0 +1,91 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef INCLUDED_ENCODER_CONVOLUTIONAL_IC1_IC1_H +#define INCLUDED_ENCODER_CONVOLUTIONAL_IC1_IC1_H + +#include "encoder_convolutional.h" + +class encoder_convolutional_ic1_ic1 : public encoder_convolutional +{ +public: +/*! + * class encoder_convolutional_ic1_ic1 : public encoder_convolutional + * + * Encode the incoming streams using a convolutional encoder, + * "feedforward" or feedback. Optional termination, data + * streaming, and starting and ending memory states. + * + * input is "ic1": streams of char, one stream per input as defined by the + * instantiated code, using only the right-most justified bit as + * the single input bit per input item. + * + * output is "ic1": streams of char, one stream per output as defined by the + * instantiated code, using only the right-most justified bit as + * the single output bit per output item. + */ + + encoder_convolutional_ic1_ic1 + (int frame_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + bool do_termination = true, + int start_memory_state = 0, + int end_memory_state = 0) + : encoder_convolutional (frame_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + do_termination, + start_memory_state, + end_memory_state) {}; + + encoder_convolutional_ic1_ic1 + (int frame_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + const std::vector<int> &code_feedback, + bool do_termination = true, + int start_memory_state = 0, + int end_memory_state = 0) + : encoder_convolutional (frame_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + code_feedback, + do_termination, + start_memory_state, + end_memory_state) {}; + + virtual ~encoder_convolutional_ic1_ic1 () {}; + + virtual size_t compute_n_input_bits (size_t n_output_bits); + virtual size_t compute_n_output_bits (size_t n_input_bits); + +protected: + virtual void get_next_inputs__input (const char** in_buf); + virtual void write_output_bits (char** out_buf); +}; + +#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_IC1_IC1_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.cc b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.cc new file mode 100644 index 000000000..5d2a4bbbd --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.cc @@ -0,0 +1,224 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <encoder_convolutional_ic8_ic8.h> +#include <assert.h> +#include <iostream> + +#define DO_TIME_THOUGHPUT 1 +#define DO_PRINT_DEBUG 1 + +#if DO_TIME_THOUGHPUT +#include <mld/mld_timer.h> +#endif +#if DO_PRINT_DEBUG +#include <mld/n2bs.h> +#endif + +// FIXME: when doing packed, should probably allow user to select how +// bits are selected, so-as to make sure it's always the same +// no matter the CPU endianness + +// FIXME +size_t +encoder_convolutional_ic8_ic8::compute_n_output_bits +(size_t n_input_bits) +{ + assert (0); + return (0); +} + +/* + * Compute the number of input bits needed to produce + * 'n_output' bits. For convolutional encoders, there is + * 1 bit output per bit input per stream, with the addition of a some + * bits for trellis termination if selected. Thus the input:output + * bit ratio will be: + * + * if (streaming | no termination), 1:1 + * + * if (not streaming & termination), roughly 1:(1+X), where "X" is the + * total memory size of the code divided by the block length in bits. + * But this also depends on the state of the FSM ... how many bits are + * left before termination. + * + * The returned value will also depend on whether bits are packed, as + * well as whether streams are mux'ed together. + */ + +size_t +encoder_convolutional_ic8_ic8::compute_n_input_bits +(size_t n_output_bits) +{ + size_t t_n_output_bits, t_n_input_bits; + t_n_output_bits = t_n_input_bits = n_output_bits; + + if (d_do_termination == true) { + + // not streaming, doing termination; find the number of bits + // currently available with no required inputs, if any + + size_t n_extra = 0; + if (d_fsm_state == fsm_enc_conv_doing_term) { + n_extra = d_max_memory - d_n_enc_bits; + } + + // check to see if this is enough; return 0 if it is. + + if (n_extra >= t_n_output_bits) + return (0); + + // remove those which require no input + + t_n_output_bits -= n_extra; + + // find the number of frames of data which could be processed + + size_t t_n_output_bits_per_frame = d_frame_size_bits + d_max_memory; + + // get the base number of input items required for the given + // number of frames to be generated + + size_t t_n_frames = t_n_output_bits / t_n_output_bits_per_frame; + t_n_input_bits = t_n_frames * d_frame_size_bits; + + // add to that the number of leftover inputs needed to generate + // the remainder of the outputs within the remaining frame, up to + // the given frame size (since anything beyond that within this + // frame requires no inputs) + + size_t t_leftover_bits = t_n_output_bits % t_n_output_bits_per_frame; + t_n_input_bits += ((t_leftover_bits > d_frame_size_bits) ? + d_frame_size_bits : t_leftover_bits); + } + + return (t_n_input_bits); +} + +void +encoder_convolutional_ic8_ic8::increment_io_indices +(bool while_encoding) +{ + // increment the buffer index only for this version, only after + // encoding is done and all resulting outputs are stored on the + // output streams + + if (while_encoding == false) { + d_out_buf_ndx++; + d_in_buf_ndx++; + } + + // nothing to do while encoding, so no else + +#if 0 +// move counters to the next input bit, wrapping to the next input +// byte as necessary + if (++d_in_bit_shift % g_num_bits_per_byte == 0) { + d_in_bit_shift = 0; + d_in_buf_ndx++; + } +// move counters to the next output bit, wrapping to the next output +// byte as necessary + if (++d_out_bit_shift % g_num_bits_per_byte == 0) { + d_out_bit_shift = 0; + d_out_buf_ndx++; + } +#endif +} + +void +encoder_convolutional_ic8_ic8::output_bit +(char t_out_bit, + char** out_buf, + size_t t_output_stream) +{ + // store the result for this particular output stream + // one bit per output item for "ic8" type output + + if (DO_PRINT_DEBUG) { + std::cout << ", O_i[" << t_output_stream << + "][" << d_out_buf_ndx << "] = " << + n2bs (out_buf[t_output_stream][d_out_buf_ndx], 2); + } + + out_buf[t_output_stream][d_out_buf_ndx] = t_out_bit; + + if (DO_PRINT_DEBUG) { + std::cout << ", b_out = " << t_out_bit << + ", O_o[" << t_output_stream << "][" << d_out_buf_ndx << "][" << + d_out_bit_shift << "] = " << + n2bs (out_buf[t_output_stream][d_out_buf_ndx], 2) << '\n'; + } + +#if 0 +#if DO_PRINT_DEBUG + std::cout << ", O_i[" << t_output_stream << + "][" << d_out_buf_ndx << "] = " << + n2bs (out_buf[t_output_stream][d_out_buf_ndx], g_num_bits_per_byte); +#endif + +// packed bits in each output item + out_buf[t_output_stream][d_out_buf_ndx] |= + (t_out_bit << d_out_bit_shift); + +#if DO_PRINT_DEBUG + std::cout << ", b_out = " << t_out_bit << + ", O_o[" << t_output_stream << "][" << d_out_buf_ndx << "][" << + d_out_bit_shift << "] = " << + n2bs (out_buf[t_output_stream][d_out_buf_ndx], g_num_bits_per_byte) << '\n'; +#endif +#endif +} + +char +encoder_convolutional_ic8_ic8::get_next_bit__input +(const char** in_buf, + size_t code_input_n) +{ + // get a bit from this particular input stream + // one bit per output item for "ic8" type input + + if (DO_PRINT_DEBUG) { + std::cout << "I[" << p << "][" << d_in_buf_ndx << "] = "; + cout_binary (t_next_bit, g_num_bits_per_byte); + std::cout << ", st_i[" << p << "] = "; + cout_binary ((*t_states_ptr), d_max_memory+2); + std::cout << ", I[" << p << "][" << d_in_buf_ndx << "][" << + d_in_bit_shift << "] = " << t_next_bit << + ", st_o[" << p << "] = "; + cout_binary (t_state, d_max_memory+2); + std::cout << '\n'; + } + + return ((in_buf[code_input_n][d_in_buf_ndx] >> d_in_bit_shift) & 1); +} + +char +encoder_convolutional_ic8_ic8::get_next_bit__term +(size_t code_input_n) +{ + return ((d_term_states[code_input_n] >> d_in_bit_shift) & 1); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.h b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.h new file mode 100644 index 000000000..dad39400c --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_convolutional_ic8_ic8.h @@ -0,0 +1,96 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef INCLUDED_ENCODER_CONVOLUTIONAL_IC8_IC8_H +#define INCLUDED_ENCODER_CONVOLUTIONAL_IC8_IC8_H + +#include "encoder_convolutional.h" + +/*! + * class encoder_convolutional_ic8_ic8 : public encoder_convolutional + * + * Encode the incoming streams using a convolutional encoder, + * "feedforward" or feedback. Optional termination, data + * streaming, and starting and ending memory states. + * + * input is "ic8": streams of char, one stream per input as defined by the + * instantiated code, using all 8 bits in the char. + * + * FIXME: need to have inputs for MSB or LSB first input and output. + * + * output is "ic8": streams of char, one stream per output as defined by the + * instantiated code, using all 8 bits in the char. + */ + +class encoder_convolutional_ic8_ic8 : public encoder_convolutional +{ +public: + encoder_convolutional_ic8_ic8 + (int frame_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + bool do_termination = true, + int start_memory_state = 0, + int end_memory_state = 0) + : encoder_convolutional (frame_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + do_termination, + start_memory_state, + end_memory_state) {}; + + encoder_convolutional_ic8_ic8 + (int frame_size_bits, + int n_code_inputs, + int n_code_outputs, + const std::vector<int> &code_generators, + const std::vector<int> &code_feedback, + bool do_termination = true, + int start_memory_state = 0, + int end_memory_state = 0) + : encoder_convolutional (frame_size_bits, + n_code_inputs, + n_code_outputs, + code_generators, + code_feedback, + do_termination, + start_memory_state, + end_memory_state) {}; + + virtual ~encoder_convolutional_ic8_ic8 () {}; + + virtual size_t compute_n_input_bits (size_t n_output_bits); + virtual size_t compute_n_output_bits (size_t n_input_bits); + +protected: + virtual char get_next_bit__input (const char** in_buf, + size_t code_input_n); + virtual char get_next_bit__term (size_t code_input_n); + virtual void output_bit (char t_out_bit, char** out_buf, + size_t t_output_stream); + virtual void increment_io_indices (bool while_encoding); + virtual void update_memory_post_encode (); +}; + +#endif /* INCLUDED_ENCODER_CONVOLUTIONAL_IC8_IC8_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_turbo.cc b/gr-error-correcting-codes/src/lib/libecc/encoder_turbo.cc new file mode 100644 index 000000000..3f528cb91 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_turbo.cc @@ -0,0 +1,52 @@ +#include "encoder_turbo.h" + +encoder_turbo::encoder_turbo +(int n_code_inputs, + int n_code_outputs, + const std::vector<encoder_convolutional*> &encoders, + const std::vector<size_t> &interleavers) +{ + // need error checking on inputs + + d_encoders = encoders; + d_interleavers = interleavers; +} + +// dummy stuff for now to test std::vector<gr_streams_convolutional...> stuff + +size_t +encoder_turbo::compute_n_input_bits +(size_t n_output_bits) +{ + return (0); +} + +size_t +encoder_turbo::compute_n_output_bits +(size_t n_input_bits) +{ + return (0); +} + +void +encoder_turbo::encode_private +(const char** in_buf, + char** out_buf) +{ +} + +char +encoder_turbo::get_next_bit +(const char** in_buf, + size_t code_input_n) +{ + return (0); +} + +void +encoder_turbo::output_bit +(char t_out_bit, + char** out_buf, + size_t t_output_stream) +{ +} diff --git a/gr-error-correcting-codes/src/lib/libecc/encoder_turbo.h b/gr-error-correcting-codes/src/lib/libecc/encoder_turbo.h new file mode 100644 index 000000000..8c295f1e5 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/encoder_turbo.h @@ -0,0 +1,147 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#ifndef INCLUDED_ENCODER_TURBO_H +#define INCLUDED_ENCODER_TURBO_H + +#include "encoder_convolutional.h" +#include <vector> + +class encoder_turbo : public encoder +{ +public: +/*! + * class encoder_turbo : public encoder + * + * Encode the incoming streams using a turbo encoder; This is a + * virtual class which defines the basics of a turbo encoder, but + * not how input and output bits are handled. These features are + * all defined by overriding methods appropriately. + * + * n_code_inputs: + * n_code_outputs: the total number of code inputs and outputs for the + * overall turbo encoder (not just the constituent codes). + * + * encoders: the constituent encoders to be used; all -should- be + * configured with the same "block_size" and "termination", though + * from this encoder's perspective it doesn't really matter. + * + * interleavers: the interleavers to use before each encoder, + * respectively, except the first encoder which will not use an + * interleaver. + */ + + encoder_turbo + (int n_code_inputs, + int n_code_outputs, + const std::vector<encoder_convolutional*> &encoders, + const std::vector<size_t> &interleavers); + + virtual ~encoder_turbo () {}; + +/* for remote access to internal info */ + + inline bool do_termination () {return (d_do_termination);}; + +#if 1 + virtual size_t compute_n_input_bits (size_t n_output_bits); + virtual size_t compute_n_output_bits (size_t n_input_bits); +#endif + +protected: +/* + * fsm_enc_turbo_t: finite state machine for the turbo encoder; + * output happens all the time, so that's built-in to each state. + * + * fsm_enc_turbo_init: initialize for a new frame / block; this is already + * done at instantiation, so do it only at the end of a block. + * + * fsm_enc_turbo_doing_input: doing encoding inside the trellis + * + * fsm_enc_turbo_doing_term: termination trellis, if requested + */ + + enum fsm_enc_turbo_t { + fsm_enc_turbo_init, fsm_enc_turbo_doing_input, fsm_enc_turbo_doing_term + }; + +/* + * maio(i,o): matrix access into a vector, knowing the # of code + * outputs (from inside the class). References into a vector with + * code inputs ordered by code output. + * + * 'i' is the first dimension - immediate memory order first - the code input + * 'o' is the second dimension - slower memory order second - the code output + * + * returns ((o*n_code_outputs) + i) + */ + + inline size_t maio(size_t i, size_t o) {return ((o*d_n_code_outputs) + i);}; + +/* + * maoi(i,o): matrix access into a vector, knowing the # of code + * inputs (from inside the class). References into a vector with + * code outputs ordered by code input. + * + * 'o' is the first dimension - immediate memory order first - the code output + * 'i' is the second dimension - slower memory order second - the code input + * + * returns ((i*n_code_inputs) + o) + */ + + inline size_t maoi(size_t i, size_t o) {return ((i*d_n_code_inputs) + o);}; + + // methods defined in this class +#if 1 + // temporary just to get full compilation + + virtual void encode_private (const char** in_buf, char** out_buf); + virtual char get_next_bit (const char** in_buf, size_t code_input_n); + virtual void output_bit (char t_out_bit, char** out_buf, + size_t t_output_stream); +#else + virtual void encode_private (const char** in_buf, char** out_buf) = 0; + virtual void encode_loop (const char** in_buf, char** out_buf, + size_t* which_counter, size_t how_many) = 0; + virtual char get_next_bit (const char** in_buf, size_t code_input_n) = 0; + virtual char get_next_bit__term (size_t code_input_n) = 0; + + // methods which are required by classes which inherit from this + // one; primarily just the parts which deal with getting input bits + // and writing output bits, changing the indices for those buffers. + + virtual char get_next_bit__input (const char** in_buf, + size_t code_input_n) = 0; + virtual void increment_io_indices (bool while_encoding) = 0; +#endif + + // variables + + fsm_enc_turbo_t d_fsm_state; + bool d_do_termination; + size_t d_max_memory, d_n_memories; + + std::vector<encoder_convolutional*> d_encoders; + std::vector<size_t> d_interleavers; +}; + +#endif /* INCLUDED_ENCODER_TURBO_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/mld/Makefile.am b/gr-error-correcting-codes/src/lib/libecc/mld/Makefile.am new file mode 100644 index 000000000..b5accd5af --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/mld/Makefile.am @@ -0,0 +1,36 @@ +# +# Copyright 2005 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. +# + +include $(top_srcdir)/Makefile.common + +INCLUDES = $(STD_DEFINES_AND_INCLUDES) -I.. -I../.. + +noinst_LTLIBRARIES = libmld.la + +libmld_la_SOURCES = \ + mld_timer.cc n2bs.cc + +noinst_HEADERS = \ + mld_timer.h n2bs.h + +MOSTLYCLEANFILES = *.loT *~ + +CONFIG_CLEAN_FILES = *.in diff --git a/gr-error-correcting-codes/src/lib/libecc/mld/mld_timer.cc b/gr-error-correcting-codes/src/lib/libecc/mld/mld_timer.cc new file mode 100644 index 000000000..91708ceb9 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/mld/mld_timer.cc @@ -0,0 +1,50 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio. + * + * Primary Author: Michael Dickens, NCIP Lab, University of Notre Dame + * + * 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. + */ + +#include <sys/types.h> +#include <mld_timer.h> + +void start_timer (struct timeval *t_tp) +{ + gettimeofday (t_tp, 0); +} + +u_long end_timer (struct timeval *g_tp) +{ + struct timeval t_tp; + gettimeofday (&t_tp, 0); + + u_long retVal = (t_tp.tv_sec - g_tp->tv_sec); + u_long df_usec; + + if (t_tp.tv_usec < g_tp->tv_usec) { + retVal -= 1; + df_usec = 1000000 - (g_tp->tv_usec - t_tp.tv_usec); + } else + df_usec = t_tp.tv_usec - g_tp->tv_usec; + + retVal *= 1000000; + retVal += df_usec; + return (retVal); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/mld/mld_timer.h b/gr-error-correcting-codes/src/lib/libecc/mld/mld_timer.h new file mode 100644 index 000000000..5e5f89c38 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/mld/mld_timer.h @@ -0,0 +1,28 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio. + * + * Primary Author: Michael Dickens, NCIP Lab, University of Notre Dame + * + * 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. + */ + +#include <sys/time.h> + +extern void start_timer (struct timeval *t_tp); +extern u_long end_timer (struct timeval *g_tp); diff --git a/gr-error-correcting-codes/src/lib/libecc/mld/n2bs.cc b/gr-error-correcting-codes/src/lib/libecc/mld/n2bs.cc new file mode 100644 index 000000000..909aa0867 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/mld/n2bs.cc @@ -0,0 +1,73 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio. + * + * Primary Author: Michael Dickens, NCIP Lab, University of Notre Dame + * + * 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. + */ + +#include <n2bs.h> +#include <iostream> + +const int g_num_bits_per_byte = 8; + +std::string n2bs (long long number, size_t digits) +{ + if (digits > (sizeof (long long) * g_num_bits_per_byte)) + digits = sizeof (long long); + std::string retVal (digits, '0'); + if (number != 0) + for (int n = --digits; n >= 0; n--) { + if (number & 1) { + retVal[n] = '1'; + } + number >>= 1; + } + return (retVal); +} +std::string n2bs (char number, size_t digits) +{ + if (digits > (sizeof (char) * g_num_bits_per_byte)) + digits = sizeof (char); + return n2bs ((long long) number, digits); +} +std::string n2bs (int number, size_t digits) +{ + if (digits > (sizeof (int) * g_num_bits_per_byte)) + digits = sizeof (int); + return n2bs ((long long) number, digits); +} +std::string n2bs (long number, size_t digits) +{ + if (digits > (sizeof (long) * g_num_bits_per_byte)) + digits = sizeof (long); + return n2bs ((long long) number, digits); +} +std::string n2bs (size_t number, size_t digits) +{ + if (digits > (sizeof (size_t) * g_num_bits_per_byte)) + digits = sizeof (size_t); + return n2bs ((long long) number, digits); +} + +void cout_binary (int number, int digits) +{ + while (digits-- > 0) + std::cout << ((number >> digits) & 1); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/mld/n2bs.h b/gr-error-correcting-codes/src/lib/libecc/mld/n2bs.h new file mode 100644 index 000000000..a663dce8a --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/mld/n2bs.h @@ -0,0 +1,32 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006 Free Software Foundation, Inc. + * + * This file is part of GNU Radio. + * + * Primary Author: Michael Dickens, NCIP Lab, University of Notre Dame + * + * 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. + */ + +#include <string> + +extern std::string n2bs (char number, size_t digits); +extern std::string n2bs (int number, size_t digits); +extern std::string n2bs (long number, size_t digits); +extern std::string n2bs (size_t number, size_t digits); +extern std::string n2bs (long long number, size_t digits); +extern void cout_binary (int number, int digits); diff --git a/gr-error-correcting-codes/src/lib/libecc/tests/Makefile.am b/gr-error-correcting-codes/src/lib/libecc/tests/Makefile.am new file mode 100644 index 000000000..79850ba74 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/tests/Makefile.am @@ -0,0 +1,47 @@ +# +# Copyright 2001 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. +# + +include $(top_srcdir)/Makefile.common + +INCLUDES = $(STD_DEFINES_AND_INCLUDES) $(CPPUNIT_INCLUDES) -I.. + +noinst_LTLIBRARIES = libecc-qa.la + +noinst_HEADERS = \ + qa_encoder_convolutional_ic1_ic1.h \ + qa_ecc.h + +libecc_qa_la_SOURCES = \ + qa_encoder_convolutional_ic1_ic1.cc \ + qa_ecc.cc + +# list of programs run by "make check" and "make distcheck" + +TESTS = test_all + +noinst_PROGRAMS = test_all + +LIBECC = ../libecc.la +LIBECCQA = libecc-qa.la $(LIBECC) + +test_all_SOURCES = test_all.cc +test_all_LDADD = $(LIBECCQA) \ + $(CPPUNIT_LIBS) diff --git a/gr-error-correcting-codes/src/lib/libecc/tests/qa_ecc.cc b/gr-error-correcting-codes/src/lib/libecc/tests/qa_ecc.cc new file mode 100644 index 000000000..03b185be6 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/tests/qa_ecc.cc @@ -0,0 +1,40 @@ +/* + * 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. + */ + +/* + * This class gathers together all the test cases for the gr + * directory into a single test suite. As you create new test cases, + * add them here. + */ + +#include <qa_ecc.h> +#include <qa_encoder_convolutional_ic1_ic1.h> + +CppUnit::TestSuite* +qa_ecc::suite +() +{ + CppUnit::TestSuite* s = new CppUnit::TestSuite ("ecc"); + + s->addTest (qa_encoder_convolutional_ic1_ic1::suite ()); + + return (s); +} diff --git a/gr-error-correcting-codes/src/lib/libecc/tests/qa_ecc.h b/gr-error-correcting-codes/src/lib/libecc/tests/qa_ecc.h new file mode 100644 index 000000000..ef411673e --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/tests/qa_ecc.h @@ -0,0 +1,36 @@ +/* -*- 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 _QA_ECC_H_ +#define _QA_ECC_H_ + +#include <cppunit/TestSuite.h> + +//! collect all the tests for the gr directory + +class qa_ecc { +public: + //! return suite of tests for all of gr directory + static CppUnit::TestSuite *suite (); +}; + +#endif /* _QA_ECC_H_ */ diff --git a/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc b/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc new file mode 100644 index 000000000..6ea72b6f8 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.cc @@ -0,0 +1,430 @@ +/* -*- 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. + */ + +#include "encoder_convolutional_ic1_ic1.h" +#include <qa_encoder_convolutional_ic1_ic1.h> +#include <cppunit/TestAssert.h> +#include <string.h> +#include <iostream> +#include <iomanip> +#include <stdio.h> + + +void +qa_encoder_convolutional_ic1_ic1::do_encoder_check +(const char** c_in, + const char** c_res, + int n_output_items, + int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const int* code_generators, + const int* code_feedback) +{ + std::vector<int> t_code_generators; + t_code_generators.assign (n_code_inputs * n_code_outputs, 0); + for (int m = 0; m < n_code_inputs * n_code_outputs; m++) + t_code_generators[m] = code_generators[m]; + + encoder_convolutional_ic1_ic1* t_encoder; + + if (code_feedback) { + std::vector<int> t_code_feedback; + t_code_feedback.assign (n_code_inputs * n_code_outputs, 0); + for (int m = 0; m < n_code_inputs * n_code_outputs; m++) + t_code_feedback[m] = code_feedback[m]; + + t_encoder = new encoder_convolutional_ic1_ic1 + (block_size_bits, + n_code_inputs, + n_code_outputs, + t_code_generators, + t_code_feedback); + } else { + t_encoder = new encoder_convolutional_ic1_ic1 + (block_size_bits, + n_code_inputs, + n_code_outputs, + t_code_generators); + } + + char** t_out = new char*[n_code_outputs]; + for (int m = 0; m < n_code_outputs; m++) { + t_out[m] = new char[n_output_items]; + } + + t_encoder->encode (c_in, (char**) t_out, n_output_items); + + for (int m = 0; m < n_code_outputs; m++) { + for (int n = 0; n < n_output_items; n++) { + CPPUNIT_ASSERT_EQUAL (c_res[m][n], t_out[m][n]); + } + } + + delete t_encoder; + t_encoder = 0; + + for (int m = 0; m < n_code_outputs; m++) { + delete [] t_out[m]; + t_out[m] = 0; + } + delete [] t_out; + t_out = 0; +} + +// TEST 0 +// +// checking for SOAI realization (implicitely) +// no feedback, no termination + +const static int t0_code_generator[6] = {1, 0, 5, 0, 1, 6}; +const static int t0_n_code_inputs = 3; +const static int t0_n_code_outputs = 2; +const static int t0_n_input_items = 10; +const static int t0_n_output_items = 10; + +const static char t0_in_0[t0_n_input_items] = + {0, 1, 0, 0, 1, 0, 1, 0, 0, 0}; +const static char t0_in_1[t0_n_input_items] = + {0, 1, 0, 0, 0, 1, 1, 0, 0, 0}; +const static char t0_in_2[t0_n_input_items] = + {0, 0, 1, 1, 1, 1, 1, 0, 0, 0}; +const static char* t0_in[t0_n_code_inputs] = + {t0_in_0, t0_in_1, t0_in_2}; + +const static char t0_res_0[t0_n_output_items] = + {0, 1, 1, 1, 1, 0, 1, 1, 1, 0}; +const static char t0_res_1[t0_n_output_items] = + {0, 1, 0, 1, 0, 1, 1, 0, 1, 0}; +const static char* t0_res[t0_n_code_outputs] = + {t0_res_0, t0_res_1}; + +void +qa_encoder_convolutional_ic1_ic1::t0 +() +{ + do_encoder_check ((const char**) t0_in, (const char**) t0_res, + t0_n_output_items, 100, t0_n_code_inputs, + t0_n_code_outputs, (const int*) t0_code_generator); +} + +// TEST 1 +// +// checking for SIAO realization (implicitely) +// no feedback, no termination + +const static int t1_code_generator[6] = {1, 0, 0, 1, 5, 6}; +const static int t1_n_code_inputs = 2; +const static int t1_n_code_outputs = 3; +const static int t1_n_input_items = 9; +const static int t1_n_output_items = 9; + +const static char t1_in_0[t1_n_input_items] = + {0, 1, 1, 1, 0, 0, 0, 1, 0}; +const static char t1_in_1[t1_n_input_items] = + {0, 0, 0, 0, 0, 1, 1, 1, 0}; +const static char* t1_in[t1_n_code_inputs] = + {t1_in_0, t1_in_1}; + +const static char t1_res_0[t1_n_output_items] = + {0, 1, 1, 1, 0, 0, 0, 1, 0}; +const static char t1_res_1[t1_n_output_items] = + {0, 0, 0, 0, 0, 1, 1, 1, 0}; +const static char t1_res_2[t1_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 1, 0}; +const static char* t1_res[t1_n_code_outputs] = + {t1_res_0, t1_res_1, t1_res_2}; + +void +qa_encoder_convolutional_ic1_ic1::t1 +() +{ + do_encoder_check ((const char**) t1_in, (const char**) t1_res, + t1_n_output_items, 100, t1_n_code_inputs, + t1_n_code_outputs, (const int*) t1_code_generator); +} + +// TEST 2 +// +// checking for SIAO realization (implicitely) +// with same feedback, no termination + +const static int t2_code_generator[6] = {1, 0, 0, 1, 5, 6}; +const static int t2_code_feedback[6] = {0, 0, 0, 0, 7, 7}; +const static int t2_n_code_inputs = 2; +const static int t2_n_code_outputs = 3; +const static int t2_n_input_items = 19; +const static int t2_n_output_items = 19; + +const static char t2_in_0[t2_n_input_items] = + {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0}; +const static char t2_in_1[t2_n_input_items] = + {0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0}; +const static char* t2_in[t2_n_code_inputs] = + {t2_in_0, t2_in_1}; + +const static char t2_res_0[t2_n_output_items] = + {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0}; +const static char t2_res_1[t2_n_output_items] = + {0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0}; +const static char t2_res_2[t2_n_output_items] = + {0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0}; +const static char* t2_res[t2_n_code_outputs] = + {t2_res_0, t2_res_1, t2_res_2}; + +void +qa_encoder_convolutional_ic1_ic1::t2 +() +{ + do_encoder_check ((const char**) t2_in, (const char**) t2_res, + t2_n_output_items, 100, t2_n_code_inputs, + t2_n_code_outputs, (const int*) t2_code_generator, + (const int*) t2_code_feedback); +} + +// TEST 3 +// +// checking for SOAI realization (implicitely) +// with same feedback, no termination + +const static int t3_code_generator[6] = {1, 0, 5, 0, 1, 6}; +const static int t3_code_feedback[6] = {0, 0, 7, 0, 0, 7}; +const static int t3_n_code_inputs = 3; +const static int t3_n_code_outputs = 2; +const static int t3_n_input_items = 17; +const static int t3_n_output_items = 17; + +const static char t3_in_0[t3_n_input_items] = + {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}; +const static char t3_in_1[t3_n_input_items] = + {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; +const static char t3_in_2[t3_n_input_items] = + {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0}; +const static char* t3_in[t3_n_code_inputs] = + {t3_in_0, t3_in_1, t3_in_2}; + +const static char t3_res_0[t3_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0}; +const static char t3_res_1[t3_n_output_items] = + {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0}; +const static char* t3_res[t3_n_code_outputs] = + {t3_res_0, t3_res_1}; + +void +qa_encoder_convolutional_ic1_ic1::t3 +() +{ + do_encoder_check ((const char**) t3_in, (const char**) t3_res, + t3_n_output_items, 100, t3_n_code_inputs, + t3_n_code_outputs, (const int*) t3_code_generator, + (const int*) t3_code_feedback); +} + +// TEST 4 +// +// checking for SIAO realization (implicitely), +// with different feedbacks, no termination + +const static int t4_code_generator[6] = {1, 4, 0, 3, 1, 6}; +const static int t4_code_feedback[6] = {0, 7, 0, 5, 0, 5}; +const static int t4_n_code_inputs = 2; +const static int t4_n_code_outputs = 3; +const static int t4_n_input_items = 20; +const static int t4_n_output_items = 20; + +const static char t4_in_0[t4_n_input_items] = + {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0}; +const static char t4_in_1[t4_n_input_items] = + {0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0}; +const static char* t4_in[t4_n_code_inputs] = + {t4_in_0, t4_in_1}; + +const static char t4_res_0[t4_n_output_items] = + {0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0}; +const static char t4_res_1[t4_n_output_items] = + {0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0}; +const static char t4_res_2[t4_n_output_items] = + {0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}; +const static char* t4_res[t4_n_code_outputs] = + {t4_res_0, t4_res_1, t4_res_2}; + +void +qa_encoder_convolutional_ic1_ic1::t4 +() +{ + do_encoder_check ((const char**) t4_in, (const char**) t4_res, + t4_n_output_items, 100, t4_n_code_inputs, + t4_n_code_outputs, (const int*) t4_code_generator, + (const int*) t4_code_feedback); +} + +// TEST 5 +// +// checking for SOAI realization (implicitely), +// with different feedbacks, no termination + +const static int t5_code_generator[6] = {1, 0, 0, 1, 5, 7}; +const static int t5_code_feedback[6] = {0, 0, 0, 0, 7, 3}; +const static int t5_n_code_inputs = 2; +const static int t5_n_code_outputs = 3; +const static int t5_n_input_items = 19; +const static int t5_n_output_items = 19; + +const static char t5_in_0[t5_n_input_items] = + {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}; +const static char t5_in_1[t5_n_input_items] = + {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}; +const static char* t5_in[t5_n_code_inputs] = + {t5_in_0, t5_in_1}; + +const static char t5_res_0[t5_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0}; +const static char t5_res_1[t5_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0}; +const static char t5_res_2[t5_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0}; +const static char* t5_res[t5_n_code_outputs] = + {t5_res_0, t5_res_1, t5_res_2}; + +void +qa_encoder_convolutional_ic1_ic1::t5 +() +{ +#if 0 + do_encoder_check ((const char**) t5_in, (const char**) t5_res, + t5_n_output_items, 100, t5_n_code_inputs, + t5_n_code_outputs, (const int*) t5_code_generator); +#endif +} + +// TEST 6 +// +// checking for termination, no feedback + +const static int t6_code_generator[6] = {1, 0, 5, 0, 1, 6}; +const static int t6_n_code_inputs = 3; +const static int t6_n_code_outputs = 2; +const static int t6_n_input_items = 6; +const static int t6_n_output_items = 8; + +const static char t6_in_0[t6_n_input_items] = + {0, 1, 0, 0, 1, 0}; +const static char t6_in_1[t6_n_input_items] = + {0, 1, 0, 0, 0, 0}; +const static char t6_in_2[t6_n_input_items] = + {0, 0, 1, 1, 1, 0}; +const static char* t6_in[t6_n_code_inputs] = + {t6_in_0, t6_in_1, t6_in_2}; + +const static char t6_res_0[t6_n_output_items] = + {0, 1, 1, 1, 1, 1, 1, 0}; +const static char t6_res_1[t6_n_output_items] = + {0, 1, 0, 1, 0, 0, 1, 0}; +const static char* t6_res[t6_n_code_outputs] = + {t6_res_0, t6_res_1}; + +void +qa_encoder_convolutional_ic1_ic1::t6 +() +{ + do_encoder_check ((const char**) t6_in, (const char**) t6_res, + t6_n_output_items, 5, t6_n_code_inputs, + t6_n_code_outputs, (const int*) t6_code_generator); +} + +// TEST 7 +// +// checking for termination, with same feedback + +const static int t7_code_generator[6] = {1, 0, 5, 0, 1, 6}; +const static int t7_code_feedback[6] = {0, 0, 7, 0, 0, 7}; +const static int t7_n_code_inputs = 3; +const static int t7_n_code_outputs = 2; +const static int t7_n_input_items = 17; +const static int t7_n_output_items = 17; + +const static char t7_in_0[t7_n_input_items] = + {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}; +const static char t7_in_1[t7_n_input_items] = + {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; +const static char t7_in_2[t7_n_input_items] = + {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0}; +const static char* t7_in[t7_n_code_inputs] = + {t7_in_0, t7_in_1, t7_in_2}; + +const static char t7_res_0[t7_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0}; +const static char t7_res_1[t7_n_output_items] = + {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0}; +const static char* t7_res[t7_n_code_outputs] = + {t7_res_0, t7_res_1}; + +void +qa_encoder_convolutional_ic1_ic1::t7 +() +{ +#if 0 + do_encoder_check ((const char**) t7_in, (const char**) t7_res, + t7_n_output_items, 5, t7_n_code_inputs, + t7_n_code_outputs, (const int*) t7_code_generator, + (const int*) t7_code_feedback); +#endif +} + +// TEST 8 +// +// checking for termination, with different feedback + +const static int t8_code_generator[6] = {1, 0, 5, 0, 1, 6}; +const static int t8_code_feedback[6] = {0, 0, 7, 0, 0, 3}; +const static int t8_n_code_inputs = 3; +const static int t8_n_code_outputs = 2; +const static int t8_n_input_items = 17; +const static int t8_n_output_items = 17; + +const static char t8_in_0[t8_n_input_items] = + {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}; +const static char t8_in_1[t8_n_input_items] = + {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; +const static char t8_in_2[t8_n_input_items] = + {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0}; +const static char* t8_in[t8_n_code_inputs] = + {t8_in_0, t8_in_1, t8_in_2}; + +const static char t8_res_0[t8_n_output_items] = + {0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0}; +const static char t8_res_1[t8_n_output_items] = + {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0}; +const static char* t8_res[t8_n_code_outputs] = + {t8_res_0, t8_res_1}; + +void +qa_encoder_convolutional_ic1_ic1::t8 +() +{ +#if 0 + do_encoder_check ((const char**) t8_in, (const char**) t8_res, + t8_n_output_items, 5, t8_n_code_inputs, + t8_n_code_outputs, (const int*) t8_code_generator, + (const int*) t8_code_feedback); +#endif +} diff --git a/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.h b/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.h new file mode 100644 index 000000000..4449e9eb8 --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/tests/qa_encoder_convolutional_ic1_ic1.h @@ -0,0 +1,65 @@ +/* -*- 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_QA_ENCODER_CONVOLUTIONAL_IC1_IC1_H +#define INCLUDED_QA_ENCODER_CONVOLUTIONAL_IC1_IC1_H + +#include <cppunit/extensions/HelperMacros.h> +#include <cppunit/TestCase.h> +#include <stdexcept> + +class qa_encoder_convolutional_ic1_ic1 : public CppUnit::TestCase { + + CPPUNIT_TEST_SUITE (qa_encoder_convolutional_ic1_ic1); + CPPUNIT_TEST (t0); + CPPUNIT_TEST (t1); + CPPUNIT_TEST (t2); + CPPUNIT_TEST (t3); + CPPUNIT_TEST (t4); + CPPUNIT_TEST (t5); + CPPUNIT_TEST (t6); + CPPUNIT_TEST (t7); + CPPUNIT_TEST (t8); + CPPUNIT_TEST_SUITE_END (); + + private: + void do_encoder_check (const char** c_t1_in, + const char** c_t1_res, + int n_output_items, + int block_size_bits, + int n_code_inputs, + int n_code_outputs, + const int* code_generators, + const int* code_feedback = 0); + + void t0 (); + void t1 (); + void t2 (); + void t3 (); + void t4 (); + void t5 (); + void t6 (); + void t7 (); + void t8 (); +}; + +#endif /* INCLUDED_QA_ENCODER_CONVOLUTIONAL_IC1_IC1_H */ diff --git a/gr-error-correcting-codes/src/lib/libecc/tests/test_all.cc b/gr-error-correcting-codes/src/lib/libecc/tests/test_all.cc new file mode 100644 index 000000000..2cd6f663e --- /dev/null +++ b/gr-error-correcting-codes/src/lib/libecc/tests/test_all.cc @@ -0,0 +1,38 @@ +/* -*- 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. + */ + +#include <cppunit/TextTestRunner.h> +#include <qa_ecc.h> + +int +main +(int argc, + char **argv) +{ + CppUnit::TextTestRunner runner; + + runner.addTest (qa_ecc::suite ()); + + bool was_successful = runner.run ("", false); + + return ((was_successful == true) ? 0 : 1); +} |