3 * Copyright 2006 Free Software Foundation, Inc.
5 * This file is part of GNU Radio
7 * GNU Radio is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2, or (at your option)
12 * GNU Radio is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Radio; see the file COPYING. If not, write to
19 * the Free Software Foundation, Inc., 51 Franklin Street,
20 * Boston, MA 02110-1301, USA.
27 #include "decoder_viterbi_full_block.h"
32 const int g_max_block_size_bits = 10000000;
33 const int g_max_num_streams = 10;
34 const int g_num_bits_per_byte = 8;
36 #define DO_TIME_THOUGHPUT 0
38 #define DO_PRINT_DEBUG_INST 0
39 #define DO_PRINT_DEBUG_FSM 0
40 #define DO_PRINT_DEBUG_INIT 0
41 #define DO_PRINT_DEBUG_UP 0
42 #define DO_PRINT_DEBUG_UP_0 0
43 #define DO_PRINT_DEBUG_UP_1 0
44 #define DO_PRINT_DEBUG_MIDDLE 0
45 #define DO_PRINT_DEBUG_MIDDLE_0 0
46 #define DO_PRINT_DEBUG_MIDDLE_1 0
47 #define DO_PRINT_DEBUG_TERM 0
48 #define DO_PRINT_DEBUG_TERM_1 0
49 #define DO_PRINT_DEBUG_OUTPUT 0
50 #define DO_PRINT_DEBUG_OUTPUT_0 0
51 #define DO_PRINT_DEBUG_EXIT 0
52 #define DO_PRINT_DEBUG 1
55 #include <mld/mld_timer.h>
61 decoder_viterbi_full_block::decoder_viterbi_full_block
62 (int sample_precision,
63 encoder_convolutional* l_encoder)
64 : decoder_viterbi (sample_precision, l_encoder)
66 // verify that the block size is non-zero
68 if (d_block_size_bits == 0) {
69 std::cerr << "decoder_viterbi_full_block: Error: "
70 "Block size is 0, and must be positive for block decoding.\n";
74 // the traceback buffers are specific to the type of decoding
75 // (full/block, partial/block, partial/stream)
77 // create the traceback buffers; for full/block, use the total # of
78 // bits to decode + 1: each bit is represented by a transition
79 // between traceback elements.
81 d_n_traceback_els = d_n_total_inputs_per_stream + 1;
83 // create the output buffers:
84 // this is a 2d matrix structure, where the first dimension
85 // is the number of output bits; the second dimension is
86 // the number of states.
87 // When doing full blocks, each bit-time's state's traceback
88 // contains just the pointer to the previous bit-time's state's traceback
89 // as well as the inputs for that connection.
90 // No further work is required because each reverse-path is unique
91 // once a given end-bit-time's state is determined to be "the one".
93 traceback_t_hdl t_out_buf =
94 d_out_buf = new traceback_t_ptr [d_n_traceback_els];
95 for (size_t n = d_n_traceback_els; n > 0; n--) {
96 (*t_out_buf++) = new traceback_t [d_n_states];
99 if (DO_PRINT_DEBUG_INST) {
101 "total # in bits / stream = " << d_n_total_inputs_per_stream << "\n" <<
102 "d_n_traceback_els = " << d_n_traceback_els << "\n";
105 if (DO_PRINT_DEBUG_INST) {
106 traceback_t_hdl t_out_bufs = d_out_buf;
107 for (size_t n = 0; n < d_n_traceback_els; n++, *t_out_bufs++) {
108 traceback_t_ptr t_out_buf = *t_out_bufs;
109 for (size_t m = 0; m < d_n_states; m++, t_out_buf++) {
110 std::cout << "tb[" << n << "] = " << t_out_bufs <<
111 ", &tb[" << n << "][" << m << "] = " << (&d_out_buf[n][m]) <<
112 ", tb[" << n << "," << m << "] = " << t_out_buf << "\n";
118 decoder_viterbi_full_block::~decoder_viterbi_full_block
121 // delete the traceback buffers
123 traceback_t_hdl t_out_buf = d_out_buf;
124 for (size_t n = d_n_traceback_els; n > 0; n--) {
125 delete [] (*t_out_buf++);
131 decoder_viterbi_full_block::compute_n_input_items
132 (size_t n_output_bits)
138 decoder_viterbi_full_block::compute_n_output_bits
139 (size_t n_input_items)
145 decoder_viterbi_full_block::update_traceback__up
146 (size_t from_state_ndx,
152 size_t t_state_print_bits = d_total_memory + 1;
153 size_t t_mem_print_bits = d_max_memory + 2;
155 // update the traceback structure, depending on which variety it is
156 // doing full trellis before decoding; use d_out_buf
158 // get the current state & output state
160 traceback_t_ptr t_out_buf = &(d_out_buf[d_time_count]
162 traceback_t_ptr t_next_out_buf = &(d_out_buf[d_time_count+1]
164 if (DO_PRINT_DEBUG_UP_1) {
165 std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n" <<
166 "ndx[" << n << "] == " << from_state_ndx <<
167 ", s[" << n2bs(from_state_ndx,t_state_print_bits) <<
169 n2bs(t_state->d_max_state_ndx,t_state_print_bits) <<
170 ", input = " << n2bs(l_input, d_n_code_inputs+1) <<
171 ": " << t_next_out_buf << " => " << t_out_buf << "\n";
174 // and connect output to the current, set inputs on output
176 t_next_out_buf->d_prev = t_out_buf;
177 t_next_out_buf->d_inputs = l_input;
182 decoder_viterbi_full_block::update_traceback__middle
188 size_t t_state_print_bits = d_total_memory + 1;
189 size_t t_mem_print_bits = d_max_memory + 2;
191 // change which d_states' index to use as starting
195 // get the state's index for the "to" set of new inputs to get the
198 state_t_ptr t_state = d_states[d_states_ndx];
200 // update the traceback structure
201 // loop over all current states
203 traceback_t_ptr t_prev_out_bufs = d_out_buf[d_time_count];
204 traceback_t_ptr t_out_bufs = d_out_buf[d_time_count+1];
206 if (DO_PRINT_DEBUG_MIDDLE_1) {
207 std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n";
210 for (size_t n = d_n_states; n > 0; n--, t_state++) {
212 // simple: get the current state & output state
213 // and connect output to the current, set inputs on output
215 traceback_t_ptr t_out_buf = t_out_bufs++;
216 traceback_t_ptr t_prev_out_buf =
217 &(t_prev_out_bufs[t_state->d_max_state_ndx]);
219 if (DO_PRINT_DEBUG_MIDDLE_1) {
220 std::cout << "s[" << n2bs(d_n_states-n,t_state_print_bits) <<
222 n2bs(t_state->d_max_state_ndx,t_state_print_bits) <<
223 ", input = " << n2bs(t_state->d_max_input, d_n_code_inputs+1) <<
224 ": " << t_out_buf << " => " << t_prev_out_buf << "\n";
227 t_out_buf->d_prev = t_prev_out_buf;
228 t_out_buf->d_inputs = t_state->d_max_input;
235 decoder_viterbi_full_block::update_traceback__term
241 size_t t_state_print_bits = d_total_memory + 1;
242 size_t t_mem_print_bits = d_max_memory + 2;
244 // done with all states and all inputs; now update the traceback structure
245 // change which d_states' index to use as starting
247 // update the number of "up_term" states
249 // reduce the number of using states
250 t_n_up_down_ndx >>= d_n_code_inputs;
251 // reset the state's index for each set of new inputs
252 t_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx];
253 // update the traceback structure
254 // loop over all current states
255 traceback_t_ptr t_prev_out_bufs = d_out_buf[d_time_count];
256 traceback_t_ptr t_out_bufs = d_out_buf[d_time_count+1];
257 #if DO_PRINT_DEBUG_TERM_1
258 std::cout << "d_o_b[" << d_time_count+1 << "] => d_o_b prev\n";
260 // loop over all current stored "term" state indices
261 for (size_t n = 0; n < t_n_up_down_ndx; n++) {
262 // get the start index and then pointer to each of the "to" states,
263 // which hold the newest "max" stuff
264 size_t t_state_ndx = *t_state_ndx_ptr++;
265 state_t_ptr t_state = &(d_states[d_states_ndx][t_state_ndx]);
266 // simple: get the current state & output state
267 // and connect output to the current, set inputs on output
268 traceback_t_ptr t_out_buf = &(t_out_bufs[t_state_ndx]);
269 traceback_t_ptr t_prev_out_buf =
270 &(t_prev_out_bufs[t_state->d_max_state_ndx]);
271 #if DO_PRINT_DEBUG_TERM_1
272 std::cout << "ndx[" << n << "] == " << t_state_ndx <<
273 ", s[" << n2bs(t_state_ndx,t_state_print_bits) <<
275 n2bs(t_state->d_max_state_ndx,t_state_print_bits) <<
276 ", input = " << n2bs(t_state->d_max_input, d_n_code_inputs+1) <<
277 ": " << t_out_buf << " => " << t_prev_out_buf << "\n";
279 t_out_buf->d_prev = t_prev_out_buf;
280 t_out_buf->d_inputs = t_state->d_max_input;
281 // finished (for) this state
288 decoder_viterbi_full_block::decode_private
293 #if DO_TIME_THOUGHPUT
298 size_t t_state_print_bits = d_total_memory + 1;
299 size_t t_mem_print_bits = d_max_memory + 2;
301 // setup variables for quicker access
302 int t_in_buf_ndx = 0, t_out_buf_ndx = 0;
303 int t_out_bit_shift = 0;
304 int t_ninput_items = fixed_rate_noutput_to_ninput (noutput_items);
305 int t_noutput_bytes = noutput_items * d_out_stream_el_size_bytes;
307 #if DO_PRINT_DEBUG_INST
308 std::cout << "# output items = " << noutput_items << " (" <<
309 t_noutput_bytes << " Bytes, " << (t_noutput_bytes * g_num_bits_per_byte) <<
310 " bits), # input items = " << t_ninput_items << " Symbols\n";
311 for (size_t n = 0; n < ninput_items.size(); n++) {
312 std::cout << "# input items [" << n << "] = " << ninput_items[n] << "\n";
316 // put any leftover bits into the output
317 if (d_n_saved_bits != 0) {
318 // copy the leftover from the save buffer
319 // check to make sure it will all fit
320 size_t t_noutput_bits = t_noutput_bytes * g_num_bits_per_byte;
322 if (t_noutput_bits < d_n_saved_bits) {
323 // asking for fewer bits than available; set to copy
324 // just what's being asked for
325 t_n_copy = t_noutput_bytes;
327 // asking for at least as many bits as available; set to copy all
328 t_out_buf_ndx = d_n_saved_bits / g_num_bits_per_byte;
329 t_out_bit_shift = d_n_saved_bits % g_num_bits_per_byte;
330 t_n_copy = t_out_buf_ndx + (t_out_bit_shift != 0 ? 1 : 0);
332 // do the copy for all output streams (code inputs)
333 // copy starting at save buffer index "start"
334 for (size_t n = 0; n < d_n_code_inputs; n++)
335 bcopy (&(d_save_buffer[n][d_n_saved_bits_start_ndx]),
336 out_buf[n], t_n_copy);
337 #if DO_PRINT_DEBUG_INST
338 std::cout << "Copied " << t_n_copy << " Byte" <<
339 (t_n_copy != 1 ? "s" : "") << ": s_b[][" <<
340 d_n_saved_bits_start_ndx << "] => o_b[][0]\n" <<
341 "# saved bits = " << d_n_saved_bits <<
342 ", o_b_ndx = " << t_out_buf_ndx <<
343 ", bit shift = " << t_out_bit_shift << "\n";
345 // update the number of saved bits and start
346 if (t_noutput_bits < d_n_saved_bits) {
347 // asking for fewer bit than available: update
348 // the number of saved bits and their starting index
349 d_n_saved_bits_start_ndx += t_noutput_bytes;
350 d_n_saved_bits -= (t_noutput_bytes * g_num_bits_per_byte);
351 #if DO_PRINT_DEBUG_INST
352 std::cout << "Updated # saved bits = " << d_n_saved_bits <<
353 ", index = " << d_n_saved_bits_start_ndx << "\n";
355 // nothing to consume; return the desired number of output items
356 return (noutput_items);
358 d_n_saved_bits_start_ndx = d_n_saved_bits = 0;
361 #if DO_PRINT_DEBUG_INST
362 std::cout << "Starting FSM in state: " <<
363 (d_fsm == fsm_dec_init ? "init" :
364 (d_fsm == fsm_dec_doing_up ? "up" :
365 (d_fsm == fsm_dec_doing_middle ? "middle" :
366 (d_fsm == fsm_dec_doing_term ? "term" :
367 (d_fsm == fsm_dec_output ? "output" : "unknown"))))) << "\n";
370 // while there are input items to create
371 while (t_out_buf_ndx < t_noutput_bytes) {
372 #if DO_PRINT_DEBUG_FMS
373 std::cout << "Starting 'while': processing " << t_in_buf_ndx << " of " <<
374 t_ninput_items << " items.\nJumping to state '" <<
375 (d_fsm == fsm_dec_init ? "init" :
376 (d_fsm == fsm_dec_doing_up ? "up" :
377 (d_fsm == fsm_dec_doing_middle ? "middle" :
378 (d_fsm == fsm_dec_doing_term ? "term" :
379 (d_fsm == fsm_dec_output ? "output" : "unknown"))))) << "'\n";
381 // jump to the correct state in the fsm
383 case fsm_dec_doing_up:
384 #if DO_PRINT_DEBUG_FSM
385 std::cout << "Starting fsm_dec_doing_up\n";
387 // set the number of up_down indices
388 size_t t_n_up_down_ndx = 1 << (d_n_code_inputs *
390 // stay in this state until the correct number of input symbols are
391 // reached; exit also if we run out of input symbols to process
392 while ((d_time_count < d_max_memory) &
393 (t_in_buf_ndx < t_ninput_items)) {
394 #if DO_PRINT_DEBUG_UP_0
395 std::cout << "Doing 'while' loop:\n" <<
396 "t_n_up_down_ndx = " << t_n_up_down_ndx << "\n" <<
397 "d_time_count = " << d_time_count << "\n" <<
398 "d_max_memory = " << d_max_memory << "\n" <<
399 "t_in_buf_ndx = " << t_in_buf_ndx << "\n" <<
400 "t_ninput_items = " << t_ninput_items << "\n";
402 // use the "from" states, loop over all inputs and compute the metric for
403 // each & store it in the "to" state at the end of the connection.
404 // no need to compare metrics yet, since none join into any given state
407 // reset the "to" state's metrics
408 // probably don't need to do this; try removing later
409 reset_metrics (d_states_ndx ^ 1);
410 #if DO_PRINT_DEBUG_UP
411 std::cout << "Reset Metrics\n";
415 // reset the state's index for each set of new inputs
416 size_t* t_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx];
417 size_t* t_next_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx ^ 1];
418 // loop over all current stored "up" states
419 for (size_t n = 0; n < t_n_up_down_ndx; n++) {
420 size_t t_state_ndx = *t_state_ndx_ptr++;
421 // get a pointer to this state's structure
422 state_t_ptr t_state = &(d_states[d_states_ndx][t_state_ndx]);
423 // get the connections for all inputs
424 connection_t_ptr t_connection = t_state->d_connections;
425 #if DO_PRINT_DEBUG_UP_0
426 std::cout << "Looping over all 'up' states:\n" <<
427 "n = " << n << "\n" <<
428 "t_n_up_down_ndx = " << t_n_up_down_ndx << "\n" <<
429 "d_states_ndx = " << d_states_ndx << "\n" <<
430 "t_state_ndx = " << t_state_ndx << "\n" <<
431 "d_n_input_combs = " << d_n_input_combinations << "\n" <<
432 "t_state = " << t_state << "\n" <<
433 "t_connection = " << t_connection << "\n";
435 // loop over all possible input values, 1 bit per input stream
436 for (size_t q = 0; q < d_n_input_combinations; q++, t_connection++) {
437 // find the "to" state for this connection
438 state_t_ptr t_to_state = t_connection->d_to;
439 // get the output bits for this connection
440 float* t_output_bit = t_connection->d_output_bits;
441 // start with this state's metric
442 float t_metric = t_state->d_max_metric;
443 #if DO_PRINT_DEBUG_UP_0
445 "to state index = " << t_connection->d_to_ndx << "\n" <<
446 "current metric = " << t_metric << "\n";
448 if (d_do_mux_inputs == true) {
449 // if using mux'ed input streams, handle differently
450 const float* t_in_buf = &(in_buf[0][t_in_buf_ndx]);
451 // loop over all encoder-output values
452 for (size_t r = d_n_code_outputs; r > 0; r--) {
453 #if DO_PRINT_DEBUG_UP
454 std::cout << "in_sym = " << *t_in_buf << ", code_out_bit = " <<
455 *t_output_bit << " ==> metric -> ";
457 t_metric += ((*t_in_buf++) * (*t_output_bit++));
458 #if DO_PRINT_DEBUG_UP
459 std::cout << t_metric << "\n";
463 // loop over all encoder-output values
464 for (size_t r = 0; r < d_n_code_outputs; r++) {
465 #if DO_PRINT_DEBUG_UP
466 std::cout << "in_sym = " << in_buf[r][t_in_buf_ndx] <<
467 ", code_out_bit = " << *t_output_bit << " ==> metric -> ";
469 t_metric += (in_buf[r][t_in_buf_ndx] * (*t_output_bit++));
470 #if DO_PRINT_DEBUG_UP
471 std::cout << t_metric << "\n";
475 // get the "to" state index
477 size_t t_to_ndx = t_connection->d_to_ndx;
479 // store the metric in the "to" state; should not have
482 t_to_state->d_max_metric = t_metric;
484 // add the "to" state index to the "up" state list
486 *t_next_state_ndx_ptr++ = t_to_ndx;
488 // update the traceback structure
490 update_traceback__up (t_state, t_to_state, q);
492 // next (for) input value
495 // next (for) "up_term" state
498 // increment the input buffer indices
500 increment_input_indices (false);
502 // increment the time counter
506 // change which up-term index to use
510 // increase the number of states to be used
512 t_n_up_down_ndx <<= d_n_code_inputs;
514 // change which d_states' index to use as starting
518 // next (while) input
521 // if reached the end of doing the "up" part of the trellis,
522 // switch states into the middle
524 if (d_time_count == d_max_memory) {
525 if (DO_PRINT_DEBUG_FSM) {
526 std::cout << "Setting FSM to fsm_dec_doing_middle\n";
528 d_fsm = fsm_dec_doing_middle;
530 if (DO_PRINT_DEBUG_FSM) {
531 std::cout << "Exited fsm_dec_doing_up\n";
535 case (fsm_dec_doing_middle):
536 if (DO_PRINT_DEBUG_FSM) {
537 std::cout << "Entered fsm_dec_doing_middle\n";
540 // stay in this state until a full block (+ optional
541 // termination) of input metrics is reached, or until there are
542 // no more input metrics to parse
544 while ((d_time_count < d_block_size_bits) &
545 (t_in_buf_ndx < t_ninput_items)) {
547 // use all states, loop over all inputs, compute the metric
548 // for each; compare the current metric with all previous
549 // stored metric in the endpoint of the connection to find the
552 // reset the "to" state's metrics
554 reset_metrics (d_states_ndx ^ 1);
556 // get the state's index for each set of new inputs
558 state_t_ptr t_state = d_states[d_states_ndx];
560 if (DO_PRINT_DEBUG_MIDDLE) {
561 std::cout << "Time Count " << (d_time_count+1) << " of " <<
562 d_block_size_bits << "\nd_states_ndx = " << d_states_ndx << "\n";
565 // loop over all current states
567 for (size_t n = 0; n < d_n_states; n++, t_state++) {
569 // loop over all possible input values, 1 bit per input stream
571 connection_t_ptr t_connection = t_state->d_connections;
573 if (DO_PRINT_DEBUG_MIDDLE_0) {
574 std::cout << "Looping over all 'middle' states: " <<
575 n << " of " << d_n_states << "\n";
578 for (size_t q = 0; q < d_n_input_combinations; q++, t_connection++) {
580 if (DO_PRINT_DEBUG_MIDDLE_0) {
581 std::cout << "Input = " << n2bs(q, d_n_code_inputs+1) << "\n";
584 // start with this state's metric
586 float t_metric = t_state->d_max_metric;
588 // get the "to" state
590 state_t_ptr t_to_state = t_connection->d_to;
592 // get that state's metric
594 float t_to_metric = t_to_state->d_max_metric;
596 // see if the computation is even needed;
597 // maximum change is d_n_code_outputs if all bits match exactly
599 if ((t_to_metric - t_metric) > ((float) 2*d_n_code_outputs)) {
600 if (DO_PRINT_DEBUG_MIDDLE_0) {
601 std::cout << "!not computing metric!\n";
606 // metrics are close enough; do the computation and the
607 // compare get the output bits for this connection
609 float* t_output_bit = t_connection->d_output_bits;
610 if (d_do_mux_inputs == true) {
612 // if using mux'ed input streams, handle differently
614 const float* t_in_buf = &(in_buf[0][t_in_buf_ndx]);
616 // loop over all encoder-output values
618 for (size_t r = d_n_code_outputs; r > 0; r--) {
619 #if DO_PRINT_DEBUG_MIDDLE_0
620 std::cout << "in_sym = " << *t_in_buf << ", code_out_bit = " <<
621 *t_output_bit << " ==> metric -> ";
623 t_metric += ((*t_in_buf++) * (*t_output_bit++));
624 #if DO_PRINT_DEBUG_MIDDLE_0
625 std::cout << t_metric << "\n";
629 // loop over all encoder-output values
630 for (size_t r = 0; r < d_n_code_outputs; r++) {
631 #if DO_PRINT_DEBUG_MIDDLE_0
632 std::cout << "in_sym = " << in_buf[r][t_in_buf_ndx] <<
633 ", code_out_bit = " << *t_output_bit << " ==> metric -> ";
635 t_metric += (in_buf[r][t_in_buf_ndx] * (*t_output_bit++));
636 #if DO_PRINT_DEBUG_MIDDLE_0
637 std::cout << t_metric << "\n";
641 // done with this input value; compare old and new metrics
642 if (t_metric > t_to_metric) {
643 #if DO_PRINT_DEBUG_MIDDLE
644 std::cout << "New Metric to s[" <<
645 n2bs (t_connection->d_to_ndx,t_state_print_bits) << "]: ";
646 if (t_to_state->d_max_metric == -1e10) {
647 std::cout << "setting to ";
649 std::cout << "was s[" <<
650 n2bs(t_to_state->d_max_state_ndx,t_state_print_bits) <<
651 "]i[" << n2bs (t_to_state->d_max_input, d_n_code_inputs+1) <<
652 "]@ " << t_to_state->d_max_metric << " now ";
654 std::cout << "s[" << n2bs(n,t_state_print_bits) << "] i[" <<
655 n2bs (q, d_n_code_inputs+1) << "]@ " << t_metric << "\n";
657 // new metric is better; copy that info into the "to" state
658 t_to_state->d_max_metric = t_metric;
659 t_to_state->d_max_state_ndx = n;
660 t_to_state->d_max_input = q;
662 // next (for) input value
667 // done with all states and all inputs;
668 // update the traceback buffers
670 update_traceback__middle ();
672 // increment the input buffer indices
674 increment_input_indices ();
676 // increment the time counter
680 // check (while) staying in this fsm state or not
683 if ((d_block_size_bits != 0) &
684 (d_time_count == d_block_size_bits)) {
685 if (DO_PRINT_DEBUG_FSM) {
686 std::cout << "Setting FSM to fsm_dec_doing_term\n";
688 d_fsm = fsm_dec_doing_term;
690 if (DO_PRINT_DEBUG_FSM) {
691 std::cout << "Exited fsm_dec_doing_middle\n";
695 case (fsm_dec_doing_term):
696 if (DO_PRINT_DEBUG_FSM) {
697 std::cout << "Entered fsm_dec_doing_term\n";
700 // set the "next" up_down index to the end of their states
702 size_t t_time_count = d_max_memory - (d_time_count - d_block_size_bits);
703 t_n_up_down_ndx = 1 << (d_n_code_inputs * t_time_count);
705 // stay in this state until the correct number of input metrics
706 // are reached; exit if we run out of input metrics to process
708 while ((t_time_count > 0) &
709 (t_in_buf_ndx < t_ninput_items)) {
711 if (DO_PRINT_DEBUG_TERM) {
712 std::cout << "Doing time " << (d_max_memory - t_time_count + 1) <<
713 " of " << d_max_memory << "; starting buf[" << t_in_buf_ndx <<
714 "] of [" << t_ninput_items << "]\n";
717 // FIXME: loop over just the "0" inputs
719 // use the "to" states, and compute the metric for each,
720 // compare & store it in the "to" state at the end of the
723 // reset the "to" state's metrics
725 reset_metrics (d_states_ndx ^ 1);
727 // reset the state's index for each set of new inputs
729 size_t* t_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx];
730 size_t* t_next_state_ndx_ptr = d_up_term_states_ndx[d_up_term_ndx ^ 1];
732 // loop over all current stored "term" state indeces
734 for (size_t n = 0; n < t_n_up_down_ndx; n++) {
735 size_t t_state_ndx = *t_state_ndx_ptr++;
736 state_t_ptr t_state = &(d_states[d_states_ndx][t_state_ndx]);
738 // loop over just the all 0 input value (d_connections[0])
740 connection_t_ptr t_connection = t_state->d_connections;
742 // get the "to" state
744 state_t_ptr t_to_state = t_connection->d_to;
746 // start with this state's metric
748 float t_metric = t_state->d_max_metric;
750 // get that state's metric
752 float t_to_metric = t_to_state->d_max_metric;
754 if (DO_PRINT_DEBUG_TERM) {
755 std::cout << "Term state " << (n+1) << " of " <<
756 t_n_up_down_ndx << "; using d_s[" << d_states_ndx << "][" <<
757 n2bs(t_state_ndx,t_state_print_bits) << "]\n";
760 // see if the computation is even needed;
761 // maximum change is d_n_code_outputs if all bits match exactly
763 if ((t_to_metric - t_metric) > ((float) 2*d_n_code_outputs)) {
764 if (DO_PRINT_DEBUG_TERM) {
765 std::cout << "!not computing metric!\n";
770 // metrics are close enough; do the computation and the
771 // compare get the output bits for this connection
773 float* t_output_bit = t_connection->d_output_bits;
774 if (d_do_mux_inputs == true) {
775 // if using mux'ed input streams, handle differently
776 const float* t_in_buf = &(in_buf[0][t_in_buf_ndx]);
777 // loop over all encoder-output values
778 for (size_t r = d_n_code_outputs; r > 0; r--) {
779 t_metric += ((*t_in_buf++) * (*t_output_bit++));
782 // loop over all encoder-output values
783 for (size_t r = 0; r < d_n_code_outputs; r++) {
784 t_metric += (in_buf[r][t_in_buf_ndx] * (*t_output_bit++));
787 // done with this input value; compare old and new metrics
788 // see if it's the best metric
789 if (t_metric > t_to_metric) {
790 #if DO_PRINT_DEBUG_TERM
791 std::cout << "New Metric to s[" <<
792 n2bs (t_connection->d_to_ndx,t_state_print_bits) << "]: ";
793 if (t_to_state->d_max_metric == -1e10) {
794 std::cout << "setting to ";
796 std::cout << "was s[" <<
797 n2bs(t_to_state->d_max_state_ndx,t_state_print_bits) <<
798 "]i[" << n2bs (t_to_state->d_max_input, d_n_code_inputs+1) <<
799 "]@ " << t_to_state->d_max_metric << " now ";
801 std::cout << "s[" << n2bs(t_state_ndx,t_state_print_bits) <<
802 "] i[" << n2bs (0, d_n_code_inputs+1) << "]@ " << t_metric << "\n";
804 t_to_state->d_max_metric = t_metric;
805 t_to_state->d_max_state_ndx = t_state_ndx;
806 t_to_state->d_max_input = 0;
808 // add the "to" state's index to the "next" set of state's indices list
809 *t_next_state_ndx_ptr++ = t_connection->d_to_ndx;
810 // finished (for) this state
813 // update the traceback buffers
815 update_traceback__term ();
816 increment_input_indices (false);
818 // increment the time counters
823 // finished (while) staying in this fsm state or not
827 if (t_time_count == 0) {
828 // finished this trellis, now move as much of the decoded
829 // input to the output buffer as possible
830 if (DO_PRINT_DEBUG_FSM) {
831 std::cout << "Setting FSM to fsm_dec_output\n";
833 d_fsm = fsm_dec_output;
835 if (DO_PRINT_DEBUG_FSM) {
836 std::cout << "Exited fsm_dec_doing_term\n";
840 case (fsm_dec_output):
841 if (DO_PRINT_DEBUG_FSM) {
842 std::cout << "Entered fsm_dec_output.\n";
845 // this is done in reverse bit order (last time to first time)
846 // using the traceback structure in d_out_buf, starting with the
847 // maximum valued one in the last time slot, then using the
848 // traceback's "d_prev" link to trace the trellis back
850 // see where the output data will terminate
852 int t_next_out_buf_ndx = (t_out_buf_ndx +
853 (d_block_size_bits / g_num_bits_per_byte));
854 int t_next_out_bit_shift = (t_out_bit_shift +
855 (d_block_size_bits % g_num_bits_per_byte));
856 if (t_next_out_bit_shift >= g_num_bits_per_byte) {
857 t_next_out_bit_shift -= g_num_bits_per_byte;
858 t_next_out_buf_ndx++;
860 #if DO_PRINT_DEBUG_OUTPUT
861 std::cout << "First bit in at out[][" << t_out_buf_ndx << "].[" <<
862 t_out_bit_shift << "] -> " << d_block_size_bits << " bits == " <<
863 (d_block_size_bits / g_num_bits_per_byte) << " Byte" <<
864 ((d_block_size_bits / g_num_bits_per_byte) != 1 ? "s" : "") <<
865 " + " << (d_block_size_bits % g_num_bits_per_byte) << " bit" <<
866 ((d_block_size_bits % g_num_bits_per_byte) != 1 ? "s" : "") <<
867 "\nNext set of bits start at out[][" << t_next_out_buf_ndx <<
868 "].[" << t_next_out_bit_shift << "]\n";
870 // find the starting traceback structure
871 traceback_t_ptr t_out_buf;
872 if (d_do_termination == true) {
873 // FIXME: assume termination state == 0
874 #if DO_PRINT_DEBUG_OUTPUT_0
875 std::cout << "Using termination; going through trellis for " <<
876 d_max_memory << " bit" <<
877 ((d_max_memory != 1) ? "s" : "") << "\n";
879 t_out_buf = &(d_out_buf[d_time_count][0]);
880 #if DO_PRINT_DEBUG_OUTPUT_0
881 std::cout << "Starting traceback ptr " << t_out_buf << "\n";
883 // skip over the termination bits
884 for (size_t n = d_max_memory; n > 0; n--) {
885 t_out_buf = t_out_buf->d_prev;
886 #if DO_PRINT_DEBUG_OUTPUT_0
887 std::cout << "Next traceback ptr " << t_out_buf << "\n";
891 // no termination but doing block coding;
892 // FIXME: use the state with the bext metric
893 // get the state's index for each set of new inputs
894 state_t_ptr t_state = d_states[d_states_ndx];
895 float t_max_metric = t_state->d_max_metric;
896 size_t t_max_state_ndx = 0;
898 // loop over all current states
899 for (size_t n = 1; n < d_n_states; n++, t_state++) {
900 // start with this state's metric
901 float t_metric = t_state->d_max_metric;
902 // compare with current max
903 if (t_metric > t_max_metric) {
904 t_max_metric = t_metric;
908 // get the correct out_buf reference to start with
909 t_out_buf = &(d_out_buf[d_time_count][t_max_state_ndx]);
911 #if DO_PRINT_DEBUG_OUTPUT
912 std::cout << "Found starting traceback ptr " << t_out_buf <<
913 "; getting all " << d_block_size_bits << " bits per stream.\n";
915 // now we've got the starting traceback structure address;
916 // check to make sure there is enough space in each output buffer
917 size_t t_block_bit_ndx = d_block_size_bits;
918 if ((t_next_out_buf_ndx > t_noutput_bytes) |
919 ((t_next_out_buf_ndx == t_noutput_bytes) &
920 (t_next_out_bit_shift != 0))) {
921 // not enough space for all output bits;
922 // find the number of extra bits to save
923 size_t t_save_buf_ndx = t_next_out_buf_ndx - t_noutput_bytes;
924 size_t t_n_extra_bits = ((t_save_buf_ndx * g_num_bits_per_byte) +
925 t_next_out_bit_shift);
926 // set the number of saved bits
927 d_n_saved_bits = t_n_extra_bits;
928 // remove the extra bits from the number to copy to the output buffer
929 t_block_bit_ndx -= t_n_extra_bits;
930 // find the actual output buf index, once we get there
931 t_next_out_buf_ndx -= t_save_buf_ndx;
932 #if DO_PRINT_DEBUG_OUTPUT
933 std::cout << "Not enough output buffer space:\n" <<
934 "len (o_b) = " << t_noutput_bytes << " ==> " <<
935 t_n_extra_bits << " extra bit" <<
936 (t_n_extra_bits != 1 ? "s" : "") << " == " <<
937 t_save_buf_ndx << " Byte" <<
938 (t_save_buf_ndx != 1 ? "s" : "") << ", " <<
939 t_next_out_bit_shift << " bit" <<
940 (t_next_out_bit_shift != 1 ? "s" : "") << "\n";
942 // zero each output buffers' bytes
943 size_t t_n_zero = t_save_buf_ndx + (t_next_out_bit_shift ? 1 : 0);
944 #if DO_PRINT_DEBUG_OUTPUT
945 size_t t_n_out_bytes = ((d_block_size_bits / g_num_bits_per_byte) +
946 ((d_block_size_bits % g_num_bits_per_byte) ? 1 : 0));
947 std::cout << "Zeroing save buffer from for " << t_n_zero <<
948 " Byte" << (t_n_zero != 1 ? "s" : "") << " (of " <<
949 d_block_size_bits << " bit" <<
950 (d_block_size_bits != 1 ? "s" : "") << " == " << t_n_out_bytes <<
951 " Byte" << (t_n_out_bytes != 1 ? "s" : "") << ")\n";
953 for (size_t m = 0; m < d_n_code_inputs; m++)
954 bzero (d_save_buffer[m], t_n_zero);
955 // loop over all extra bits
956 for (size_t n = t_n_extra_bits; n > 0; n--) {
957 // first decrement the output bit & byte as necessary
958 if (--t_next_out_bit_shift < 0) {
959 t_next_out_bit_shift += g_num_bits_per_byte;
962 // get the encoder inputs to output
963 size_t t_inputs = t_out_buf->d_inputs;
964 // loop over all code inputs (decoder-outputs), 1 bit per stream
965 for (size_t m = 0; m < d_n_code_inputs; m++) {
966 d_save_buffer[m][t_save_buf_ndx] |=
967 ((t_inputs & 1) << t_next_out_bit_shift);
970 t_out_buf = t_out_buf->d_prev;
971 #if DO_PRINT_DEBUG_OUTPUT_0
972 std::cout << "Next traceback ptr " << t_out_buf << "\n";
975 // at exit, "t_out_buf_ndx" should be == t_noutput_bytes, and
976 // "t_out_bit_shift" should be 0; check these!
977 #if DO_PRINT_DEBUG_OUTPUT
978 std::cout << "n_o_b_ndx (" << t_next_out_buf_ndx << ") ?=? " <<
979 "#o_B (" << t_noutput_bytes << ") & t_o_b_sh (" <<
980 t_next_out_bit_shift << ") ?=? 0\n";
981 assert (t_next_out_buf_ndx == t_noutput_bytes);
982 assert (t_next_out_bit_shift == 0);
985 // set the correct output buffer index and bit shift
986 t_out_bit_shift = t_next_out_bit_shift;
987 t_out_buf_ndx = t_next_out_buf_ndx;
988 // copy any remaining bits looping backwards in bit-time
989 // through the traceback trellis
990 for (size_t n = t_block_bit_ndx; n > 0; n--) {
991 // first decrement the output bit & byte as necessary
992 if (--t_out_bit_shift < 0) {
993 t_out_bit_shift += g_num_bits_per_byte;
996 // get the encoder inputs to output
997 size_t t_inputs = t_out_buf->d_inputs;
998 // loop over all code inputs (decoder-outputs), 1 bit per stream
999 for (size_t m = 0; m < d_n_code_inputs; m++) {
1000 out_buf[m][t_out_buf_ndx] |= ((t_inputs & 1) << t_out_bit_shift);
1003 t_out_buf = t_out_buf->d_prev;
1004 #if DO_PRINT_DEBUG_OUTPUT_0
1005 std::cout << "Next traceback ptr " << t_out_buf << "\n";
1008 // set the next output byte and bit-shift
1009 t_out_bit_shift = t_next_out_bit_shift;
1010 t_out_buf_ndx = t_next_out_buf_ndx;
1011 #if DO_PRINT_DEBUG_FSM
1012 std::cout << "Set FSM to fsm_dec_init\n";
1014 d_fsm = fsm_dec_init;
1015 #if DO_PRINT_DEBUG_FSM
1016 std::cout << "Exited fsm_dec_output\n";
1019 case (fsm_dec_init):
1020 #if DO_PRINT_DEBUG_FSM
1021 std::cout << "Entered fsm_dec_init\n";
1023 // this is called immediately (first input bit upon startup),
1024 // or after termination of a trellis.
1026 // reset states to the 0'th one
1027 d_up_term_ndx = d_states_ndx = 0;
1028 // zero the metrics for those states
1031 // might not need to do this; check and see after it works
1032 // reset up_term states and number so that there is 1 item, the "0" state.
1033 bzero (d_up_term_states_ndx[0], sizeof (size_t) * d_n_states);
1034 bzero (d_up_term_states_ndx[1], sizeof (size_t) * d_n_states);
1036 d_up_term_states_ndx[0][0] = 0;
1038 // reset time count back to the start
1041 // reset the traceback structures
1042 // might not need to do this; check and see after it works
1043 traceback_t_hdl t_out_bufs = d_out_buf;
1044 for (size_t n = d_n_traceback_els; n > 0; n--) {
1045 traceback_t_ptr t_out_buf = (*t_out_bufs++);
1046 for (size_t m = d_n_states; m > 0; m--, t_out_buf++) {
1047 t_out_buf->d_prev = NULL;
1048 t_out_buf->d_inputs = -1;
1052 // set the fsm to "doing up"
1053 #if DO_PRINT_DEBUG_FSM
1054 std::cout << "Set FSM to fsm_dec_doing_up\n";
1056 d_fsm = fsm_dec_doing_up;
1057 #if DO_PRINT_DEBUG_FSM
1058 std::cout << "Exited fsm_dec_init\n";
1061 // should never get here!
1064 // done (switch) with FSM
1066 // done (while) there are inputs
1069 // consume all of the input items on all input streams
1070 // "ninput_items[]" doesn't seem to be reliable,
1071 // so compute this from the actual number of blocks processed
1072 #if DO_PRINT_DEBUG_EXIT
1073 std::cout << "Exiting FSM in state: " <<
1074 (d_fsm == fsm_dec_init ? "init" :
1075 (d_fsm == fsm_dec_doing_up ? "up" :
1076 (d_fsm == fsm_dec_doing_middle ? "middle" :
1077 (d_fsm == fsm_dec_doing_term ? "term" :
1078 (d_fsm == fsm_dec_output ? "output" : "unknown"))))) << "\n" <<
1079 "Consuming " << t_in_buf_ndx <<
1080 " input items on each input stream (of " << t_ninput_items << ").\n";
1082 consume_each (t_in_buf_ndx);
1084 // make sure the number of output items makes sense
1085 // t_out_buf_ndx always points to the current index
1086 // t_out_bit_shift always points to the next bit position to be written
1087 int t_leftover_bytes = t_out_buf_ndx % d_out_stream_el_size_bytes;
1088 int t_leftover_bits = ((t_leftover_bytes * g_num_bits_per_byte) +
1090 int t_noutput_items = noutput_items;
1091 #if DO_PRINT_DEBUG_EXIT
1092 std::cout << "Final o_b[" << t_out_buf_ndx << "][" <<
1093 t_out_bit_shift << "] of " << t_noutput_bytes <<
1094 ", el_size = " << d_out_stream_el_size_bytes <<
1095 ", lo_Bytes = " << t_leftover_bytes <<
1096 ", t_lo_bits = " << t_leftover_bits << "\n" <<
1097 "Desired # output items = " << noutput_items << "\n";
1099 if (t_leftover_bits != 0) {
1100 // should never get here!
1104 int t_ndx = t_out_buf_ndx - t_leftover_bytes;
1105 size_t t_n_copy = t_leftover_bytes + ((t_out_bit_shift != 0) ? 1 : 0);
1106 assert (t_n_copy <= d_out_stream_el_size_bytes);
1107 // copy the leftover into the save buffer
1108 for (size_t n = 0; n < d_n_code_inputs; n++) {
1109 bcopy (&(out_buf[n][t_ndx]), d_save_buffer[n], t_n_copy);
1111 t_noutput_items = t_ndx / d_out_stream_el_size_bytes;
1112 d_n_saved_bits = t_leftover_bits;
1113 #if DO_PRINT_DEBUG_EXIT
1114 std::cout << "Copied " << t_n_copy << " Byte" <<
1115 (t_n_copy != 1 ? "s" : "") << " from o_b[][" << t_ndx <<
1116 "] into each save buffer.\n" <<
1117 "Actual #output items = " << t_noutput_items <<
1118 ", # saved bit(s) = " << d_n_saved_bits << "\n";
1125 #if DO_TIME_THOUGHPUT
1126 u_long d_t = end_timer (&t_tp);
1128 std::cout << "decoder_viterbi_full_block: Completed " << t_ninput_items <<
1129 " bits in " << d_t << " usec => " <<
1130 1e6*(((double)(t_ninput_items))/((double) d_t)) <<