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);
250 zero_metric -= rx_codeword(j);
253 one_metric += rx_codeword(j);
255 one_metric -= rx_codeword(j);
257 one_output = (one_output << 1)
259 zero_output = (zero_output << 1)
262 delta_metrics(zero_output) = zero_metric;
263 delta_metrics(one_output) = one_metric;
271 int Conv_Code_MFD_2[15][2] = {
290 int Conv_Code_MFD_3[15][3] = {
301 {0117, 01365, 01633},
302 {02353, 02671, 03175},
303 {04767, 05723, 06265},
304 {010533, 010675, 017661},
305 {021645, 035661, 037133},
309 int Conv_Code_MFD_4[15][4] = {
314 {013, 015, 015, 017},
315 {025, 027, 033, 037},
316 {053, 067, 071, 075},
317 {0135, 0135, 0147, 0163},
318 {0235, 0275, 0313, 0357},
319 {0463, 0535, 0733, 0745},
320 {0117, 01365, 01633, 01653},
321 {02327, 02353, 02671, 03175},
322 {04767, 05723, 06265, 07455},
323 {011145, 012477, 015573, 016727},
324 {021113, 023175, 035527, 035537},
329 int Conv_Code_MFD_5[9][5] = {
333 {07, 07, 07, 05, 05},
334 {017, 017, 013, 015, 015},
335 {037, 027, 033, 025, 035},
336 {075, 071, 073, 065, 057},
337 {0175, 0131, 0135, 0135, 0147},
338 {0257, 0233, 0323, 0271, 0357},
342 int Conv_Code_MFD_6[9][6] = {
346 {07, 07, 07, 07, 05, 05},
347 {017, 017, 013, 013, 015, 015},
348 {037, 035, 027, 033, 025, 035},
349 {073, 075, 055, 065, 047, 057},
350 {0173, 0151, 0135, 0135, 0163, 0137},
351 {0253, 0375, 0331, 0235, 0313, 0357},
355 int Conv_Code_MFD_7[9][7] = {
356 {0, 0, 0, 0, 0, 0, 0},
357 {0, 0, 0, 0, 0, 0, 0},
358 {0, 0, 0, 0, 0, 0, 0},
359 {07, 07, 07, 07, 05, 05, 05},
360 {017, 017, 013, 013, 013, 015, 015},
361 {035, 027, 025, 027, 033, 035, 037},
362 {053, 075, 065, 075, 047, 067, 057},
363 {0165, 0145, 0173, 0135, 0135, 0147, 0137},
364 {0275, 0253, 0375, 0331, 0235, 0313, 0357},
368 int Conv_Code_MFD_8[9][8] = {
369 {0, 0, 0, 0, 0, 0, 0, 0},
370 {0, 0, 0, 0, 0, 0, 0, 0},
371 {0, 0, 0, 0, 0, 0, 0, 0},
372 {07, 07, 05, 05, 05, 07, 07, 07},
373 {017, 017, 013, 013, 013, 015, 015, 017},
374 {037, 033, 025, 025, 035, 033, 027, 037},
375 {057, 073, 051, 065, 075, 047, 067, 057},
376 {0153, 0111, 0165, 0173, 0135, 0135, 0147, 0137},
377 {0275, 0275, 0253, 0371, 0331, 0235, 0313, 0357},
380 int maxK_Conv_Code_MFD[9] = {0, 0, 14, 14, 14, 8, 8, 8, 8};
382 void get_MFD_gen_pol(
int n,
int K, ivec & gen)
388 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[2],
"This convolutional code doesn't exist in the tables");
389 gen(0) = Conv_Code_MFD_2[K][0];
390 gen(1) = Conv_Code_MFD_2[K][1];
393 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[3],
"This convolutional code doesn't exist in the tables");
394 gen(0) = Conv_Code_MFD_3[K][0];
395 gen(1) = Conv_Code_MFD_3[K][1];
396 gen(2) = Conv_Code_MFD_3[K][2];
399 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[4],
"This convolutional code doesn't exist in the tables");
400 gen(0) = Conv_Code_MFD_4[K][0];
401 gen(1) = Conv_Code_MFD_4[K][1];
402 gen(2) = Conv_Code_MFD_4[K][2];
403 gen(3) = Conv_Code_MFD_4[K][3];
406 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[5],
"This convolutional code doesn't exist in the tables");
407 gen(0) = Conv_Code_MFD_5[K][0];
408 gen(1) = Conv_Code_MFD_5[K][1];
409 gen(2) = Conv_Code_MFD_5[K][2];
410 gen(3) = Conv_Code_MFD_5[K][3];
411 gen(4) = Conv_Code_MFD_5[K][4];
414 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[6],
"This convolutional code doesn't exist in the tables");
415 gen(0) = Conv_Code_MFD_6[K][0];
416 gen(1) = Conv_Code_MFD_6[K][1];
417 gen(2) = Conv_Code_MFD_6[K][2];
418 gen(3) = Conv_Code_MFD_6[K][3];
419 gen(4) = Conv_Code_MFD_6[K][4];
420 gen(5) = Conv_Code_MFD_6[K][5];
423 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[7],
"This convolutional code doesn't exist in the tables");
424 gen(0) = Conv_Code_MFD_7[K][0];
425 gen(1) = Conv_Code_MFD_7[K][1];
426 gen(2) = Conv_Code_MFD_7[K][2];
427 gen(3) = Conv_Code_MFD_7[K][3];
428 gen(4) = Conv_Code_MFD_7[K][4];
429 gen(5) = Conv_Code_MFD_7[K][5];
430 gen(6) = Conv_Code_MFD_7[K][6];
433 it_assert(K >= 3 && K <= maxK_Conv_Code_MFD[8],
"This convolutional code doesn't exist in the tables");
434 gen(0) = Conv_Code_MFD_8[K][0];
435 gen(1) = Conv_Code_MFD_8[K][1];
436 gen(2) = Conv_Code_MFD_8[K][2];
437 gen(3) = Conv_Code_MFD_8[K][3];
438 gen(4) = Conv_Code_MFD_8[K][4];
439 gen(5) = Conv_Code_MFD_8[K][5];
440 gen(6) = Conv_Code_MFD_8[K][6];
441 gen(7) = Conv_Code_MFD_8[K][7];
444 it_assert(
false,
"This convolutional code doesn't exist in the tables");
449 int Conv_Code_ODS_2[17][2] = {
470 int Conv_Code_ODS_3[14][3] = {
481 {01233, 01375, 01671},
482 {02335, 02531, 03477},
483 {05745, 06471, 07553},
484 {013261, 015167, 017451},
488 int Conv_Code_ODS_4[12][4] = {
493 {013, 015, 015, 017},
494 {025, 027, 033, 037},
495 {051, 055, 067, 077},
496 {0117, 0127, 0155, 0171},
497 {0231, 0273, 0327, 0375},
498 {0473, 0513, 0671, 0765},
499 {01173, 01325, 01467, 01751},
500 {02565, 02747, 03311, 03723},
503 int maxK_Conv_Code_ODS[5] = {0, 0, 16, 13, 11};
505 void get_ODS_gen_pol(
int n,
int K, ivec & gen)
511 it_assert(K >= 3 && K <= maxK_Conv_Code_ODS[2],
"This convolutional code doesn't exist in the tables");
512 gen(0) = Conv_Code_ODS_2[K][0];
513 gen(1) = Conv_Code_ODS_2[K][1];
516 it_assert(K >= 3 && K <= maxK_Conv_Code_ODS[3],
"This convolutional code doesn't exist in the tables");
517 gen(0) = Conv_Code_ODS_3[K][0];
518 gen(1) = Conv_Code_ODS_3[K][1];
519 gen(2) = Conv_Code_ODS_3[K][2];
522 it_assert(K >= 3 && K <= maxK_Conv_Code_ODS[4],
"This convolutional code doesn't exist in the tables");
523 gen(0) = Conv_Code_ODS_4[K][0];
524 gen(1) = Conv_Code_ODS_4[K][1];
525 gen(2) = Conv_Code_ODS_4[K][2];
526 gen(3) = Conv_Code_ODS_4[K][3];
529 it_assert(
false,
"This convolutional code doesn't exist in the tables");
538 int inverse_rate,
int constraint_length)
542 if (type_of_code == MFD)
543 get_MFD_gen_pol(inverse_rate, constraint_length, gen);
544 else if (type_of_code == ODS)
545 get_ODS_gen_pol(inverse_rate, constraint_length, gen);
547 it_assert(
false,
"This convolutional code doesn't exist in the tables");
556 int constraint_length)
558 it_error_if(constraint_length <= 0,
"Convolutional_Code::set_generator_polynomials(): Constraint length out of range");
561 it_error_if(n <= 0,
"Convolutional_Code::set_generator_polynomials(): Invalid code rate");
564 if (constraint_length != K) {
565 K = constraint_length;
567 for (
int i = 0; i <
pow2i(K); i++) {
578 for (
int i = 0; i <
n; i++) {
582 int zero_output, one_output;
645 output.set_size(input.size() *
n,
false);
647 for (
int i = 0; i < input.size(); i++) {
649 for (
int j = 0; j <
n; j++) {
665 output.set_size((input.size() +
m) * n,
false);
670 for (
int i = 0; i < input.size(); i++) {
672 for (
int j = 0; j <
n; j++) {
680 for (
int i = input.size(); i < input.size() +
m; i++) {
681 for (
int j = 0; j <
n; j++) {
695 output.set_size(input.size() *
n,
false);
699 bvec last_bits = input.right(
m);
700 for (
int i = 0; i <
m; i++) {
705 for (
int i = 0; i < input.size(); i++) {
707 for (
int j = 0; j <
n; j++) {
722 output.set_size(n,
false);
725 for (
int j = 0; j <
n; j++) {
737 it_error(
"Convolutional_Code::decode(): Hard-decision decoding not implemented");
742 it_error(
"Convolutional_Code::decode(): Hard-decision decoding not implemented");
773 int block_length = received_signal.size() /
n;
775 "Convolutional_Code::decode_tail(): Input sequence to short");
777 vec temp_sum_metric(
no_states), temp_rec(n), delta_metrics;
779 double temp_metric_zero, temp_metric_one;
782 output.set_size(block_length -
m,
false);
793 for (
int l = 0; l <
m; l++) {
794 temp_rec = received_signal.mid(l * n, n);
805 temp_visited_state(s) =
true;
813 temp_visited_state(s) =
true;
818 if (temp_metric_zero < temp_metric_one) {
819 temp_sum_metric(s) = temp_metric_zero;
823 temp_sum_metric(s) = temp_metric_one;
832 for (
int l = m; l < block_length; l++) {
833 temp_rec = received_signal.
mid(l * n, n);
845 if (temp_metric_zero < temp_metric_one) {
846 temp_sum_metric(s) = temp_metric_zero;
850 temp_sum_metric(s) = temp_metric_one;
858 int min_metric_state = 0;
860 for (
int l = block_length - 1; l > block_length - 1 -
m; l--) {
867 for (
int l = block_length - 1 - m; l >= 0; l--) {
882 int block_length = received_signal.size() /
n;
884 "Convolutional_Code::decode_tailbite(): Input sequence to short");
886 vec temp_sum_metric(
no_states), temp_rec(n), delta_metrics;
888 double temp_metric_zero, temp_metric_one;
890 bvec best_output(block_length), temp_output(block_length);
893 output.set_size(block_length,
false);
906 for (
int l = 0; l < block_length; l++) {
907 temp_rec = received_signal.mid(l * n, n);
917 temp_visited_state(s) =
true;
925 temp_visited_state(s) =
true;
930 if (temp_metric_zero < temp_metric_one) {
931 temp_sum_metric(s) = temp_metric_zero;
935 temp_sum_metric(s) = temp_metric_one;
944 int min_metric_state = ss;
947 for (
int l = block_length - 1; l >= 0; l--) {
948 temp_output(l) =
get_input(min_metric_state);
955 best_output = temp_output;
958 output = best_output;
968 int block_length = received_signal.size() /
n;
970 "Convolutional_Code::decode_trunc(): Input sequence to short");
972 vec temp_sum_metric(
no_states), temp_rec(n), delta_metrics;
974 double temp_metric_zero, temp_metric_one;
982 for (
int i = 0; i < block_length; i++) {
986 temp_rec = received_signal.mid(i * n, n);
996 temp_visited_state(s) =
true;
1004 temp_visited_state(s) =
true;
1009 if (temp_metric_zero < temp_metric_one) {
1010 temp_sum_metric(s) = temp_metric_zero;
1014 temp_sum_metric(s) = temp_metric_one;
1037 output.ins(output.size(),
get_input(min_metric_state));
1055 int state = 0, zero_state, one_state, zero_temp, one_temp, i, j;
1056 bvec zero_output(n), one_output(n);
1058 int block_length = coded_sequence.size() / n -
m;
1059 it_error_if(block_length <= 0,
"The input sequence is to short");
1060 input.set_length(block_length,
false);
1063 for (i = 0; i < block_length; i++) {
1065 one_state = state | (1 <<
m);
1066 for (j = 0; j <
n; j++) {
1067 zero_temp = zero_state &
gen_pol(j);
1068 one_temp = one_state &
gen_pol(j);
1072 if (coded_sequence.mid(i*n, n) == zero_output) {
1074 state = zero_state >> 1;
1076 else if (coded_sequence.mid(i*n, n) == one_output) {
1078 state = one_state >> 1;
1092 int start, S, W0, W1, S0, S1;
1093 bvec visited(1 <<
m);
1095 for (start = 1; start <
no_states; start++) {
1104 if (S1 < start)
goto node0;
1105 if (W1 > 0)
goto node0;
1107 if (visited(S1) ==
bin(1))
1114 if (S0 < start)
continue;
1115 if (W0 > 0)
continue;
1117 if (visited(S0) ==
bin(1))
1135 int max_stack_size = 50000;
1136 ivec S_stack(max_stack_size), W_stack(max_stack_size), t_stack(max_stack_size);
1138 int stack_pos = -1, t, S, W, W0, w0, w1;
1140 dist_prof.set_size(K,
false);
1160 if (W0 < dist_prof(
m)) {
1162 if (stack_pos >= max_stack_size) {
1163 max_stack_size = 2 * max_stack_size;
1164 S_stack.set_size(max_stack_size,
true);
1165 W_stack.set_size(max_stack_size,
true);
1166 t_stack.set_size(max_stack_size,
true);
1170 W_stack(stack_pos) = W0;
1171 t_stack(stack_pos) = t + 1;
1177 if (W > dist_prof(
m))
1183 if (W < dist_prof(t))
1186 if (t ==
m)
goto stack;
1191 if (stack_pos >= 0) {
1193 S = S_stack(stack_pos);
1194 W = W_stack(stack_pos);
1195 t = t_stack(stack_pos);
1198 if (W < dist_prof(t))
1201 if (t ==
m)
goto stack;
1221 ivec mindist(
no_states), mindist_temp(1 <<
m);
1224 spectrum(0).set_size(dmax + no_terms,
false);
1225 spectrum(1).set_size(dmax + no_terms,
false);
1231 int wmax = dmax + no_terms;
1234 int d, w0, w1, s, s0, s1;
1236 visited_states.zeros();
1238 visited_states(s) = 1;
1240 Ad_states(s, w1) = 1;
1241 Cd_states(s, w1) = 1;
1249 mindist_temp.zeros();
1250 visited_states_temp.zeros();
1252 if ((mindist(s) > 0) && (mindist(s) < wmax)) {
1256 for (d = mindist(s); d < (wmax - w0); d++) {
1257 Ad_temp(s0, d + w0) += Ad_states(s, d);
1258 Cd_temp(s0, d + w0) += Cd_states(s, d);
1259 visited_states_temp(s0) = 1;
1263 for (d = mindist(s); d < (wmax - w1); d++) {
1264 Ad_temp(s1, d + w1) += Ad_states(s, d);
1265 Cd_temp(s1, d + w1) += Cd_states(s, d) + Ad_states(s, d);
1266 visited_states_temp(s1) = 1;
1268 if (mindist_temp(s0) > 0) { mindist_temp(s0) = (mindist(s) + w0) < mindist_temp(s0) ? mindist(s) + w0 : mindist_temp(s0); }
1269 else { mindist_temp(s0) = mindist(s) + w0; }
1270 if (mindist_temp(s1) > 0) { mindist_temp(s1) = (mindist(s) + w1) < mindist_temp(s1) ? mindist(s) + w1 : mindist_temp(s1); }
1271 else { mindist_temp(s1) = mindist(s) + w1; }
1275 Ad_states = Ad_temp;
1276 Cd_states = Cd_temp;
1279 visited_states = visited_states_temp;
1280 mindist =
elem_mult(mindist_temp, visited_states);
1301 int cat_treshold = 7 *
K;
1303 ivec dist_prof(K), dist_prof_rev(K);
1307 int dist_prof_rev0 = dist_prof_rev(0);
1312 for (i = 0; i <
K; i++) {
1313 if (dist_prof_rev(i) > dist_prof(i)) {
1315 dist_prof_rev0 = dist_prof(0);
1316 dist_prof = dist_prof_rev;
1319 else if (dist_prof_rev(i) < dist_prof(i)) {
1324 int d = dfree + no_terms - 1;
1325 int max_stack_size = 50000;
1326 ivec S_stack(max_stack_size), W_stack(max_stack_size), b_stack(max_stack_size), c_stack(max_stack_size);
1332 spectrum(0).set_size(dfree + no_terms,
false);
1333 spectrum(1).set_size(dfree + no_terms,
false);
1336 int S, S0, S1, W0, W1, w0, w1, c = 0;
1338 int W = d - dist_prof_rev0;
1353 if (mf <
m)
goto F6;
1360 if (((d - W0) < dfree) || (((d - W0) == dfree) && (
spectrum(1)(d - W0) > Cdfree)))
1366 if ((W1 < dist_prof(
m - 1)) || (W < dist_prof(
m)))
goto F5;
1368 if (test_catastrophic && W == W1) {
1370 if (c > cat_treshold)
1385 if (stack_pos == -1)
goto end;
1387 S = S_stack(stack_pos);
1388 W = W_stack(stack_pos);
1389 b = b_stack(stack_pos);
1390 c = c_stack(stack_pos);
1396 if (W0 < dist_prof(
m - mf - 1))
goto F4;
1399 if ((W1 >= dist_prof(
m - 1)) && (W >= dist_prof(
m))) {
1401 if (test_catastrophic && stack_pos > 10000)
1405 if (stack_pos >= max_stack_size) {
1406 max_stack_size = 2 * max_stack_size;
1407 S_stack.set_size(max_stack_size,
true);
1408 W_stack.set_size(max_stack_size,
true);
1409 b_stack.set_size(max_stack_size,
true);
1410 c_stack.set_size(max_stack_size,
true);
1412 S_stack(stack_pos) = S1;
1413 W_stack(stack_pos) = W1;
1414 b_stack(stack_pos) = b + 1;
1415 c_stack(stack_pos) = c;
1419 if (test_catastrophic && W == W0) {
1421 if (c > cat_treshold)
1446 for (i = 0; i < (length >> 1); i++) {
1447 out = out | ((in & (1 << i)) << (length - 1 - (i << 1)));
1449 for (j = 0; j < (length - i); j++) {
1450 out = out | ((in & (1 << (j + i))) >> ((j << 1) - (length & 1) + 1));
1463 for (i = 0; i <
length; i++) {
1464 w += (in & (1 << i)) >> i;
1474 it_assert_debug(v1.size() == v2.size(),
"compare_spectra: wrong sizes");
1476 for (
int i = 0; i < v1.size(); i++) {
1477 if (v1(i) < v2(i)) {
1480 else if (v1(i) > v2(i)) {
1494 double t1 = 0, t2 = 0;
1495 for (
int i = 0; i < v1.size(); i++) {
1496 t1 += (double)v1(i) * weight_profile(i);
1497 t2 += (double)v2(i) * weight_profile(i);
1499 if (t1 < t2)
return 1;
1500 else if (t1 > t2)
return 0;