44 int i, j, temp, out, w = 0, shiftreg = state;
46 shiftreg = shiftreg | (input <<
m);
47 for (j = 0; j <
n; j++) {
50 for (i = 0; i <
K; i++) {
66 int i, j, temp, out, w = 0, shiftreg = state;
68 shiftreg = shiftreg | (input <<
m);
69 for (j = 0; j <
n; j++) {
72 for (i = 0; i <
K; i++) {
87 int i, j, temp, out, shiftreg = state;
91 shiftreg = shiftreg | (1 <<
m);
92 for (j = 0; j <
n; j++) {
96 for (i = 0; i <
m; i++) {
101 w1 += out ^(temp & 1);
111 int i, j, temp, out, shiftreg = state;
115 shiftreg = shiftreg | (1 <<
m);
116 for (j = 0; j <
n; j++) {
120 for (i = 0; i <
m; i++) {
125 w1 += out ^(temp & 1);
134 int j, temp, temp_state;
138 temp_state = (state << 1) | input;
139 for (j = 0; j <
n; j++) {
140 temp = temp_state &
gen_pol(j);
153 int j, temp, temp_state;
156 temp_state = (state << 1) | 1;
157 for (j = 0; j <
n; j++) {
158 temp = temp_state &
gen_pol(j);
172 int j, temp, temp_state;
175 zero_output = 0, one_output = 0;
176 temp_state = (state << 1) | 1;
177 for (j = 0; j <
n; j++) {
178 temp = temp_state &
gen_pol(j);
182 one_output = (one_output << 1) |
int(
xor_int_table(temp) ^ one_bit);
191 const vec &rx_codeword,
197 one_metric = zero_metric = 0;
199 int temp_state = (state << 1) | 1;
200 for (
int j = 0; j <
n; j++) {
201 temp = temp_state &
gen_pol(j);
204 one_metric += (2 *
static_cast<int>(
xor_int_table(temp) ^ one_bit) - 1)
206 zero_metric += (2 *
static_cast<int>(
xor_int_table(temp)) - 1)
216 int no_outputs =
pow2i(
n), no_loop =
pow2i(
n - 1), mask = no_outputs - 1,
218 delta_metrics.set_size(no_outputs,
false);
221 for (
int i = 0; i < no_loop; i++) {
222 delta_metrics(i) = 0;
224 for (
int j =
n - 1; j >= 0; j--) {
226 delta_metrics(i) += rx_codeword(j);
228 delta_metrics(i) -= rx_codeword(j);
231 delta_metrics(i ^ mask) = -delta_metrics(i);
235 double zero_metric, one_metric;
236 int zero_output, one_output, temp_state;
239 zero_metric = 0, one_metric = 0;
240 zero_output = 0, one_output = 0;
241 temp_state = (s << 1) | 1;
242 for (
int j = 0; j <
n; j++) {
243 temp = temp_state &
gen_pol(j);
247 zero_metric += rx_codeword(j);
248 one_metric -= rx_codeword(j);
251 zero_metric -= rx_codeword(j);
252 one_metric += rx_codeword(j);
254 one_output = (one_output << 1)
256 zero_output = (zero_output << 1)
259 delta_metrics(zero_output) = zero_metric;
260 delta_metrics(one_output) = one_metric;
268 int Conv_Code_MFD_2[15][2] = {
287 int Conv_Code_MFD_3[15][3] = {
298 {0117, 01365, 01633},
299 {02353, 02671, 03175},
300 {04767, 05723, 06265},
301 {010533, 010675, 017661},
302 {021645, 035661, 037133},
306 int Conv_Code_MFD_4[15][4] = {
311 {013, 015, 015, 017},
312 {025, 027, 033, 037},
313 {053, 067, 071, 075},
314 {0135, 0135, 0147, 0163},
315 {0235, 0275, 0313, 0357},
316 {0463, 0535, 0733, 0745},
317 {0117, 01365, 01633, 01653},
318 {02327, 02353, 02671, 03175},
319 {04767, 05723, 06265, 07455},
320 {011145, 012477, 015573, 016727},
321 {021113, 023175, 035527, 035537},
326 int Conv_Code_MFD_5[9][5] = {
330 {07, 07, 07, 05, 05},
331 {017, 017, 013, 015, 015},
332 {037, 027, 033, 025, 035},
333 {075, 071, 073, 065, 057},
334 {0175, 0131, 0135, 0135, 0147},
335 {0257, 0233, 0323, 0271, 0357},
339 int Conv_Code_MFD_6[9][6] = {
343 {07, 07, 07, 07, 05, 05},
344 {017, 017, 013, 013, 015, 015},
345 {037, 035, 027, 033, 025, 035},
346 {073, 075, 055, 065, 047, 057},
347 {0173, 0151, 0135, 0135, 0163, 0137},
348 {0253, 0375, 0331, 0235, 0313, 0357},
352 int Conv_Code_MFD_7[9][7] = {
353 {0, 0, 0, 0, 0, 0, 0},
354 {0, 0, 0, 0, 0, 0, 0},
355 {0, 0, 0, 0, 0, 0, 0},
356 {07, 07, 07, 07, 05, 05, 05},
357 {017, 017, 013, 013, 013, 015, 015},
358 {035, 027, 025, 027, 033, 035, 037},
359 {053, 075, 065, 075, 047, 067, 057},
360 {0165, 0145, 0173, 0135, 0135, 0147, 0137},
361 {0275, 0253, 0375, 0331, 0235, 0313, 0357},
365 int Conv_Code_MFD_8[9][8] = {
366 {0, 0, 0, 0, 0, 0, 0, 0},
367 {0, 0, 0, 0, 0, 0, 0, 0},
368 {0, 0, 0, 0, 0, 0, 0, 0},
369 {07, 07, 05, 05, 05, 07, 07, 07},
370 {017, 017, 013, 013, 013, 015, 015, 017},
371 {037, 033, 025, 025, 035, 033, 027, 037},
372 {057, 073, 051, 065, 075, 047, 067, 057},
373 {0153, 0111, 0165, 0173, 0135, 0135, 0147, 0137},
374 {0275, 0275, 0253, 0371, 0331, 0235, 0313, 0357},
377 int maxK_Conv_Code_MFD[9] = {0, 0, 14, 14, 14, 8, 8, 8, 8};
379 void get_MFD_gen_pol(
int n,
int K, ivec & gen)
385 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[2],
"This convolutional code doesn't exist in the tables");
386 gen(0) = Conv_Code_MFD_2[K][0];
387 gen(1) = Conv_Code_MFD_2[K][1];
390 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[3],
"This convolutional code doesn't exist in the tables");
391 gen(0) = Conv_Code_MFD_3[K][0];
392 gen(1) = Conv_Code_MFD_3[K][1];
393 gen(2) = Conv_Code_MFD_3[K][2];
396 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[4],
"This convolutional code doesn't exist in the tables");
397 gen(0) = Conv_Code_MFD_4[K][0];
398 gen(1) = Conv_Code_MFD_4[K][1];
399 gen(2) = Conv_Code_MFD_4[K][2];
400 gen(3) = Conv_Code_MFD_4[K][3];
403 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[5],
"This convolutional code doesn't exist in the tables");
404 gen(0) = Conv_Code_MFD_5[K][0];
405 gen(1) = Conv_Code_MFD_5[K][1];
406 gen(2) = Conv_Code_MFD_5[K][2];
407 gen(3) = Conv_Code_MFD_5[K][3];
408 gen(4) = Conv_Code_MFD_5[K][4];
411 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[6],
"This convolutional code doesn't exist in the tables");
412 gen(0) = Conv_Code_MFD_6[K][0];
413 gen(1) = Conv_Code_MFD_6[K][1];
414 gen(2) = Conv_Code_MFD_6[K][2];
415 gen(3) = Conv_Code_MFD_6[K][3];
416 gen(4) = Conv_Code_MFD_6[K][4];
417 gen(5) = Conv_Code_MFD_6[K][5];
420 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[7],
"This convolutional code doesn't exist in the tables");
421 gen(0) = Conv_Code_MFD_7[K][0];
422 gen(1) = Conv_Code_MFD_7[K][1];
423 gen(2) = Conv_Code_MFD_7[K][2];
424 gen(3) = Conv_Code_MFD_7[K][3];
425 gen(4) = Conv_Code_MFD_7[K][4];
426 gen(5) = Conv_Code_MFD_7[K][5];
427 gen(6) = Conv_Code_MFD_7[K][6];
430 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[8],
"This convolutional code doesn't exist in the tables");
431 gen(0) = Conv_Code_MFD_8[K][0];
432 gen(1) = Conv_Code_MFD_8[K][1];
433 gen(2) = Conv_Code_MFD_8[K][2];
434 gen(3) = Conv_Code_MFD_8[K][3];
435 gen(4) = Conv_Code_MFD_8[K][4];
436 gen(5) = Conv_Code_MFD_8[K][5];
437 gen(6) = Conv_Code_MFD_8[K][6];
438 gen(7) = Conv_Code_MFD_8[K][7];
441 it_assert(
false,
"This convolutional code doesn't exist in the tables");
446 int Conv_Code_ODS_2[17][2] = {
467 int Conv_Code_ODS_3[14][3] = {
478 {01233, 01375, 01671},
479 {02335, 02531, 03477},
480 {05745, 06471, 07553},
481 {013261, 015167, 017451},
485 int Conv_Code_ODS_4[12][4] = {
490 {013, 015, 015, 017},
491 {025, 027, 033, 037},
492 {051, 055, 067, 077},
493 {0117, 0127, 0155, 0171},
494 {0231, 0273, 0327, 0375},
495 {0473, 0513, 0671, 0765},
496 {01173, 01325, 01467, 01751},
497 {02565, 02747, 03311, 03723},
500 int maxK_Conv_Code_ODS[5] = {0, 0, 16, 13, 11};
502 void get_ODS_gen_pol(
int n,
int K, ivec & gen)
508 it_assert(K >= 3 && K <= maxK_Conv_Code_ODS[2],
"This convolutional code doesn't exist in the tables");
509 gen(0) = Conv_Code_ODS_2[K][0];
510 gen(1) = Conv_Code_ODS_2[K][1];
513 it_assert(K >= 3 && K <= maxK_Conv_Code_ODS[3],
"This convolutional code doesn't exist in the tables");
514 gen(0) = Conv_Code_ODS_3[K][0];
515 gen(1) = Conv_Code_ODS_3[K][1];
516 gen(2) = Conv_Code_ODS_3[K][2];
519 it_assert(K >= 3 && K <= maxK_Conv_Code_ODS[4],
"This convolutional code doesn't exist in the tables");
520 gen(0) = Conv_Code_ODS_4[K][0];
521 gen(1) = Conv_Code_ODS_4[K][1];
522 gen(2) = Conv_Code_ODS_4[K][2];
523 gen(3) = Conv_Code_ODS_4[K][3];
526 it_assert(
false,
"This convolutional code doesn't exist in the tables");
535 int inverse_rate,
int constraint_length)
539 if (type_of_code == MFD)
540 get_MFD_gen_pol(inverse_rate, constraint_length, gen);
541 else if (type_of_code == ODS)
542 get_ODS_gen_pol(inverse_rate, constraint_length, gen);
544 it_assert(
false,
"This convolutional code doesn't exist in the tables");
553 int constraint_length)
555 it_error_if(constraint_length <= 0,
"Convolutional_Code::set_generator_polynomials(): Constraint length out of range");
558 it_error_if(n <= 0,
"Convolutional_Code::set_generator_polynomials(): Invalid code rate");
561 if (constraint_length != K) {
562 K = constraint_length;
564 for (
int i = 0; i <
pow2i(K); i++) {
575 for (
int i = 0; i <
n; i++) {
579 int zero_output, one_output;
642 output.set_size(input.size() *
n,
false);
644 for (
int i = 0; i < input.size(); i++) {
646 for (
int j = 0; j <
n; j++) {
662 output.set_size((input.size() +
m) * n,
false);
667 for (
int i = 0; i < input.size(); i++) {
669 for (
int j = 0; j <
n; j++) {
677 for (
int i = input.size(); i < input.size() +
m; i++) {
678 for (
int j = 0; j <
n; j++) {
692 output.set_size(input.size() *
n,
false);
696 bvec last_bits = input.right(
m);
697 for (
int i = 0; i <
m; i++) {
702 for (
int i = 0; i < input.size(); i++) {
704 for (
int j = 0; j <
n; j++) {
719 output.set_size(n,
false);
722 for (
int j = 0; j <
n; j++) {
734 it_error(
"Convolutional_Code::decode(): Hard-decision decoding not implemented");
739 it_error(
"Convolutional_Code::decode(): Hard-decision decoding not implemented");
770 int block_length = received_signal.size() /
n;
772 "Convolutional_Code::decode_tail(): Input sequence to short");
774 vec temp_sum_metric(
no_states), temp_rec(n), delta_metrics;
776 double temp_metric_zero, temp_metric_one;
779 output.set_size(block_length -
m,
false);
790 for (
int l = 0; l <
m; l++) {
791 temp_rec = received_signal.mid(l * n, n);
802 temp_visited_state(s) =
true;
810 temp_visited_state(s) =
true;
815 if (temp_metric_zero < temp_metric_one) {
816 temp_sum_metric(s) = temp_metric_zero;
820 temp_sum_metric(s) = temp_metric_one;
829 for (
int l = m; l < block_length; l++) {
830 temp_rec = received_signal.
mid(l * n, n);
842 if (temp_metric_zero < temp_metric_one) {
843 temp_sum_metric(s) = temp_metric_zero;
847 temp_sum_metric(s) = temp_metric_one;
855 int min_metric_state = 0;
857 for (
int l = block_length - 1; l > block_length - 1 -
m; l--) {
864 for (
int l = block_length - 1 - m; l >= 0; l--) {
879 int block_length = received_signal.size() /
n;
881 "Convolutional_Code::decode_tailbite(): Input sequence to short");
883 vec temp_sum_metric(
no_states), temp_rec(n), delta_metrics;
885 double temp_metric_zero, temp_metric_one;
887 bvec best_output(block_length), temp_output(block_length);
890 output.set_size(block_length,
false);
903 for (
int l = 0; l < block_length; l++) {
904 temp_rec = received_signal.mid(l * n, n);
914 temp_visited_state(s) =
true;
922 temp_visited_state(s) =
true;
927 if (temp_metric_zero < temp_metric_one) {
928 temp_sum_metric(s) = temp_metric_zero;
932 temp_sum_metric(s) = temp_metric_one;
941 int min_metric_state = ss;
944 for (
int l = block_length - 1; l >= 0; l--) {
945 temp_output(l) =
get_input(min_metric_state);
952 best_output = temp_output;
955 output = best_output;
965 int block_length = received_signal.size() /
n;
967 "Convolutional_Code::decode_trunc(): Input sequence to short");
969 vec temp_sum_metric(
no_states), temp_rec(n), delta_metrics;
971 double temp_metric_zero, temp_metric_one;
979 for (
int i = 0; i < block_length; i++) {
983 temp_rec = received_signal.mid(i * n, n);
993 temp_visited_state(s) =
true;
1001 temp_visited_state(s) =
true;
1006 if (temp_metric_zero < temp_metric_one) {
1007 temp_sum_metric(s) = temp_metric_zero;
1011 temp_sum_metric(s) = temp_metric_one;
1034 output.ins(output.size(),
get_input(min_metric_state));
1052 int state = 0, zero_state, one_state, zero_temp, one_temp, i, j;
1053 bvec zero_output(n), one_output(n);
1055 int block_length = coded_sequence.size() / n -
m;
1056 it_error_if(block_length <= 0,
"The input sequence is to short");
1057 input.set_length(block_length,
false);
1060 for (i = 0; i < block_length; i++) {
1062 one_state = state | (1 <<
m);
1063 for (j = 0; j <
n; j++) {
1064 zero_temp = zero_state &
gen_pol(j);
1065 one_temp = one_state &
gen_pol(j);
1069 if (coded_sequence.mid(i*n, n) == zero_output) {
1071 state = zero_state >> 1;
1073 else if (coded_sequence.mid(i*n, n) == one_output) {
1075 state = one_state >> 1;
1089 int start, S, W0, W1, S0, S1;
1090 bvec visited(1 <<
m);
1092 for (start = 1; start <
no_states; start++) {
1101 if (S1 < start)
goto node0;
1102 if (W1 > 0)
goto node0;
1104 if (visited(S1) ==
bin(1))
1111 if (S0 < start)
continue;
1112 if (W0 > 0)
continue;
1114 if (visited(S0) ==
bin(1))
1132 int max_stack_size = 50000;
1133 ivec S_stack(max_stack_size), W_stack(max_stack_size), t_stack(max_stack_size);
1135 int stack_pos = -1, t, S, W, W0, w0, w1;
1137 dist_prof.set_size(K,
false);
1157 if (W0 < dist_prof(
m)) {
1159 if (stack_pos >= max_stack_size) {
1160 max_stack_size = 2 * max_stack_size;
1161 S_stack.set_size(max_stack_size,
true);
1162 W_stack.set_size(max_stack_size,
true);
1163 t_stack.set_size(max_stack_size,
true);
1167 W_stack(stack_pos) = W0;
1168 t_stack(stack_pos) = t + 1;
1174 if (W > dist_prof(
m))
1180 if (W < dist_prof(t))
1183 if (t ==
m)
goto stack;
1188 if (stack_pos >= 0) {
1190 S = S_stack(stack_pos);
1191 W = W_stack(stack_pos);
1192 t = t_stack(stack_pos);
1195 if (W < dist_prof(t))
1198 if (t ==
m)
goto stack;
1218 ivec mindist(
no_states), mindist_temp(1 <<
m);
1221 spectrum(0).set_size(dmax + no_terms,
false);
1222 spectrum(1).set_size(dmax + no_terms,
false);
1228 int wmax = dmax + no_terms;
1231 int d, w0, w1, s, s0, s1;
1233 visited_states.zeros();
1235 visited_states(s) = 1;
1237 Ad_states(s, w1) = 1;
1238 Cd_states(s, w1) = 1;
1246 mindist_temp.zeros();
1247 visited_states_temp.zeros();
1249 if ((mindist(s) > 0) && (mindist(s) < wmax)) {
1253 for (d = mindist(s); d < (wmax - w0); d++) {
1254 Ad_temp(s0, d + w0) += Ad_states(s, d);
1255 Cd_temp(s0, d + w0) += Cd_states(s, d);
1256 visited_states_temp(s0) = 1;
1260 for (d = mindist(s); d < (wmax - w1); d++) {
1261 Ad_temp(s1, d + w1) += Ad_states(s, d);
1262 Cd_temp(s1, d + w1) += Cd_states(s, d) + Ad_states(s, d);
1263 visited_states_temp(s1) = 1;
1265 if (mindist_temp(s0) > 0) { mindist_temp(s0) = (mindist(s) + w0) < mindist_temp(s0) ? mindist(s) + w0 : mindist_temp(s0); }
1266 else { mindist_temp(s0) = mindist(s) + w0; }
1267 if (mindist_temp(s1) > 0) { mindist_temp(s1) = (mindist(s) + w1) < mindist_temp(s1) ? mindist(s) + w1 : mindist_temp(s1); }
1268 else { mindist_temp(s1) = mindist(s) + w1; }
1272 Ad_states = Ad_temp;
1273 Cd_states = Cd_temp;
1276 visited_states = visited_states_temp;
1277 mindist =
elem_mult(mindist_temp, visited_states);
1298 int cat_treshold = 7 *
K;
1300 ivec dist_prof(K), dist_prof_rev(K);
1304 int dist_prof_rev0 = dist_prof_rev(0);
1309 for (i = 0; i <
K; i++) {
1310 if (dist_prof_rev(i) > dist_prof(i)) {
1312 dist_prof_rev0 = dist_prof(0);
1313 dist_prof = dist_prof_rev;
1316 else if (dist_prof_rev(i) < dist_prof(i)) {
1321 int d = dfree + no_terms - 1;
1322 int max_stack_size = 50000;
1323 ivec S_stack(max_stack_size), W_stack(max_stack_size), b_stack(max_stack_size), c_stack(max_stack_size);
1329 spectrum(0).set_size(dfree + no_terms,
false);
1330 spectrum(1).set_size(dfree + no_terms,
false);
1333 int S, S0, S1, W0, W1, w0, w1, c = 0;
1335 int W = d - dist_prof_rev0;
1350 if (mf <
m)
goto F6;
1357 if (((d - W0) < dfree) || (((d - W0) == dfree) && (
spectrum(1)(d - W0) > Cdfree)))
1363 if ((W1 < dist_prof(
m - 1)) || (W < dist_prof(
m)))
goto F5;
1365 if (test_catastrophic && W == W1) {
1367 if (c > cat_treshold)
1382 if (stack_pos == -1)
goto end;
1384 S = S_stack(stack_pos);
1385 W = W_stack(stack_pos);
1386 b = b_stack(stack_pos);
1387 c = c_stack(stack_pos);
1393 if (W0 < dist_prof(
m - mf - 1))
goto F4;
1396 if ((W1 >= dist_prof(
m - 1)) && (W >= dist_prof(
m))) {
1398 if (test_catastrophic && stack_pos > 10000)
1402 if (stack_pos >= max_stack_size) {
1403 max_stack_size = 2 * max_stack_size;
1404 S_stack.set_size(max_stack_size,
true);
1405 W_stack.set_size(max_stack_size,
true);
1406 b_stack.set_size(max_stack_size,
true);
1407 c_stack.set_size(max_stack_size,
true);
1409 S_stack(stack_pos) = S1;
1410 W_stack(stack_pos) = W1;
1411 b_stack(stack_pos) = b + 1;
1412 c_stack(stack_pos) = c;
1416 if (test_catastrophic && W == W0) {
1418 if (c > cat_treshold)
1443 for (i = 0; i < (length >> 1); i++) {
1444 out = out | ((in & (1 << i)) << (length - 1 - (i << 1)));
1446 for (j = 0; j < (length - i); j++) {
1447 out = out | ((in & (1 << (j + i))) >> ((j << 1) - (length & 1) + 1));
1460 for (i = 0; i <
length; i++) {
1461 w += (in & (1 << i)) >> i;
1471 it_assert_debug(v1.size() == v2.size(),
"compare_spectra: wrong sizes");
1473 for (
int i = 0; i < v1.size(); i++) {
1474 if (v1(i) < v2(i)) {
1477 else if (v1(i) > v2(i)) {
1491 double t1 = 0, t2 = 0;
1492 for (
int i = 0; i < v1.size(); i++) {
1493 t1 += (double)v1(i) * weight_profile(i);
1494 t2 += (double)v2(i) * weight_profile(i);
1496 if (t1 < t2)
return 1;
1497 else if (t1 > t2)
return 0;