1 #include "trellis.h"
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5
6 // derived from the trellis state machine described in the ysf spec, Appendix B
7 uint8_t trellis_transitions[16][2] = {
8 {0b00, 0b11}, // 0000
9 {0b11, 0b00}, // 0001
10 {0b10, 0b01}, // 0010
11 {0b01, 0b10}, // 0011
12 {0b01, 0b10}, // 0100
13 {0b10, 0b01}, // 0101
14 {0b11, 0b00}, // 0110
15 {0b00, 0b11}, // 0111
16 {0b01, 0b10}, // 1000
17 {0b10, 0b01}, // 1001
18 {0b11, 0b00}, // 1010
19 {0b00, 0b11}, // 1011
20 {0b00, 0b11}, // 1100
21 {0b11, 0b00}, // 1101
22 {0b10, 0b01}, // 1110
23 {0b01, 0b10} // 1111
24 };
25
hamming_distance(uint8_t a,uint8_t b)26 uint8_t hamming_distance(uint8_t a, uint8_t b) {
27 uint8_t xored = a ^ b;
28 uint8_t i;
29 uint8_t result = 0;
30 for (i = 0; i < 8; i++) {
31 result += (xored >> i) & 1;
32 }
33 return result;
34 }
35
36 typedef struct {
37 uint8_t metric;
38 uint8_t *data;
39 } branch;
40
decode_trellis(uint8_t * input,uint8_t size,uint8_t * output)41 uint8_t decode_trellis(uint8_t *input, uint8_t size, uint8_t *output) {
42 uint8_t pos = 0;
43 uint8_t shift = 0;
44
45 uint8_t i;
46 branch *branches = (branch*) malloc(sizeof(branch) * 16);
47 uint8_t data_size = (size + 7) / 8;
48 for (i = 0; i < 16; i++) {
49 branches[i].metric = 0;
50 branches[i].data = (uint8_t*) malloc(data_size);
51 memset(branches[i].data, 0, data_size);
52 }
53
54 while (pos < size) {
55 uint8_t inpos = pos / 4;
56 uint8_t inshift = 2 * ( 3 - pos % 4 );
57 uint8_t in_transition = (input[inpos] >> inshift) & 0b11;
58
59 uint8_t outpos = pos / 8;
60 uint8_t outshift = ( 7 - pos % 8 );
61
62 //fprintf(stderr, "input: %i\n", in_transition);
63
64 branch *next_branches = (branch*) malloc(sizeof(branch) * 16);
65
66 for (i = 0; i < 16; i++) {
67 //fprintf(stderr, "evaluating state %i", i);
68
69 uint8_t k;
70 uint8_t best_metric = -1;
71 uint8_t selected = -1;
72 uint8_t outbit = (i & 0b1000) >> 3;
73 //fprintf(stderr, " outbit: %i", outbit);
74 for (k = 0; k < 2; k++) {
75 uint8_t previous_state = (( i << 1 ) & 0b1110 ) | k;
76 uint8_t transition = trellis_transitions[previous_state][outbit];
77 branch to_evaluate = branches[previous_state];
78 uint8_t metric = to_evaluate.metric + hamming_distance(in_transition, transition);
79 //fprintf(stderr, " metric for previous %i: %i", previous_state, metric);
80
81 if (k == 0 || metric < best_metric) {
82 best_metric = metric;
83 selected = previous_state;
84 }
85 }
86
87 branch selected_branch;
88 selected_branch.metric = best_metric;
89 selected_branch.data = (uint8_t*) malloc(data_size);
90 memcpy(selected_branch.data, branches[selected].data, data_size);
91 selected_branch.data[outpos] = selected_branch.data[outpos] | ( outbit << outshift );
92 next_branches[i] = selected_branch;
93 //fprintf(stderr, " selected: %i\n", selected);
94
95 }
96
97 for (i = 0; i < 16; i++) free(branches[i].data);
98 free(branches);
99 branches = next_branches;
100
101 pos++;
102 }
103
104 branch best_branch;
105 for (i = 0; i < 16; i++) {
106 branch candidate = branches[i];
107 if (i == 0 || candidate.metric < best_branch.metric) best_branch = candidate;
108 }
109
110 //fprintf(stderr, "metric for best branch: %i\n", best_branch.metric);
111 //fprintf(stderr, "data: %i %i\n", best_branch.data[0], best_branch.data[1]);
112 memcpy(output, best_branch.data, data_size);
113 uint8_t best_metric = best_branch.metric;
114
115 for (i = 0; i < 16; i++) free(branches[i].data);
116 free(branches);
117
118 return best_metric;
119 }
120