40 int i, j, temp, out, w = 0, shiftreg = state;
42 shiftreg = shiftreg | (int(input) <<
m);
43 for (j = 0; j <
n; j++) {
47 for (i = 0; i <
K; i++) {
59 int i, j, temp, out, w = 0, shiftreg = state;
61 shiftreg = shiftreg | (int(input) <<
m);
62 for (j = 0; j <
n; j++) {
66 for (i = 0; i <
K; i++) {
78 int i, j, temp, out, shiftreg = state;
82 shiftreg = shiftreg | (1 <<
m);
83 for (j = 0; j <
n; j++) {
87 for (i = 0; i <
m; i++) {
92 w1 += out ^(temp & 1);
99 int i, j, temp, out, shiftreg = state;
103 shiftreg = shiftreg | (1 <<
m);
104 for (j = 0; j <
n; j++) {
108 for (i = 0; i <
m; i++) {
113 w1 += out ^(temp & 1);
122 it_error_if((pmatrix.rows() !=
n) || (pmatrix.cols() == 0),
"Wrong size of puncture matrix");
129 for (j = 0; j <
n; j++) {
130 for (p = 0; p <
Period; p++)
158 int nn = 0, i, p = 0, j;
160 for (i = 0; i < int(output.size() /
n); i++) {
161 for (j = 0; j <
n; j++) {
163 output(nn) = output(i *
n + j);
169 output.set_size(nn,
true);
176 int nn = 0, i, p = 0, j;
178 for (i = 0; i < int(output.size() /
n); i++) {
179 for (j = 0; j <
n; j++) {
181 output(nn) = output(i *
n + j);
187 output.set_size(nn,
true);
194 int nn = 0, i, p = 0, j;
196 for (i = 0; i < int(output.size() /
n); i++) {
197 for (j = 0; j <
n; j++) {
199 output(nn) = output(i *
n + j);
205 output.set_size(nn,
true);
212 it_error(
"Punctured_Convolutional_Code::decode(bvec, bvec); hard-decision decoding is not implemented");
217 it_error(
"Punctured_Convolutional_Code::decode(bvec, bvec); hard-decision decoding is not implemented");
246 int nn = 0, i = 0, p = received_signal.size() /
total, j;
248 int temp_size = p *
Period *
n;
251 p = received_signal.size() - p *
total;
255 for (j = 0; j <
n; j++) {
263 it_warning(
"Punctured_Convolutional_Code::decode(): Improper length of " 264 "the received punctured block, dummy bits have been added");
272 while (nn < temp.size()) {
274 temp(nn) = received_signal(i);
296 int nn = 0, i = 0, p = received_signal.size() /
total, j;
298 int temp_size = p *
Period *
n;
301 p = received_signal.size() - p *
total;
305 for (j = 0; j <
n; j++) {
313 it_warning(
"Punctured_Convolutional_Code::decode_tail(): Improper length " 314 "of the received punctured block, dummy bits have been added");
323 while (nn < temp.size()) {
325 temp(nn) = received_signal(i);
347 int nn = 0, i = 0, p = received_signal.size() /
total, j;
349 int temp_size = p *
Period *
n;
352 p = received_signal.size() - p *
total;
356 for (j = 0; j <
n; j++) {
364 it_warning(
"Punctured_Convolutional_Code::decode_tailbite(): Improper " 365 "length of the received punctured block, dummy bits have been " 375 while (nn < temp.size()) {
377 temp(nn) = received_signal(i);
404 bool Punctured_Convolutional_Code::inverse_tail(
const bvec coded_sequence, bvec &input)
406 int state = 0, zero_state, one_state, zero_temp, one_temp, i, j, p = 0, prev_pos = 0, no_symbols;
407 int block_length = 0;
408 bvec zero_output(
n), one_output(
n), temp_output(
n);
410 block_length = coded_sequence.size() *
Period /
total -
m;
412 it_error_if(block_length <= 0,
"The input sequence is to short");
413 input.set_length(block_length,
false);
417 for (i = 0; i < block_length; i++) {
419 one_state = state | (1 <<
m);
421 for (j = 0; j <
n; j++) {
423 zero_temp = zero_state &
gen_pol(j);
424 one_temp = one_state &
gen_pol(j);
430 if (coded_sequence.mid(prev_pos, no_symbols) == zero_output.left(no_symbols)) {
432 state = zero_state >> 1;
434 else if (coded_sequence.mid(prev_pos, no_symbols) == one_output.left(no_symbols)) {
436 state = one_state >> 1;
441 prev_pos += no_symbols;
457 int max_stack_size = 50000;
458 ivec S_stack(max_stack_size), t_stack(max_stack_size);
459 int start, S, W0, W1, S0, S1, pos, t = 0;
462 for (pos = 0; pos <
Period; pos++) {
463 for (start = 0; start < (1 <<
m); start++) {
469 if (t > (1 <<
m) *
Period) {
return true; }
473 if (W1 > 0) {
goto node0; }
474 if ((W0 == 0) && (S0 == start) && (((pos + t + 1) %
Period) == pos)) {
return true; }
475 if ((W0 == 0) && (S0 == 0) && (S != 0)) {
return true; }
476 if ((S0 != 0) && (W0 == 0)) {
478 if (stack_pos >= max_stack_size) {
479 max_stack_size = 2 * max_stack_size;
480 S_stack.set_size(max_stack_size,
true);
481 t_stack.set_size(max_stack_size,
true);
483 S_stack(stack_pos) = S0;
484 t_stack(stack_pos) = t + 1;
486 if ((W1 == 0) && (S1 == start) && (((pos + t + 1) %
Period) == pos)) {
return true; }
492 if (W0 > 0)
goto stack;
493 if ((W0 == 0) && (S0 == start) && (((pos + t + 1) %
Period) == pos)) {
return true; }
494 if ((W0 == 0) && (S0 == 0) && (S != 0)) {
return true; }
505 if (stack_pos >= 0) {
506 S = S_stack(stack_pos);
507 t = t_stack(stack_pos);
518 int max_stack_size = 50000;
519 ivec S_stack(max_stack_size), W_stack(max_stack_size), t_stack(max_stack_size);
521 int stack_pos = -1, t, S, W, W0, w0, w1;
529 W =
weight(0, 1, start_time);
543 if (W0 < dist_prof(
m)) {
545 if (stack_pos >= max_stack_size) {
546 max_stack_size = 2 * max_stack_size;
547 S_stack.set_size(max_stack_size,
true);
548 W_stack.set_size(max_stack_size,
true);
549 t_stack.set_size(max_stack_size,
true);
552 W_stack(stack_pos) = W0;
553 t_stack(stack_pos) = t + 1;
559 if (W > dist_prof(
m))
565 if (W < dist_prof(t))
568 if (t ==
m)
goto stack;
573 if (stack_pos >= 0) {
575 S = S_stack(stack_pos);
576 W = W_stack(stack_pos);
577 t = t_stack(stack_pos);
580 if (W < dist_prof(t))
583 if (t ==
m)
goto stack;
590 int d_best_so_far,
bool test_catastrophic)
592 int cat_treshold = (1 <<
m) *
Period;
594 ivec dist_prof(
K), dist_prof_rev(
K), dist_prof_temp(
K);
600 int dist_prof_rev0 = dist_prof_rev(0);
605 for (i = 1; i <
Period; i++) {
608 for (j = 0; j <
K; j++) {
609 if (dist_prof_temp(j) < dist_prof_rev(j)) {
610 dist_prof_rev(j) = dist_prof_temp(j);
615 dist_prof_rev0 = dist_prof(0);
616 dist_prof = dist_prof_rev;
618 int d = dfree + no_terms - 1;
619 int max_stack_size = 50000;
620 ivec S_stack(max_stack_size), W_stack(max_stack_size), b_stack(max_stack_size);
621 ivec c_stack(max_stack_size), t_stack(max_stack_size);
627 spectrum(0).set_size(dfree + no_terms, 0);
628 spectrum(1).set_size(dfree + no_terms, 0);
631 int S, S0, S1, W0, W1, w0, w1, c = 0;
633 int W = d - dist_prof_rev0;
657 if ((d - W0) < d_best_so_far) {
return -1; }
660 if ((W1 < dist_prof(
m - 1)) || (W < dist_prof(
m)))
goto F5;
662 if (test_catastrophic && (W == W1)) {
664 if (c > cat_treshold)
679 if (stack_pos == -1)
goto end;
681 S = S_stack(stack_pos);
682 W = W_stack(stack_pos);
683 b = b_stack(stack_pos);
684 c = c_stack(stack_pos);
685 t = t_stack(stack_pos);
691 if (W0 < dist_prof(
m - mf - 1))
goto F4;
694 if ((W1 >= dist_prof(
m - 1)) && (W >= dist_prof(
m))) {
696 if (test_catastrophic && (stack_pos > 40000))
700 if (stack_pos >= max_stack_size) {
701 max_stack_size = 2 * max_stack_size;
702 S_stack.set_size(max_stack_size,
true);
703 W_stack.set_size(max_stack_size,
true);
704 b_stack.set_size(max_stack_size,
true);
705 c_stack.set_size(max_stack_size,
true);
706 t_stack.set_size(max_stack_size,
true);
708 S_stack(stack_pos) = S1;
709 W_stack(stack_pos) = W1;
710 b_stack(stack_pos) = b + 1;
711 c_stack(stack_pos) = c;
712 t_stack(stack_pos) = t + 1;
717 if (test_catastrophic && (W == W0)) {
719 if (c > cat_treshold)
738 spectrum(0).set_size(dmax + no_terms,
false);
739 spectrum(1).set_size(dmax + no_terms,
false);
743 for (
int pos = 0; pos <
Period; pos++) {
752 imat Ad_states(1 << (
K - 1), dmax + no_terms), Cd_states(1 <<
m, dmax + no_terms);
753 imat Ad_temp(1 << (
K - 1), dmax + no_terms), Cd_temp(1 <<
m, dmax + no_terms);
754 ivec mindist(1 << (
K - 1)), mindist_temp(1 <<
m);
757 spectrum(0).set_size(dmax + no_terms,
false);
758 spectrum(1).set_size(dmax + no_terms,
false);
764 int wmax = dmax + no_terms;
765 ivec visited_states(1 <<
m), visited_states_temp(1 <<
m);
766 bool proceede, expand_s1;
767 int t, d, w0, w1, s, s0, s1 = 0, s_start;
770 visited_states.zeros();
773 visited_states(s1) = 1;
775 Ad_states(s1, w1) = 1;
776 Cd_states(s1, w1) = 1;
779 if (block_length > 0) {
781 visited_states(s0) = 1;
783 Ad_states(s0, w0) = 1;
784 Cd_states(s0, w0) = 0;
798 mindist_temp.zeros();
799 visited_states_temp.zeros();
801 for (s = s_start; s < (1 <<
m); s++) {
803 if (visited_states(s) == 1) {
804 if ((mindist(s) >= 0) && (mindist(s) < wmax)) {
809 for (d = mindist(s); d < (wmax - w0); d++) {
810 Ad_temp(s0, d + w0) += Ad_states(s, d);
811 Cd_temp(s0, d + w0) += Cd_states(s, d);
813 if (visited_states_temp(s0) == 0) { mindist_temp(s0) = mindist(s) + w0; }
814 else { mindist_temp(s0) = ((mindist(s) + w0) < mindist_temp(s0)) ? mindist(s) + w0 : mindist_temp(s0); }
815 visited_states_temp(s0) = 1;
818 if ((block_length == 0) || (t < (block_length - (
K - 1)))) {
824 for (d = mindist(s); d < (wmax - w1); d++) {
825 Ad_temp(s1, d + w1) += Ad_states(s, d);
826 Cd_temp(s1, d + w1) += Cd_states(s, d) + Ad_states(s, d);
828 if (visited_states_temp(s1) == 0) { mindist_temp(s1) = mindist(s) + w1; }
829 else { mindist_temp(s1) = ((mindist(s) + w1) < mindist_temp(s1)) ? mindist(s) + w1 : mindist_temp(s1); }
830 visited_states_temp(s1) = 1;
838 if (block_length == 0) {
842 visited_states = visited_states_temp;
843 mindist =
elem_mult(mindist_temp, visited_states);
845 if ((t > block_length) && (block_length > 0)) { proceede =
false; }
848 if (block_length > 0) {
#define it_error_if(t, s)
Abort if t is true.
void encode_tail(const bvec &input, bvec &output)
Encoding that begins and ends in the zero state.
void decode_trunc(const vec &received_signal, bvec &output)
Viterbi decoding using truncation of memory (default = 5*K)
Vec< T > reverse(const Vec< T > &in)
Reverse the input vector.
virtual void decode(const vec &received_signal, bvec &output)
Viterbi decoding using specified method.
Mat< Num_T > elem_mult(const Mat< Num_T > &m1, const Mat< Num_T > &m2)
Element wise multiplication of two matrices.
int total
The number of "1" in the puncture matrix.
bvec xor_int_table
Auxilary table used by the codec.
int next_state(const int instate, const int input)
Next state from instate given the input.
void calculate_spectrum(Array< ivec > &spectrum, int dmax, int no_terms)
Calculate spectrum.
int weight_reverse(const int state, const int input, int time)
Weight of the reverse code from state with input (0 or 1) at transition time.
int fast(Array< ivec > &spectrum, int time, int dfree, int no_terms, int d_best_so_far=0, bool test_catastrophic=false)
Cederwall's fast algorithm.
virtual void decode_tailbite(const vec &received_signal, bvec &output)
Decode a block of encoded data where encode_tailbite has been used.
void encode_trunc(const bvec &input, bvec &output)
Encode a binary vector starting from the previous encoder state.
void encode(const bvec &input, bvec &output)
Encode a binary vector of inputs using specified method.
int m
Memory of the encoder.
bmat puncture_matrix
The puncture matrix (n rows and Period columns)
void encode_tailbite(const bvec &input, bvec &output)
Encode an input binary vector using tailbiting.
ivec gen_pol_rev
Generator polynomials for the reverse code.
void encode_trunc(const bvec &input, bvec &output)
Encode a binary vector of inputs starting from state set by the set_state function.
vec spectrum(const vec &v, int nfft, int noverlap)
Power spectrum calculation.
void decode_tailbite(const vec &received_signal, bvec &output)
Decode a block of encoded data where encode_tailbite has been used. Tries all start states...
int Period
The puncture period (i.e. the number of columns in the puncture matrix)
void decode_tail(const vec &received_signal, bvec &output)
Decode a block of encoded data where encode_tail has been used.
virtual void decode_trunc(const vec &received_signal, bvec &output)
Viterbi decoding using truncation of memory (default = 5*K)
void set_puncture_matrix(const bmat &pmatrix)
Set puncture matrix (size n*Period)
#define it_warning(s)
Display a warning message.
double rate
The rate of the code.
int n
Number of generators.
void distance_profile(ivec &dist_prof, int time, int dmax=100000, bool reverse=false)
Calculate distance profile. If reverse = true calculate for the reverse code instead.
int weight(const int state, const int input, int time)
The weight of path from state with input (0 or 1) at transition time.
Binary arithmetic (boolean) class.
#define it_error(s)
Abort unconditionally.
bool catastrophic(void)
Check if the code is catastrophic. Returns true if catastrophic.
CONVOLUTIONAL_CODE_METHOD cc_method
encoding and decoding method
void encode_tailbite(const bvec &input, bvec &output)
Encode a binary vector of inputs using tailbiting.
void encode_tail(const bvec &input, bvec &output)
Encoding that starts and ends in the zero state.
ivec gen_pol
Generator polynomials.
virtual void decode_tail(const vec &received_signal, bvec &output)
Decode a block of encoded data where encode_tail has been used.
Definitions of a Binary Punctured Convolutional Encoder class.
Mat< bin > bmat
bin matrix